A legtöbb helyen két módszert említenek. (A) "metszések száma" /crossing number/; (B) "kanyargási szám" /winding number/. Inclusion of a point in a polygon
Az (A) azt csinálja, hogy húz egy egyenest a ponton át, és megnézi ennek az egyenesnek és a tartományt határoló szakaszoknak az összes metszéspontját. Ezeket a metszéspontokat rendezi, és azt feltételezi, hogy ha nem történt valami baj, akkor a metszéspontok felváltva jelzik, hogy beléptünk a tartományba, majd kiléptünk belőle. Tehát ez a konkáv tartományokra is működik. Ha a pontunk előtt páratlan sok metszéspont van az egyenesen (valamelyik irányból), akkor bent vagyunk, ha páros, akkor kint.
A gyakorlati megvalósításkor sok-sok nehézséggel szembesülünk.
1. Ha az egyenes átmegy a tartomány egy csúcsán, akkor azt két metszéspontnak hihetjük (a két szomszédos szakaszon egy-egy.)
2. Ha az egyenesre esik valamelyik határ szakasz, akkor ott végtelen sok közös pont van, és nem léptünk se be se ki.
3. Nem mindegy, hogy valós vagy egész aritmetikát alkalmazunk, mert egy egyenes és egy szakasz, illetve a pont és valamelyik szakasz nagyon közel eshet egymáshoz. Valós aritmetikát használva baj lehet a kerekítési hibákból, egész aritmetikánál pedig hatalmasra nőhetnek a nevezők és a számlálók, azért nem elegendők a programozási nyelvek beépített típusai. Ha az egész probléma eredete grafikai, és csak a képernyőn akarjuk pontokról eldönteni, hogy egy képernyőre rajzolt pixel egy képernyőre rajzolt tartományhoz képest hol van, akkor kevésbé kell félni a numerikus dolgoktól, mert a pixel méreténél kisebb hibák úgysem fognak látszani.
A (B) azon alapul, hogy megszámolja, hányszor kerüli meg a poligon a pontot. Akkor van kívül egy pont, ha nullaszor. Valahogy úgy megy a számolás, hogy a körüljárás szerint sorra vesszük a tartományt határoló szakaszokat, és mindegyikre kiszámoljuk, mekkora szögben látszik (irányított szakasz, irányított szög) a pontból. Külső pontra az előjeles szögek összege nulla, ez szemléletesen látszik konvex tartomány esetén.
Itt meg az a gond, hogy rengeteg inverz trigonometrikus függvényhívást csinálunk, ami lassú és ott is lehetnek kerekítési problémák.
Ha vannak konkrét bemenő adataid (amik nem titkosak), az érdekelne, mert ehhez a problémához nem egyszerű jó tesztadatokat gyártani.
|