İki doğru kesişimi

İki doğrunun kesişip kesişmediğini saptamayı öğrenirsin.

İki doğru kesişimi

İki doğru parçasının kesişip kesişmediğini saptamak, çizgi düzenleme ve çarpışma algılamada temel bir işlemdir.

Standart yöntem yönelim testi ile çalışır: her parça diğerinin iki üçünü zıt yönlere ayırıyorsa kesişme vardır.

Dört yönelim testi yeterlidir; çapraz çarpım ile O(1)'de hesaplanır. Köşe durumlar için ek kontrol gerekebilir.

Yönelim testi

P₁P₂ parçası ile P₃P₄ parçası için dört çapraz çarpım hesaplarız: d₁ = orient(P₃, P₄, P₁), d₂ = orient(P₃, P₄, P₂), d₃ = orient(P₁, P₂, P₃), d₄ = orient(P₁, P₂, P₄).

Eğer d₁ ve d₂ zıt işaretliyse, P₁ ve P₂ P₃P₄ doğrusunun iki yanındadır. Aynısı d₃ ve d₄ için de geçerliyse, parçalar kesişir.

İşaret kontrolü (d > 0) != (d' > 0) ile yapılır.

Uygulama segments_intersect fonksiyonu

segments_intersect(p1, p2, p3, p4) yaz. İki parça kesişirse True, yoksa False. print(segments_intersect((0,0), (4,4), (0,4), (4,0))) ile True yazdır.

Örnek çözümü göster

def segments_intersect(p1, p2, p3, p4):
    # İki parça kesişir mi?
    def orient(a, b, c):
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    d1 = orient(p3, p4, p1)
    d2 = orient(p3, p4, p2)
    d3 = orient(p1, p2, p3)
    d4 = orient(p1, p2, p4)
    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return True
    return False
print(segments_intersect((0,0), (4,4), (0,4), (4,0)))

Kendini test et

Kesişim kavramları

yönelim

Çapraz çarpım
zıt yön

Kesişme var
aynı yön

Kesişme yok
O(1)

Sabit zaman
Parçalar ne zaman kesişir?
```
d1 = orient(p3, p4, p1)
d2 = orient(p3, p4, p2)
```
- d1 ve d2 aynı işaretliyse
- d1 ve d2 zıt işaretliyse
- d1 sıfırsa
- d2 sıfırsa
Cevabı göster

d1 ve d2 zıt işaretliyse — d1 ve d2 zıt işaretliyse P1 ve P2 doğrunun iki yanındadır.

yönelim işareti

if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > ____)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):

Cevabı göster

if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):

Sıradaki ders: En yakın nokta çifti

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler