Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Bir noktanın eksene hizalı bir dikdörtgen veya herhangi bir genel çokgen içinde olup olmadığını test eden sorgulardır.
Kapsama testleri, coğrafi bilgi sistemlerinde (örn: bir konumun il sınırları içinde mi olduğu) ve bilgisayar grafiklerinde (seçim araçları) sıkça kullanılır.
Point-in-Rectangle testi, noktanın (x, y) koordinatlarının dikdörtgen sınırları (xmin, ymin, xmax, ymax) arasında olup olmadığını basit kıyaslamalarla kontrol eder.
Point-in-Polygon testi ise Ray Casting (Işınsal Arama) algoritması ile çözümlenir. Noktadan sağa doğru yatay sonsuz bir ışın gönderilir. Bu ışının çokgenin kenarlarını kaç kez kestiği sayılır. Eğer kesim sayısı tek sayı ise nokta çokgenin içindedir, çift sayı ise nokta dışındadır.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function isPointInPolygon(2 p: [number, number],3 polygon: [number, number][]4): boolean {5 let inside = false;6 const n = polygon.length;7 for (let i = 0, j = n - 1; i < n; j = i++) {8 const xi = polygon[i][0], yi = polygon[i][1];9 const xj = polygon[j][0], yj = polygon[j][1];1011 const intersect = ((yi > p[1]) !== (yj > p[1]))12 && (p[0] < (xj - xi) * (p[1] - yi) / (yj - yi) + xi);13 if (intersect) inside = !inside;14 }15 return inside;16}Modu, noktayı ve sınırları girin. Modlar: RECT (px,py; xmin,ymin,xmax,ymax), POLY (px,py; x1,y1; x2,y2; ...). Örnek: POLY; 2,2; 0,0; 5,0; 5,5; 0,5
Modu, noktayı ve sınırları girin. Modlar: RECT (px,py; xmin,ymin,xmax,ymax), POLY (px,py; x1,y1; x2,y2; ...). Örnek: POLY; 2,2; 0,0; 5,0; 5,5; 0,5
En İyi Durum: O(1) dikdörtgen testi için
Ortalama Durum: O(V) çokgen testi için (V: köşe sayısı)
En Kötü Durum: O(V)
O(1) ek bellek - Bu algoritmanın karmaşıklığı belirtilmemiş.
Sorgu ve Kapsama Testleri (Query & Containment Tests) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: