Bir noktanın bir alan içinde olup olmaması

[DoganBir]

Bir noktanın önceden sınırları tanımlanmış bir alan içinde olup olmadığını anlamak için kullanılan bir algoritma arıyorum. basit olması gerekiyor, karekök alma gibi işlemler olmamalı. veya 2 çizginin birbirini kesip kesmediğini anlayacağım bir algoritma da olabilir.

[mentat]

nokta poligon testi için yöntemlerden birisi: poligonun dışında olduğundan emin olduğun bir nokta al ve test edeceğin noktayla bunu birleştir. çıkan doğru parçasını poligon ile kesiştir, kesişme sayısı tek ise nokta poligonun içinde, çift ise dışındadır.

ikinci bir yöntem de, noktandan poligonun köşelerine doğrular çek. doğrular arasındaki açıların toplamı 360 ise içerde, değilse dışarıdadır noktan.

aklıma gelenler bunlar. netten point in polygon falan diye aratabilirsin, gamedev'de de olacaktı birkaç yazı konuyla ilgili..

[lucifer]

Bir suru yontem var, ne icin kullandigina gore degisir. 2D mi 3D mi diye sorsam mesela, alanlar basit ucgen/dikdortgenler mi yoksa abuk subuk sekiller olabiliyor mu...

[DoganBir]

2D olacak. Mentat ın söylediği ilk yöntemi kullanmayı düşünüyorduk ama daha kolay ve bizi yer ve hız açısından daha az zorlayacak bir algoritma varmıdır diye araştırma yapıyorum. Şekil abuk subuk bir çokgende olabilir.

[lucifer]

2d abuk subuk cokgenler icin Mentat'in ilk metodu en iyisi.

Mentat'in ikinci metodu yuvarlama hatalari sebebiyle hafif hatali sonuc verebiliyor bazen.. hafif hatali dedigim, noktamiz poligon'un koselerinden birine yakinsa icerideyken disarida, disaridayken iceride diyebiliyor.

Mentat'in ucuncu yontemi var bir de, ama sadece poligon convex ise ise yariyor. Poligon'un bir kenarindan basliyorsun. Nokta o kenarin hangi tarafinda diye bakiyorsun, sonra sirayla diger kenarlara da bakiyorsun. Eger nokta hep ayni tarafta ise (hep sag ya da hep sol) o zaman iceridedir. Bu benim en sevdigim yontem ama poligon konveks ise ise yariyor sadece.

[amator]

Mentat'in ilk verdigi algoritma ile ilgili: http://www.alienryderflex.com/polygon/

Eger test edecegin poligon sabit ise, ve de cok abuk subuk birsey degilse bu poligonu parcalara ayirip lucifer'in soyledigi son metod'u da deneyebilirsin. P'nin AB'nin hangi tarafinda oldugunu PA x PB'nin z koordinatinin isaretiyle bulman lazim. (x = crossproduct)

[Ziyaretci]

Eğer bir şekilde poligon un içindeki ve dışındaki renkleri gruplama ihtimalin varsa, gayet hızlı bi yöntem bulunabilir. (Mesela, polygon içindekilerin renklerinin son bitleri 0 dır diğerlerinin değildir vs. şeklinde)

bu durumda direk renk kontrolü işini görebilir. yada, biraz daha kasıp, RGB lerin lowest bitlerini kullanırsan, bunu 8 poligonu gösterecek biçimde de kullanabilirsin. (ancak ışık, sis vs. efekt yapacaksan tabii bu dediklerim bir işine yaramaz.)

yada, diğer Alpha vs. bufferları kullanmayı deneyebilirsin.

yada, depth buffer için Write i TRUE, test i FALSE yaparsan, depth buffer bilgisi de yardımcı olabilir.

eğer bunlar uygulanabilir değilse, mentat ın dediği yöntemle yapman gerek gibi duruyor.

kolay gelsin.

[DataDump]

(255, 0, 255) gibi zit bir renk ile fillPolygon yap. Istedigin noktanin rgb degeri polygon ile ayni ise nokta polygonun icindedir demektir.

[DoganBir]

şimdilik ilk yöntemi kullanıyorum. Fonksiyona sadece koordinatlar geliyor ve benim bu koordinatları kullanabilme şansım var. Boyutunun çok küçük olması gerekiyor çünkü hafıza sorunumuz var. İlk yöntemden daha az yer kaplayacak bir algoritma arıyorum. Polygon önceden tanımlanmış olacak ama abuk subuk olabilme ihtimali var. Bu yüzden sonradan sorun çıkarmayacak bir algoritmaya ihtiyacım var.
Yardımlarınız içinde teşekkür ederim.
İhtiyacı olan olursa şimdilik kullandığım yöntem
http://www.informatik.uni-oldenburg.de/~trebla/graphic/

[DataDump]

Bunu ne icin kullanacaksaniz? Dusuk hafiza dedigine gore mobil bir cihaz yada set-top-box sanirim.

[DoganBir]

mikrokontroller içine yazılcak bu kod. Ve hafızanın büyük kısmı zaten dolmuş durumda

[devreci]

o zaman elinde 4 işlemden başka bişey yok. Eğer 2d ise her noktanın bağlı olduğu diğer noktadan çıkarıp x/y yap ondan sonra kontrol noktasından aynı noktayı çıkarıp x/y yapıp kıyaslama yap . tabi bu arada noktanı sağında mı solundamı ,yukarı aşağı kontrolku yapılması lazım
yani birde poligonun orta noktası bilinecek. tabi bu yamuk yumuk kenar sayısı belli olmayan uygulamalar için üçgen için daha kolay yönt var