Nokta Poligonun İçinde mi? (Point in Polygon)

Bir noktanın bir poligonun içinde olup olmadığını nasıl anlarız? Bu öyle önemli bir sorudur ki bir oyun geliştiricisi de bu soruyu sorabilir, grafik işlemleri veya harita işlemleri üzerine bir desktop yada mobil application geliştiren bir yazılımcı da sorabilir. Daha başka alanlarda da karşımıza çıkabilir.

Bununla ilgili buradan göreceğiniz üzere ön plana çıkan 2 tür algoritma vardır. Bunlardan kısa kısa söz edelim ardından kendi kullandığım farklı ve basit bir yöntemden söz etmek istiyorum.

Ray Casting Algoritması

Ray Casting algoritması oldukça basit bir mantık üzerine kuruludur. Bize şunu söyler; eğer bir poligonun dışından hedef noktaya doğru bir ışın gönderirseniz ve çarpıştığı çizgi segmenti sayısı tekse poligon içindedir, çiftse eğer poligon dışındadır. Belli başlı istisnalar dışında iyi çalışır. Cpu dostu bir algoritma olduğu için sık kullanılır ve populerdir. Bununla hazırlanmış bir kodu buradan inceleyebilirsiniz.

Winding Number Algoritması

Trigonometrik hesaplamalarla işleri sürdürdüğüm bir dönemde ismini bilmiyor olsam da kendi başıma kurgulayıp kullanırdım, populer bir algoritma olduğunu sonradan öğrendim. Bu algoritma noktanın etrafını saran poligon kenarlarını baz alır. Uygulama şekillerinden biri açı biriktirmektir. Yukarıdaki resimdeki örneklere bakarsanız A noktası ile kenarların açılarının toplamı hesaplanır. Sağ örnekte gördüğünüz gibi soldaki örnekte nokta ile kenarlar arasındaki açılar toplamı 360 derecedir, sağdakinde 0’dır. Ters trigonometrik işlemler gerektirdiği için optimizasyon endişesi taşıyabilirsiniz. Fakat 2000’li yıllarda daha modernize, optimize, açıları hesaplamaya gerek duyulmayan yöntemler keşfedildi. Oldukça optimize çalıştığı iddia edilen bu makaleye bakabilirsiniz.

Farklı bir yöntem

Size belki pek rastlamayacağınız bir yöntem sunmak istiyorum. Bu yöntem çok acil ihtiyacım olduğunda geliştirdiğim bir algoritmadır. Temel dayanağım poligonu meydana getiren kenar segmentlerinin birbirini takip eden bir yön ile dizilmiş olmasıydı. Genelde poligonları bu şekilde belirleriz, her kenar bir önceki kenarın bitiş noktasını başlangıç kabul eder. Bu saat yönünde yada saat yönünün tersine olabilir.

Avantajlarına gelirsek kenarlarla yapacağımız döngü bitmeden çıkma olanağına sahiptir, yani bir kural ihlali dahi olsa döngü sonlanır ve size sonucu verir. Bu nedenle optimize çalışır.

Görselde de ifade ettiğim şekilde nokta bağlantıları bir yön üzerinde ilerliyor. (Saat yönünde ) Bu şu anlama geliyor; eğer hedef nokta poligonun içindeyse, noktanın bu kenarla yapacağı dikey nokta çarpımlarının tamamı negatif çıkmalı. (Dizilim yönü saat yönünün tersine olsaydı pozitif olarak düşünmeliydik ) Eğer bir tanesi bile pozitif çıkarsa olumsuz dönüp, döngüyü sonlandırmalıyız.

Bunu kodlara dökecek olursak eğer;

function is_point_in_polygon(_p,_obj){
	for(var i=0;i<array_length(_obj.lines);i++){
		var line=_obj.lines[i];
		var vl=line.make_vector();
		var pv=new vec2(_p.x-line.p1.x,_p.y-line.p1.y);
		var pp=pv.perp_product_with(vl.normalise());
		if(pp>0)return false;
	}
	return true;
}

Gördüğünüz gibi kenarın vektörünü alıyoruz, kenarın 1. noktasıyla teste soktuğumuz noktanın vektörünü alıyoruz, bu ikisinin dikey nokta çarpımı ile dik projeksiyonunu alıyoruz. Eğer herhangi bir kenarla yapılan projeksiyon pozitif dönerse fonksiyonumuz olumsuz dönüyor. Bu avantajlı bir durumdur, noktanın poligon dışında olduğu çoğu durumda döngü bitmeden fonksiyon sonlanacaktır.

Ben bazı özel durumlar haricinde bunu tercih ediyorum ve bir sorunla karşılaşmadım. Fakat diğer populer örneklerden birini kullanabilirsiniz.

Eğer hesaplamaları anlamakta güçlük çekiyorsanız vektör hesaplamaları konusundaki kaleme aldığım vektörler yazı serisini okuyabilirsiniz.