Nokta poligonda mı
- Algoritmalar kursu
- Uzman seviye
- Ders 23/41
- 4 dk
İşin gönderme yöntemiyle nokta sorgulamayı öğrenirsin.
Nokta poligonda mı
Nokta poligonda mı problemi, bir noktanın çokgenin içinde mi dışında mı olduğunu saptar. En bilinen yöntem işin gönderme (ray casting) algoritmasıdır.
Önceden seçilmiş bir yönde (genellikle sağa) sonsuz bir işin gönderilir ve çokgen kenarlarıyla kaç kez kesiştiği sayılır. Tek sayıda kesişme içeride, çift sayıda dışarıda demektir.
Her kenar için tek bir karşılaştırma yeterlidir; toplam karmaşıklık O(n)'dir.
İşin gönderme uygulaması
Uygulamada her kenar için iki koşul sınanır: işinin y aralığına düşüp düşmediği ve noktanın x'inden sağda kesişip kesişmediği.
İlk koşul (yi > py) != (yj > py) ile sınanır. İkinci koşul, doğrusal interpolasyonla x kesişme noktasını hesaplar ve px ile karşılaştırır.
Her iki koşul sağlandığında inside değişkeni ters çevrilir. Döngü sonunda inside değeri döndürülür.
Uygulama point_in_polygon fonksiyonu
point_in_polygon(poly, px, py) yaz. Nokta içerideyse True, dışarıdaysa False. print(point_in_polygon([(0,0), (4,0), (4,3), (0,3)], 2, 1)) ile True yazdır.
Başlangıç kodu
def point_in_polygon(poly, px, py):
# Işın gönderme yöntemiÖrnek çözüm
def point_in_polygon(poly, px, py):
# Işın gönderme yöntemi
n = len(poly)
inside = False
j = n - 1
for i in range(n):
xi, yi = poly[i]
xj, yj = poly[j]
if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):
inside = not inside
j = i
return inside
print(point_in_polygon([(0,0), (4,0), (4,3), (0,3)], 2, 1))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 işin kesişme koşulu
if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + ____):if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):Açıklama: xi ile x-kesişme hesaplanır.
2 İşin gönderme kavramları
| Kavram | Anlamı |
|---|---|
tek kesişme |
İçeride |
çift kesişme |
Dışarıda |
sağa işin |
Yön |
O(n) |
Karmaşıklık |
3 İşin çift sayıda kesişirse nokta nerededir?
inside = not inside- Belirsiz
- İçeride
- Kenar üzerinde
- Dışarıda Doğru cevap
Açıklama: Çift kesişme dışarıda anlamına gelir.