A probléma a következő: adott egy konvex polygon. Keressük meg az ebbe írható legnagyobb ortogonális téglalapot (tehát a téglalap oldalai legyenek párhuzamosak az x és y tengellyel). (Ez ahhoz kell, hogy a telkekre házat tudjak rakni.)
Van is itt egy megoldás:
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Namármost, normális ember nem posztol bejegyzést arról, hogy talált egy linket. A probléma, hogy nem bírom felfogni, hogy hogy is kellene ezt lekódolni. Úgyhogy gondolkodtam.
Nem feltétlenül kell nekünk a lehető legnagyobb beírható téglalap. Elég az is, ha "elég nagy", tehát goodenough solution-t is elfogadunk. Ez viszont elég nagy könnyebséget jelent, ráadásul a kódot le is csökkenti mindösszesen 66 sorra (Haskellben).
A megoldásom menete vázlatosan:
Számoljuk ki, hol lehet kb-ra P középpontja, nevezzük mondjuk X-nek. (Ezt úgy számoltam ki, hogy vettem az összes pont átlagát.) Majd vegyük adottnak, hogy a kvázi-legnagyobb téglalap tartalmazza ezt a pontot. (Szerintem elég józan feltételezés.) Tovább egyszerűsíthetjük a problémát, ha a téglalapok koordinátái csak bizonyos pontokon lehetnek, pl egy E távolságra levő függőleges és vízszintes vonalak metszéspontjain. (A képen ezekre utalnak a tengelyeken elhelyezkedő beosztások.) Ezután vegyük az összes olyan téglalapot, aminek bal oldala X-től balra, jobb oldala X-től jobbra van, a teteje X fölött, az alja pedig X alatt. (A képen kékkel egy elfogadható, pirossal egy elfogadhatatlan téglalapot látunk.) Ezekből szűrjük ki azokat, amik nincsenek benne teljesen P-ben (a képen pirossal jelölve), amit úgy tehetünk meg, hogy a téglalap sarokpontjaira ráeresztünk egy "benne van-e a polygonban?" ellenőrzést. (Konvex polygonra igaz az, hogy ha egy téglalap minden sarokpontja benne van a polygonban, akkor a téglalap összes pontja is.) A maradék téglalapok közül megkeressük azt, amelyiknek maximális a területe, és meg is vagyunk.
Jól hangzik, lássuk hát gyakorlatban.
type Position = (Float, Float)
type Polygon = [Position]
-- Megmondja egy pontról és egy egyenesről, hogy a pont az
-- egyenes bal oldalán van-e.
onLeft :: Position -> Position -> Position -> Bool
onLeft (ax, ay) (bx, by) (cx, cy) =
(bx - ax) * (cy - ay) - (cx - ax) * (by - ay) > 0
-- 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 polygon pontjaiból kiszámolja a polygon kvázi-közepét.
centerOf :: Polygon -> Position
centerOf poly = (x, y)
where
xs = fst . unzip $ poly
ys = snd . unzip $ poly
x = sum xs / fromIntegral (length xs)
y = sum ys / fromIntegral (length ys)
Akkor nézzük, hogyan is működik a fenti kód. Az onLeft-et nem részletezem, a paraméterek érthetőek, a kódot meg én sem értem. :D A centerOf már izgalmasabb: az
xs = fst . unzip $ poly
sor mit is csinál? A $ jelről anyit, hogy az tulajdonképpen nem csinál semmit, csak zárójelet szoktunk spórolni vele. Írhatnánk így is:
xs = (fst . unzip) poly
Tudjuk, hogy a poly adattípusa [Position], vagyis [(Float, Float)], tehát olyan tömb, aminek az elemei 2-tuple-k. az unzip típusa:
unzip :: [(a, b)] -> ([a], [b])
vagyis egy 2-tuple-kből álló tömb helyett lesz egy tömbökből álló 2-tuple-nk. Izgalmasan hangzik. Jelen esetben ez azt jelenti, hogy az unzip poly egy olyan 2-tuple-t ad eredményül, aminek első eleme az x értékek tömbje, a második pedig az y értékeké. És ha erre alkalmazunk egy fst-t:
fst (unzip poly)
akkor meg is kaptuk az összes x-et tartalmazó tömböt. De álljunk csak meg. Miért van akkor olyan furán írva?
Nos, vizsgáljuk meg a . operátor típusát:
(.) :: (b -> c) -> (a -> b) -> (a -> c)
tehát két függvényt applikál. (Operátorokat zárójelek közé illik írni.) Igazából semmi okom nem volt rá, hogy így megbonyolítsam, de épp így tartotta kedvem, és gondoltam, akkor már beszélek is egy kicsit erről a két operátorról. Magyarul az xs és ys tárolja az x és y koordináták tömbjeit. A
sum xs / fromIntegral (length xs)
sor pedig annyit csinál, hogy összeadja xs elemeit, majd elosztja az összes elem számával (amit fromIntegral-lal intből racionálisba alakítunk, hogy lehessen vele osztani).Innentől szerintem érthető.
A következő részben az isPointInPolygon is meg lesz magyarázva.
