c++ da noktalar kapalı alan içindemi? tarzında algoritma

[tunahanabi]

nokta koordinatlarını kullandığımız bir proje yapıyoruz.exe mizin bu noktaların kapalı bi alan içinde kalıp kalmadığını sorgulamasını istiyoruz.
nokta X ve Y koordinatlarına sahip.
bölge ise 4 köşeli DEĞİL çok kenarlı bi yapıya sahip. 10-15 köşe noktası var ve kenarlar düzenli değil. bu noktaların koordinatları sabit ve elimizde.
bize lazım olan; programa girilen herbir noktanın bu çokgen alanın içinde mi yoksa dışında mı kaldığını sorgulayan bi algoritma.
şimdiden yardımlarınız için teşekkürler.
Turbo c++ kullanıyoruz

[tunahanabi]

arkadaşlar görürumki kimse cevap yazmamış. konuyu tam açıklayamadımmı?
elimde bi kod car ve ben hiçbişey anlamadım
struct yapısını ve dizi yapısını kullanmadan aşağıdaki kodu nasıl yazabilirim. ayrıca for ve if döngülerini de pek anlayamadım. yardımcı olursanız sevinirim.

================================================== =====

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon[0];
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}

if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
}

[myavuzselim]

Benim aklima gelen bir yöntem:

Test edecegin nokta T = (tx,ty) olsun.
Cokgenin (çokgene C diyelim) noktalari P_i = (x_i,y_i), i=1..n olsun.

Simdi T noktasindan herhangi bir D dogrusunu geçir.
En kolayi: D: X = tx

Sonra D ile C'nin kesisimindeki bütün noktalari bul, bu noktalarin kümesine de K diyelim.

K'nin elemanlari 2 bölümden olusuyor, o da
1) T'nin üst tarafinda olanlar (K1)
2) T'nin alt tarafinda olanlar (K2)
Eger K1'in eleman sayisi tek sayi ise noktan çokgenin içindedir. Yoksa degildir.
(K1'in eleman sayisi tek ise K2'ninki de tek oluyor. Cünkü K'nin eleman sayisi çift olmak zorunda).

Peki K'nin elemanlarini nasil bulacaksin?
D ile ] (x_i,y_i), (x_ i+1,y_ i+1) [, i=1..n dogru parçalarinin kesisimini bularak.
Ama burada en zor durum bazi sinirdaki durumlar. Eger resim ekleyebilirsem bu sinirdaki durumlari çizip göstermeye çalisirim. Anlatmasi zor geliyor da.


Bir de benim bu anlattiklarim kesin degil. Bir yerlerde hatali bir mantik yürütmüs olabilirim. Dogru olsa bile bu is için cok daha iyi algoritmalar vardir büyük bir ihtimalle. Ama benim akil yürütmek daha hosuma gidiyor.

[myavuzselim]

Simdi pek uzun cümleler kurasim gelmiyor, ama tek söyleyebilecegim, birinci ve üçüncü resimlerdeki okla isaretli bölgeleri tek nokta olarak K'ya dahil etmen, ikinci ve dördüncü resimlerde isaretli bölgeleri de K'ya dahil etmemen.
Besinci resimdeki gibi bir durumla karsilastigin anda da algoritmayi durdurup hemen "false" döndürmen olacak.

Tabi ben bu algoritmada çokgenin "concave" (http://mathworld.wolfram.com/ConcavePolygon.html) olabilecegini düsündüm.

Eger öyle degilse, o zaman isin biraz daha kolaylasir.
O zaman TP_i x TP_(i+1), i=1..n degerlerinin isaretlerinin her i için ayni olup olmadigina bakman sanirim yeterli olur. Burada TP_i; T ile P_i den olusan vektör oluyor, ve x ise bunlarin "cross product" (http://mathworld.wolfram.com/CrossProduct.html) leri.

Yine algoritmanin dogrulugu konusunda sana guvence veremeyecegim.

[myavuzselim]

Ayni soruyu google'a sordum. Ilk yazdigim algoritmanin aynisinin tipkisini verdi. Bu da beni çok ama çok mutlu etti :super: :kuuul:

http://www.alienryderflex.com/polygon/