Korsning (euklidisk geometri) - Intersection (Euclidean geometry)

I geometri är en skärningspunkt en punkt, linje eller kurva som är gemensam för två eller flera objekt (t.ex. linjer, kurvor, plan och ytor). Det enklaste fallet i euklidisk geometri är skärningspunkten mellan två distinkta linjer , som antingen är en punkt eller inte existerar om linjerna är parallella .

Bestämning av skärningspunkten mellan lägenheter- linjära geometriska objekt inbäddade i ett högre dimensionellt utrymme- är en enkel uppgift för linjär algebra , nämligen lösningen av ett system med linjära ekvationer . I allmänhet leder bestämningen av en skärning till olinjära ekvationer , som kan lösas numeriskt , till exempel med hjälp av Newton-iteration . Korsningsproblem mellan en linje och en konisk sektion (cirkel, ellips, parabel, etc.) eller en kvadric (sfär, cylinder, hyperboloid, etc.) leder till kvadratiska ekvationer som enkelt kan lösas. Korsningar mellan kvadriker leder till kvartsekvationer som kan lösas algebraiskt .

På ett plan

Två rader

För bestämning av skärningspunkten för två icke-parallella linjer

${\ displaystyle a_ {1} x+b_ {1} y = c_ {1}, \ a_ {2} x+b_ {2} y = c_ {2}}$

man får, från Cramers regel eller genom att ersätta en variabel, skärningspunktens koordinater  : ${\ displaystyle (x_ {s}, y_ {s})}$

${\ displaystyle x_ {s} = {\ frac {c_ {1} b_ {2} -c_ {2} b_ {1}} {a_ {1} b_ {2} -a_ {2} b_ {1}}} , \ quad y_ {s} = {\ frac {a_ {1} c_ {2} -a_ {2} c_ {1}} {a_ {1} b_ {2} -a_ {2} b_ {1}}} . \}$

(Om linjerna är parallella och dessa formler inte kan användas eftersom de innebär att dividera med 0.) ${\ displaystyle a_ {1} b_ {2} -a_ {2} b_ {1} = 0}$

Två linjesegment

För två icke-parallella linjesegment och det finns inte nödvändigtvis en skärningspunkt (se diagram), eftersom skärningspunkten för motsvarande linjer inte behöver finnas i linjesegmenten. För att kontrollera situationen använder man parametriska representationer av linjerna: ${\ displaystyle (x_ {1}, y_ {1}), (x_ {2}, y_ {2})}$${\ displaystyle (x_ {3}, y_ {3}), (x_ {4}, y_ {4})}$${\ displaystyle (x_ {0}, y_ {0})}$

${\ displaystyle (x (s), y (s)) = (x_ {1}+s (x_ {2} -x_ {1}), y_ {1}+s (y_ {2} -y_ {1} )),}$

${\ displaystyle (x (t), y (t)) = (x_ {3}+t (x_ {4} -x_ {3}), y_ {3}+t (y_ {4} -y_ {3} )).}$

Linjesegmenten skärs endast i en gemensam punkt på motsvarande rader om motsvarande parametrar uppfyller villkoret . Parametrarna är lösningen för det linjära systemet ${\ displaystyle (x_ {0}, y_ {0})}$${\ displaystyle s_ {0}, t_ {0}}$${\ displaystyle 0 \ leq s_ {0}, t_ {0} \ leq 1}$${\ displaystyle s_ {0}, t_ {0}}$

${\ displaystyle s (x_ {2} -x_ {1})-t (x_ {4} -x_ {3}) = x_ {3} -x_ {1},}$

${\ displaystyle s (y_ {2} -y_ {1})-t (y_ {4} -y_ {3}) = y_ {3} -y_ {1} \.}$

Det kan lösas för s och t med Cramers regel (se ovan ). Om villkoret är uppfyllt sätter man in eller i motsvarande parametriska representation och får skärningspunkten . ${\ displaystyle 0 \ leq s_ {0}, t_ {0} \ leq 1}$${\ displaystyle s_ {0}}$${\ displaystyle t_ {0}}$${\ displaystyle (x_ {0}, y_ {0})}$

Exempel: För linjesegmenten och man får det linjära systemet ${\ displaystyle (1,1), (3,2)}$${\ displaystyle (1,4), (2, -1)}$

${\ displaystyle 2s-t = 0}$

${\ displaystyle s+5t = 3}$

och . Det betyder: linjerna skär varandra vid en punkt . ${\ displaystyle s_ {0} = {\ tfrac {3} {11}}, t_ {0} = {\ tfrac {6} {11}}}$${\ displaystyle ({\ tfrac {17} {11}}, {\ tfrac {14} {11}})}$

Anmärkning: Med tanke på linjer istället för segment, bestämda av punkterpar, kan varje villkor tappas och metoden ger linjens skärningspunkt (se ovan ). ${\ displaystyle 0 \ leq s_ {0}, t_ {0} \ leq 1}$

En linje och en cirkel

För skärningspunkten mellan

• linje och cirkel${\ displaystyle ax+by = c}$ ${\ displaystyle x^{2}+y^{2} = r^{2}}$

man löser linjeekvationen för x eller y och ersätter den i cirkelns ekvation och får lösningen (med formeln för en kvadratisk ekvation) med ${\ displaystyle (x_ {1}, y_ {1}), (x_ {2}, y_ {2})}$

${\ displaystyle x_ {1/2} = {\ frac {ac \ pm b {\ sqrt {r^{2} (a^{2}+b^{2})-c^{2}}}} { a^{2}+b^{2}}} \,}$

${\ displaystyle y_ {1/2} = {\ frac {bc \ mp a {\ sqrt {r^{2} (a^{2}+b^{2})-c^{2}}}} { a^{2}+b^{2}}} \,}$

om Om detta villkor håller med strikt ojämlikhet finns det två skärningspunkter; i detta fall kallas linjen en sekant linje i cirkeln, och linjesegmentet som förbinder skärningspunkterna kallas ett ackord av cirkeln. ${\ displaystyle r^{2} (a^{2}+b^{2})-c^{2} \ geq 0 \.}$

Om det hålls finns det bara en skärningspunkt och linjen är tangent till cirkeln. Om den svaga ojämlikheten inte håller, skär linjen inte cirkeln. ${\ displaystyle r^{2} (a^{2}+b^{2})-c^{2} = 0}$

Om cirkelns mittpunkt inte är ursprunget, se. Skärningspunkten mellan en linje och en parabel eller hyperbol kan behandlas analogt.

Två cirklar

Bestämning av skärningspunkterna mellan två cirklar

• ${\ displaystyle (x-x_ {1})^{2}+(y-y_ {1})^{2} = r_ {1}^{2}, \ \ quad (x-x_ {2})^ {2}+(y-y_ {2})^{2} = r_ {2}^{2}}$

kan reduceras till föregående fall av skärning av en linje och en cirkel. Genom att subtrahera de två givna ekvationerna får man linjeekvationen:

${\ displaystyle 2 (x_ {2} -x_ {1}) x+2 (y_ {2} -y_ {1}) y = r_ {1}^{2} -x_ {1}^{2} -y_ {1}^{2} -r_ {2}^{2}+x_ {2}^{2}+y_ {2}^{2}.}$

Denna speciella linje är den radikala linjen i de två cirklarna.

Specialfall  :${\ displaystyle \; x_ {1} = y_ {1} = y_ {2} = 0}$
I detta fall är ursprunget mitten av den första cirkeln och den andra mitten ligger på x-axeln (s. Diagram). Ekvationen för den radikala linjen förenklar till och skärningspunkterna kan skrivas som med ${\ displaystyle \; 2x_ {2} x = r_ {1}^{2} -r_ {2}^{2}+x_ {2}^{2} \;}$${\ displaystyle (x_ {0}, \ pm y_ {0})}$

${\ displaystyle x_ {0} = {\ frac {r_ {1}^{2} -r_ {2}^{2}+x_ {2}^{2}} {2x_ {2}}}, \ quad y_ {0} = {\ sqrt {r_ {1}^{2} -x_ {0}^{2}}} \.}$

I fallet med cirklarna har inga poäng gemensamt. När det gäller cirklarna har en gemensam punkt och den radikala linjen är en gemensam tangent. ${\ displaystyle r_ {1}^{2} <x_ {0}^{2}}$
${\ displaystyle r_ {1}^{2} = x_ {0}^{2}}$

Alla generella fall som skrivits ovan kan omvandlas genom ett skift och en rotation till specialfallet.

Skärningspunkten mellan två skivor (interiören i de två cirklarna) bildar en form som kallas en lins .

Två koniska sektioner

Problemet med skärningspunkten mellan en ellips/hyperbola/parabel med en annan konisk sektion leder till ett system med kvadratiska ekvationer , som enkelt kan lösas i speciella fall genom eliminering av en koordinat. Särskilda egenskaper hos koniska sektioner kan användas för att få en lösning . I allmänhet kan skärningspunkterna bestämmas genom att lösa ekvationen med en Newton -iteration. Om a) båda konerna ges implicit (genom en ekvation) är en tvådimensionell Newton-iteration b) en implicit och den andra parametriskt ges en 1-dimensionell Newton-iteration nödvändig. Se nästa avsnitt.

Två släta kurvor

Två kurvor i (tvådimensionellt utrymme), som är kontinuerligt differentierbara (dvs det finns ingen skarp böjning), har en skärningspunkt om de har en punkt i planet gemensamt och har vid denna punkt ${\ displaystyle \ mathbb {R} ^{2}}$

a: olika tangentlinjer ( tvärgående skärningspunkt ), eller

b: tangentlinjen gemensamt och de korsar varandra ( vidrör korsningen , se diagram).

Om båda kurvorna har en punkt S och tangentlinjen där gemensamt men inte korsar varandra, de är bara röra vid punkten S .

Eftersom rörande korsningar förekommer sällan och är svåra att hantera, utelämnar följande överväganden detta fall. Under alla omständigheter förutsätts alla nödvändiga differentialvillkor. Bestämningen av skärningspunkter leder alltid till en eller två olinjära ekvationer som kan lösas med Newton-iteration. En lista över de fall som dyker upp följer:

• Om båda kurvorna uttryckligen ges: ger ekvationen dem likhet${\ displaystyle y = f_ {1} (x), \ y = f_ {2} (x)}$

${\ displaystyle f_ {1} (x) = f_ {2} (x) \.}$

• Om båda kurvorna parametriskt ges:${\ displaystyle C_ {1} :( x_ {1} (t), y_ {1} (t)), \ C_ {2} :( x_ {2} (s), y_ {2} (s)). }$

Att jämställa dem ger två ekvationer i två variabler:

${\ displaystyle x_ {1} (t) = x_ {2} (s), \ y_ {1} (t) = y_ {2} (s) \.}$

• Om en kurva är parametriskt och den andra implicit ges:${\ displaystyle C_ {1} :( x_ {1} (t), y_ {1} (t)), \ C_ {2}: f (x, y) = 0.}$

Detta är det enklaste fallet förutom det uttryckliga fallet. Man måste infoga den parametriska representationen av i kurvan, och man får ekvationen: ${\ displaystyle C_ {1}}$${\ displaystyle f (x, y) = 0}$${\ displaystyle C_ {2}}$

${\ displaystyle f (x_ {1} (t), y_ {2} (t)) = 0 \.}$

• Om båda kurvorna implicit ges:${\ displaystyle C_ {1}: f_ {1} (x, y) = 0, \ C_ {2}: f_ {2} (x, y) = 0.}$

Här är en skärningspunkt en lösning av systemet

${\ displaystyle f_ {1} (x, y) = 0, \ f_ {2} (x, y) = 0 \.}$

Varje Newton -iteration behöver bekväma startvärden, som kan härledas genom en visualisering av båda kurvorna. En parametriskt eller uttryckligen given kurva kan enkelt visualiseras, eftersom det för varje parameter t respektive x är lätt att beräkna motsvarande punkt. För implicit givna kurvor är denna uppgift inte lika lätt. I detta fall måste man bestämma en kurvpunkt med hjälp av startvärden och en iteration. Ser .

Exempel:

1: och cirkel (se diagram). ${\ displaystyle C_ {1} :( t, t^{3})}$${\ displaystyle C_ {2} :( x-1)^{2}+(y-1)^{2} -10 = 0}$

Newton -iterationen för funktion ${\ displaystyle t_ {n+1}: = t_ {n}-{\ frac {f (t_ {n})} {f '(t_ {n})}}}}$

${\ displaystyle f (t) = (t-1)^{2}+(t^{3} -1)^{2} -10}$måste bli gjort. Som startvärden kan man välja −1 och 1,5.

Skärningspunkterna är: (-1.1073, -1.3578), (1.6011, 4.1046)

2:${\ displaystyle C_ {1}: f_ {1} (x, y) = x^{4}+y^{4} -1 = 0,}$

${\ displaystyle C_ {2}: f_ {2} (x, y) = (x-0.5)^{2}+(y-0.5)^{2} -1 = 0}$ (se diagram).

Newton -iterationen

${\ displaystyle {x_ {n+1} \ välj y_ {n+1}} = {x_ {n}+\ delta _ {x} \ välj y_ {n}+\ delta _ {y}}}$måste utföras, var är lösningen på det linjära systemet${\ displaystyle {\ delta _ {x} \ välj \ delta _ {y}}}$

${\ displaystyle {\ begin {pmatrix} {\ frac {\ partiell f_ {1}} {\ partiell x}} och {\ frac {\ partiell f_ {1}} {\ partiell y}} \\ {\ frac { \ partiell f_ {2}} {\ partiell x}} och {\ frac {\ partiell f_ {2}} {\ partiell y}} \ slut {pmatrix}} {\ delta _ {x} \ välj \ delta _ { y}} = { -f_ {1} \ välj -f_ {2}}}$vid ett tillfälle . Som startvärden kan man välja (−0,5, 1) och (1, −0,5).${\ displaystyle (x_ {n}, y_ {n})}$

Det linjära systemet kan lösas med Cramers regel.

Skärningspunkterna är (-0.3686, 0.9953) och (0.9953, -0.3686).

Två polygoner

Om man vill bestämma skärningspunkterna för två polygoner kan man kontrollera skärningspunkten mellan alla par av linjesegment av polygonerna (se ovan ). För polygoner med många segment är denna metod ganska tidskrävande. I praktiken accelererar man skärningsalgoritmen med hjälp av fönstertester . I detta fall delar man polygonerna i små delpolygoner och bestämmer det minsta fönstret (rektangel med sidor parallellt med koordinataxlarna) för en delpolygon. Innan den tidskrävande bestämningen av skärningspunkten för två linjesegment påbörjas testas alla fönsterpar för gemensamma punkter. Ser.

I rymden (tre dimensioner)

I det tredimensionella rummet finns skärningspunkter (gemensamma punkter) mellan kurvor och ytor. I följande avsnitt betraktar vi endast tvärgående skärningspunkt .

En linje och ett plan

Skärningspunkten mellan en linje och ett plan i allmän position i tre dimensioner är en punkt.

Vanligtvis representeras en linje i rymden parametriskt och ett plan av en ekvation . Att infoga parameterrepresentationen i ekvationen ger den linjära ekvationen ${\ displaystyle (x (t), y (t), z (t))}$${\ displaystyle ax+by+cz = d}$

${\ displaystyle ax (t)+by (t)+cz (t) = d \,}$

för parameter för skärningspunkten . ${\ displaystyle t_ {0}}$${\ displaystyle (x (t_ {0}), y (t_ {0}), z (t_ {0}))}$

Om den linjära ekvationen inte har någon lösning ligger linjen antingen på planet eller är parallell med den.

Tre plan

Om en linje definieras av två skärande plan och ska skäras av ett tredje plan , måste den gemensamma skärningspunkten för de tre planen utvärderas. ${\ displaystyle \ varepsilon _ {i}: \ {\ vec {n}} _ {i} \ cdot {\ vec {x}} = d_ {i}, \ i = 1,2}$${\ displaystyle \ varepsilon _ {3}: \ {\ vec {n}} _ {3} \ cdot {\ vec {x}} = d_ {3}}$

Tre plan med linjära oberoende normala vektorer har skärningspunkten ${\ displaystyle \ varepsilon _ {i}: \ {\ vec {n}} _ {i} \ cdot {\ vec {x}} = d_ {i}, \ i = 1,2,3}$${\ displaystyle {\ vec {n}} _ {1}, {\ vec {n}} _ {2}, {\ vec {n}} _ {3}}$

${\ displaystyle {\ vec {p}} _ {0} = {\ frac {d_ {1} ({\ vec {n}} _ {2} \ gånger {\ vec {n}} _ {3})+ d_ {2} ({\ vec {n}} _ {3} \ times {\ vec {n}} _ {1})+d_ {3} ({\ vec {n}} _ {1} \ times { \ vec {n}} _ {2})} {{\ vec {n}} _ {1} \ cdot ({\ vec {n}} _ {2} \ gånger {\ vec {n}} _ {3 })}}} \.}$

För beviset bör man fastställa med hjälp av reglerna för en skalär trippelprodukt . Om den skalära trippelprodukten är lika med 0, har antingen planen inte trippelkorsningen eller så är det en linje (eller ett plan, om alla tre planen är desamma). ${\ displaystyle {\ vec {n}} _ {i} \ cdot {\ vec {p}} _ {0} = d_ {i}, \ i = 1,2,3,}$

En kurva och en yta

Analogt till planhöljet leder följande fall till olinjära system, som kan lösas med en 1- eller 3-dimensionell Newton-iteration.

• parametrisk kurva och${\ displaystyle C: (x (t), y (t), z (t))}$

parametrisk yta ${\ displaystyle S: (x (u, v), y (u, v), z (u, v)) \,}$

• parametrisk kurva och${\ displaystyle C: (x (t), y (t), z (t))}$

implicit yta ${\ displaystyle S: f (x, y, z) = 0 \.}$

Exempel:

parametrisk kurva och${\ displaystyle C: (t, t^{2}, t^{3})}$

implicit yta (s. bild).${\ displaystyle S: x^{4}+y^{4}+z^{4} -1 = 0}$

Skärningspunkterna är: (−0.8587, 0.7374, −0.6332), (0.8587, 0.7374, 0.6332).

En linje -sfärkorsning är ett enkelt specialfall.

Liksom fallet med en linje och ett plan består skärningspunkten mellan en kurva och en yta i allmänt läge av diskreta punkter, men en kurva kan vara delvis eller helt inne i en yta.

En linje och en polyeder

Två ytor

Två tvärgående skärande ytor ger en skärningskurva . Det enklaste fallet är skärningslinjen mellan två icke-parallella plan.

Se även

• Beräkningsgeometri
• Ekvation för en rad
• Korsning (uppsättningsteori)
• Korsningsteori

Referenser

Vidare läsning

• Nicholas M. Patrikalakis och Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing , Springer, 2002, ISBN  3540424547 , 9783540424543, s. 408. [1]