Segmentlerin kesişimi için formül. Çizgiler kesişiyor mu: bir düzlemdeki parçaların kesişimi

İki bölüm verilsin. İlki noktalarla verilmiştir P 1 (x 1 ;y 1) Ve P 2 (x 2 ;y 2). İkincisi puanlarla verilir P 3 (x 3 ;y 3) Ve P 4 (x 4 ;y 4).

Segmentlerin göreceli konumu vektör ürünleri kullanılarak kontrol edilebilir:

Segmenti göz önünde bulundurun P 3 P 4 ve noktalar P1 Ve P2.

Nokta P1çizginin solunda yer alır P 3 P 4, onun için vektör çarpımı v 1 > 0Çünkü vektörler pozitif yönlüdür.
Nokta P2çizginin sağında yer alır, bunun için vektör çarpımı v2< 0 Çünkü vektörler negatif yönlüdür.

Konuya açıklık getirmek için P1 Ve P2 düz bir çizginin karşıt taraflarında uzanmak P 3 P 4 koşulun sağlanması yeterlidir v 1 v 2< 0 (vektör çarpımlarının zıt işaretleri vardı).

Segment için de benzer bir muhakeme yapılabilir. P 1 P 2 ve puanlar P3 Ve S4.

Yani eğer v 1 v 2< 0 Ve v 3 v 4< 0 , daha sonra segmentler kesişir.

İki vektörün çapraz çarpımı aşağıdaki formül kullanılarak hesaplanır:

Nerede:
balta, evet- ilk vektörün koordinatları,
bx, ile- ikinci vektörün koordinatları.

Koordinatları belirtilen iki farklı noktadan geçen bir doğrunun denklemi.

Bir doğru üzerinde çakışmayan iki nokta verilsin: P1 koordinatlarla ( x 1 ;y 1) Ve P2 koordinatlarla (x2;y2). Buna göre, noktada orijini olan bir vektör P1 ve bir noktada bitiyorum P2 koordinatları var (x 2 -x 1 , y 2 -y 1). Eğer P(x, y) bir çizgi üzerinde rastgele bir noktadır, o zaman vektörün koordinatları P 1 P eşit (x - x 1, y - y 1).

Vektör çarpımını kullanarak, vektörlerin doğrusal olma koşulu P 1 P Ve P 1 P 2şu şekilde yazılabilir:
|P 1 P ,P 1 P 2 |=0, yani (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
veya
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Son denklem şu şekilde yeniden yazılır:
balta + by + c = 0, (1)
Nerede
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Yani düz çizgi (1) formundaki bir denklemle belirtilebilir.

Çizgilerin kesişme noktası nasıl bulunur?
Açık çözüm, çizgi denklemleri sistemini çözmektir:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Sembolleri girin:

Burada D sistemin belirleyicisidir ve Dx,Dy- katsayılar sütununun karşılık gelen bilinmeyenle bir serbest terimler sütunu ile değiştirilmesinden kaynaklanan belirleyiciler. Eğer D ≠ 0 ise sistem (2) belirlidir, yani tek bir çözümü vardır. Bu çözüm aşağıdaki formüller kullanılarak bulunabilir: x 1 =D x /D, y 1 =D y /D bunlara Cramer formülleri denir. İkinci dereceden determinantın nasıl hesaplandığına dair kısa bir hatırlatma. Determinant iki köşegeni birbirinden ayırır: ana ve ikincil. Ana köşegen, determinantın sol üst köşesinden sağ alt köşesine doğru alınan elemanlardan oluşur. Yan çapraz - sağ üstten sol alta. İkinci dereceden determinant, ana köşegenin elemanlarının çarpımından ikincil köşegenin elemanlarının çarpımına eşittir.

Çizgilerin kesişme noktası

Bize katsayıları ve ile tanımlanan iki düz çizgi verilsin. Kesişme noktalarını bulmanız veya çizgilerin paralel olduğunu bulmanız gerekir.

Çözüm

Eğer iki doğru paralel değilse kesişirler. Kesişme noktasını bulmak için iki düz çizgi denkleminden oluşan bir sistem oluşturup çözmek yeterlidir:

Cramer formülünü kullanarak sisteme istenilen çözümü hemen buluruz. kesişim noktası:

Payda sıfır ise, yani.

o zaman sistemin çözümü yoktur (doğrudan paralel ve çakışmıyor) veya sonsuz sayıda var (doğrudan kibrit). Bu iki durumu birbirinden ayırmak gerekiyorsa, çizgilerin katsayılarının ve katsayılarıyla aynı orantı katsayısıyla orantılı olup olmadığını kontrol etmek gerekir; bunun için her iki belirleyiciyi de hesaplamak yeterlidir; sıfıra eşitse çizgiler çakışır:

Uygulama

struct pt(double x, y;); yapı satırı(çift a, b, c;); constdouble EPS =1e-9; double det (double a, double b, double c, double d)(return a * d - b * c;) bool kesişim (satır m, satır n, pt & res)(double zn = det (m.a, m.b, n.a) , bilgi yok);if(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

“Serisinden Ders” Geometrik algoritmalar»

Merhaba sevgili okuyucu.

İpucu 1: İki çizginin kesişme noktasının koordinatları nasıl bulunur?

Üç yeni fonksiyon daha yazalım.

LinesCross() işlevi, kesişmek iki mi bölüm. İçinde bölümlerin göreceli konumu vektör ürünleri kullanılarak belirlenir. Vektör çarpımlarını hesaplamak için bir fonksiyon yazacağız – VektorMulti().

Karşılaştırma işlemini gerçekleştirmek için RealLess() fonksiyonu kullanılacaktır.<” (строго меньше) для вещественных чисел.

Görev 1. İki segment koordinatlarıyla verilmiştir. belirleyen bir program yazınız. bu bölümler kesişiyor mu? kesişim noktasını bulmadan.

Çözüm
. İkincisi noktalarla verilir.

Segmenti ve noktaları göz önünde bulundurun ve .

Nokta çizginin solunda yer alır, bunun için vektör çarpımı > 0, çünkü vektörler pozitif yönlüdür.

Nokta, vektör çarpımının olduğu çizginin sağında bulunur. < 0, так как векторы отрицательно ориентированы.

Noktaların düz çizginin karşıt taraflarında yer alması için koşulun sağlanması yeterlidir.< 0 (векторные произведения имели противоположные знаки).

Segment ve noktalar için de benzer bir akıl yürütme yapılabilir.

Yani eğer , daha sonra segmentler kesişir.

Bu koşulu kontrol etmek için LinesCross() işlevi kullanılır ve vektör çarpımlarını hesaplamak için VektorMulti() işlevi kullanılır.

ax, ay – ilk vektörün koordinatları,

bx, by – ikinci vektörün koordinatları.

Geometri4 programı; (2 doğru parçası kesişiyor mu?) Const _Eps: Real=1e-4; (hesaplama doğruluğu) var x1,y1,x2,y2,x3,y3,x4,y4: gerçek; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; (Kesinlikle küçüktür) begin RealLess:= b-a> _Eps end; (RealLess)fonksiyonu VektorMulti(ax,ay,bx,by:real): gerçek; (ax,ay - a koordinatları bx,by - b koordinatları) begin vektörmulti:= ax*by-bx*ay; end;Fonksiyon DoğrularıÇapraz(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; (Bölümler kesişiyor mu?) begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); if RealLess(v1*v2,0) ve RealLess(v3*v4,0) (v1v2)<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

Program yürütme sonuçları:

Segmentlerin koordinatlarını girin: -1 1 2 2,52 2 1 -1 3
Evet.

Koordinatlarıyla belirtilen doğru parçalarının kesişip kesişmediğini belirleyen bir program yazdık.

Bir sonraki derste bir noktanın üçgenin içinde olup olmadığını belirlemek için kullanılabilecek bir algoritma oluşturacağız.

Sevgili okuyucu.

Geometrik Algoritmalar serisinden birçok dersle zaten tanıştınız. Her şey erişilebilir bir şekilde yazılmış mı? Bu derslerle ilgili geri bildirim bırakırsanız çok minnettar olacağım. Belki bir şeylerin hala iyileştirilmesi gerekiyor.

Saygılarımla Vera Gospodarets.

İki bölüm verilsin. İlki noktalarla verilmiştir P 1 (x 1 ;y 1) Ve P 2 (x 2 ;y 2). İkincisi puanlarla verilir P 3 (x 3 ;y 3) Ve P 4 (x 4 ;y 4).

Segmentlerin göreceli konumu vektör ürünleri kullanılarak kontrol edilebilir:

Segmenti göz önünde bulundurun P 3 P 4 ve noktalar P1 Ve P2.

Nokta P1çizginin solunda yer alır P 3 P 4, onun için vektör çarpımı v 1 > 0Çünkü vektörler pozitif yönlüdür.
Nokta P2çizginin sağında yer alır, bunun için vektör çarpımı v2< 0 Çünkü vektörler negatif yönlüdür.

Konuya açıklık getirmek için P1 Ve P2 düz bir çizginin karşıt taraflarında uzanmak P 3 P 4 koşulun sağlanması yeterlidir v 1 v 2< 0 (vektör çarpımlarının zıt işaretleri vardı).

Segment için de benzer bir muhakeme yapılabilir. P 1 P 2 ve puanlar P3 Ve S4.

Yani eğer v 1 v 2< 0 Ve v 3 v 4< 0 , daha sonra segmentler kesişir.

İki vektörün çapraz çarpımı aşağıdaki formül kullanılarak hesaplanır:

Nerede:
balta, evet- ilk vektörün koordinatları,
bx, ile— ikinci vektörün koordinatları.

Koordinatları belirtilen iki farklı noktadan geçen bir doğrunun denklemi.

Bir doğru üzerinde çakışmayan iki nokta verilsin: P1 koordinatlarla ( x 1 ;y 1) Ve P2 koordinatlarla (x2;y2).

Çizgilerin kesişimi

Buna göre, noktada orijini olan bir vektör P1 ve bir noktada bitiyorum P2 koordinatları var (x 2 -x 1 , y 2 -y 1). Eğer P(x, y) bir çizgi üzerinde rastgele bir noktadır, o zaman vektörün koordinatları P 1 P eşit (x - x 1, y - y 1).

Vektör çarpımını kullanarak, vektörlerin doğrusal olma koşulu P 1 P Ve P 1 P 2şu şekilde yazılabilir:
|P 1 P,P 1 P 2 |=0, yani (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
veya
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Son denklem şu şekilde yeniden yazılır:
balta + by + c = 0, (1)
Nerede
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Yani düz çizgi (1) formundaki bir denklemle belirtilebilir.

Çizgilerin kesişme noktası nasıl bulunur?
Açık çözüm, çizgi denklemleri sistemini çözmektir:

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

Sembolleri girin:

Burada D sistemin belirleyicisidir ve Dx,Dy- katsayılar sütununun karşılık gelen bilinmeyenle ve serbest terimler sütunuyla değiştirilmesinden kaynaklanan belirleyiciler. Eğer D ≠ 0 ise sistem (2) belirlidir, yani tek bir çözümü vardır. Bu çözüm aşağıdaki formüller kullanılarak bulunabilir: x 1 =D x /D, y 1 =D y /D bunlara Cramer formülleri denir. İkinci dereceden determinantın nasıl hesaplandığına dair kısa bir hatırlatma. Determinant iki köşegeni birbirinden ayırır: ana ve ikincil. Ana köşegen, determinantın sol üst köşesinden sağ alt köşesine doğru alınan elemanlardan oluşur. Yan çapraz - sağ üstten sol alta. İkinci dereceden determinant, ana köşegenin elemanlarının çarpımından ikincil köşegenin elemanlarının çarpımına eşittir.