POINT-IN-POLYGON probléma
Megpróbálom középiskolás szinten elmondani. Ábrázoló geometriára csak emléxünk... ;-)
Egy pont helyét két dimenziós koordináta-rendszerben (x,y) formában írjuk le.
Egy egyenes leírásához két ilyen pont elegendő
Egy felület határvonalait pontok sorozatával írjuk le; az elsô és utolsó pont egybeesik, vagy mondhatjuk úgy - bezárul.
Vannak mindenféle képletek, ugye... két pont távolsága, két egyenes metszéspontja... Dereng valami? Ennyi elég is. Nem is kell több. Nem is kell megnézni a képleteket. Bonyik :-|
Kérdés: Hogy lehet megállapítani egy pontról, hogy egy felületen belül vagy kívül van?
Megoldás: Húzzunk a pontunktól egy egyenest bármilyen irányba hosszabban, amennyire a felület legtávolabbi pontja van pontunktól és ujjainkon számoljuk, a vonalunk hányszor metszi a felület határvonalát.
Lássuk be, ha egyszer sem, akkor a pont a felületen kívül van. Ezt nem lehet ragozni. Ez van.
Lássuk be azt is, ha a pontunkból húzott vonalunk a felületnek csak egy határvonalát metszi, akkor a pontunk a felületen belül van. És ha két határvonalat metsz, akkor kívül van. És ezt ragozzuk tovább...
Ha három határvonalat metszünk, akkor a pontunk belül van, ha négyet, akkor kívül, ha ötöt, hetet, kilencet stb akkor belül, ha hatot, nyolcat, tizet stb, akkor kívül; végül is, ha a metszéspontok száma páratlan, akkor a pontunk a felületen belül, különben kívül van.
Ennyi.
Programozástechnikailag a feladat egyik lehetséges megoldása:
(1) Meghatározzuk a pontunk és a felület legtávolabbi határpontjának a távolságát (két pont távolságának függvényével az algoritmus kiszámolja a felület összes határpontjának távolságát pontunktól és veszi a legnagyobb értéket)
(2) A pontunkból képzünk egy másik pontot, amely az elébb meghatározott távolságra van minimum, azaz létrehozunk egy hosszabb egyenest. Iránya érdektelen :-)
(3) Az algoritmus két egyenes metszéspontjának függvényével meghatározza, ez az egyenes a felület határpontjait összekötő egyenesek közül hányat metsz.
(4) Ha a metszések száma páratlan, a pontunk a felületen belül van, különben kívül.
(Programozó matematikusaim! Persze, a mélyvízben nem ennyire egyszerû, de nagyjából ez a lényeg) |
