İki doğru kesişimi
- Algoritmalar kursu
- Uzman seviye
- Ders 21/41
- 4 dk
İ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.
Başlangıç kodu
def segments_intersect(p1, p2, p3, p4):
# İki parça kesişir mi?Örnek çözüm
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)))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kesişim kavramları
| Kavram | Anlamı |
|---|---|
yönelim |
Çapraz çarpım |
zıt yön |
Kesişme var |
aynı yön |
Kesişme yok |
O(1) |
Sabit zaman |
2 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 Doğru cevap
- d1 sıfırsa
- d2 sıfırsa
Açıklama: d1 ve d2 zıt işaretliyse P1 ve P2 doğrunun iki yanındadır.
3 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)):if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):Açıklama: d2 > 0 ile zıt işaret sınanır.