Nokta poligonda mı

İş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.

Örnek çözümü göster

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))

Kendini test et

işin kesişme koşulu

if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + ____):

Cevabı göster

if ((yi > py) != (yj > py)) and (px < (xj - xi) * (py - yi) / (yj - yi) + xi):

İşin gönderme kavramları

tek kesişme

İçeride
çift kesişme

Dışarıda
sağa işin

Yön
O(n)

Karmaşıklık
İşin çift sayıda kesişirse nokta nerededir?
```
inside = not inside
```
- Belirsiz
- İçeride
- Kenar üzerinde
- Dışarıda
Cevabı göster

Dışarıda — Çift kesişme dışarıda anlamına gelir.

Sıradaki ders: Özet - Geometry

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler