A HLint érdekes kis program. Kiszúrta például, hogy a "foldl1 (&&)" helyett írhatnék simán "and"-et is. A posztok javítva vannak.
Az előző posztban megígértem, hogy megértjük az isPointInPolygon függvényt. Nézzük.
-- Ha egy polygon pontjait az óramutató járásával ellentétes
-- irányban haladva adjuk meg, akkor annyit kell megnézni,
-- hogy az adott pont minden vonal bal oldalán van-e. Ha
-- igen, a polygonon belül van a pont, különben kívül.
-- (Kicsire nem adunk, ha rajta van, kívül van, kész.)
isPointInPolygon :: Position -> Polygon -> Bool
isPointInPolygon p ps =
and (map (\x -> onLeft (ps !! x)
(ps !! ((x + 1) `mod` psn))
p)
[0..psn-1])
where
psn = length ps
Egy C pontról meg tudjuk állapítani, hogy egy AB vonal bal oldalán van-e (onLeft a b c). Fel tudjuk-e ezt használni ahhoz, hogy egy pontról eldönthessük, benne van-e egy polygonban? Egyértelmű, hogy ha a polygon minden oldalától balra van, és az oldalak CCW irányban vannak megadva, akkor a pont a polygonon belül van. Első lépésben döntsük el minden oldalra, hogy a pont attól jobbra, vagy balra van-e! Ehhez kelleni fog a map, ami fog egy függvényt és egy tömböt, majd a tömb minden elemére alkalmazza a függvényt, és visszatér ezzel az új tömbbel. Típusa a haskellerek kedvéért:
map :: (a -> b) -> [a] -> [b]
Ehhez ugyebár kelleni fog az onLeft, és a map. Van egy tömbünk a polygon pontjairól, sorrendben. Mindig összefogjuk az éppen aktuálisat az utána következővel, és ez lesz az a vonal, amihez hasonlítjuk a pontot. Na de ha van egy pontunk, honnan tudjuk, hogy melyik a következő pont, anélkül, hogy ismernénk a tömböt? Nos, sehogy. Épp ezért én úgy oldottam meg, hogy nem pontokra alkalmaztam a map-et, hanem indexekre. Nézzük:
boolArray polygon point =
map (\index -> onLeft (polygon !! index)
(polygon !! (index + 1) point)
[0..length polygon - 1]
a (polygon !! index) elkéri az index-edik elemet a polygon tömbből. A map utáni és a [0..] előtti rész egy úgynevezett lambda függvény, ami azt jelenti, hogy nem adunk meg neki nevet, hanem csak simán definiáljuk. a \ jel (ami a lambda lenne, csak azt nehéz m,egtalálni a billentyűzeten, úgyhogy ezt választották, mert eléggé hasonlít hozzá) után jönnek a paraméterek, majd egy nyíl után a definíció maga. A probléma viszont, hogy az utolsó elemnél az utolsó utánira is szükségünk lenne, ami viszont out-of-boundary error. De igazából ott nekünk az első elem kellene, mivel ugye a polygon önmagába tér vissza. Erre van egy ügyes kis trükk, a maradékos osztás, vagy mod. Ezt nem magyarázom el, tele van vele a gugli. Viszont ha az index + 1 részt maradékosan osztjuk a hosszal, akkor az első olyan index, ami a hosszon kívül lenne, pontosan 1 lesz. Vagyis, amire szükségünk van :D A módosított verzió:
boolArray polygon point =
map (\index -> onLeft (polygon !! index)
(polygon !! ((index + 1) `mod`
(length polygon)) point)
[0..length polygon - 1]
Na, most hogy van egy tömbünk Bool értékekkel, ideje lenne őket kiértékelni. Minden bool azt mutatja, hogy az adott szakasztól jobbra vagy balra van-e a pontunk. Ugyebár akkor van a polygonban, ha minden szakasztól balra van, tehát minden True. Ezt úgy lehet a legjobban megoldani, hogy && operátorral "összeéseljük" őket. Erre van kitalálva a foldl1 (foldl, foldl', foldl1, foldr, foldr1, stb...), ami megkap egy operátort, meg egy tömböt, aztán fogja az első két elemet, applikálja rájuk az operátort, majd az eredményre és a harmadik elemre is, majd ennek az eredményére és a negyedikre is stb. (Ez a foldl - az l a leftből van. A foldr jobbról megy végig a listán. Vannak esetek, amikor ez a célravezetőbb.) Nyilván az üres tömbre hibát fog adni. Pedáns olvasóknak:
foldl1 :: (a -> a -> a) -> [a] -> a
Megvan minden, ami kell. A fentebb megírt boolArrayra használva így néz ki:
result = foldl1 (&&) boolArray
Persze erre a HLint kiböki, hogy "foldl1 (&&)" helyett talán olvashatóbb lenne, ha "and"-et használnánk, így a kód:
result = and boolArray
Ezekután pár szépítgetés után el is juthatunk a fent látott isPointInPolygonhoz. Köszöntem a figyelmet.
