Fülvágó Algoritmus

Egy félév algoritmus elmélet után senki nem illetődhet meg miatta. Elvégre a legegyszerűbb algoritmus egy sokszög három szögekre bontására. Bőven polinom idejű hiszen az általam megírt biztosan nem a legoptimálisabb megoldás is egy másodperc alatt többször lefutott akár több száz csúcsú sokszögeken is. :D

A konkrét algoritmus pár szóban elmondható, a megértése lehet más kérdés.
Szóval a kiindulásként kiválasztjuk a sokszög egy csúcsát, és a mellette lévő két másikat össze kötjük egy szakasszal. Ha ez a szakasz nem metszi a sokszög egy másik oldalát sem akkor a három pont nagy valószínűséggel egy fület alkot, de hogy ez mégse legyen ennyire egyszerű meg kell vizsgálni ez a szakasz a sokszögön belül vagy kívül van. (Ezt nagyon egyszerűen meg tudhatjuk, ha valahonnan a szakaszról elindítunk egy egyenest a végtelenbe és össze számoljuk hányszor metszette a sokszög oldalait. Ha páros számúszor (a 0 is páros) akkor külső, ha páratlan számúszor akkor belső.) Értelem szerűen, ha ez nem a sokszögön belül van akkor nem lehet fül.
Végső lépésben, ha eldöntöttük egy háromszögről, hogy az fül vagy sem, levágjuk a fület (innen a név ^^) vagy tovább lépünk egy következő csúcsra.
Mindenféle tételek, két fül tétel, vagy valami hasonló kimondja, hogy bármilyen sokszögnek van legalább két füle (kivéve persze a háromszög ami önmagában egy nagy fül. :)), tehát az algoritmus véget ér, ha egy háromszögünk marad. Nahát, nálam az elején nem mindig ért véget, sőt…
Aki kicsit vizuálisabb, annak ez biztos sokat segít a megértésben:

Ami meg ihlette a bejegyzést, természetesen az, hogy már egy hete ezzel szívok itt éjszakánként. És ez még csak második házi feladat volt az ötből. Ergo a második legkönnyebb. Persze nem csak fülvágó algoritmust kellett megvalósítani, és tulajdonképpen azzal a láncolt listával szívtam a legtöbbet amiben a csúcsokat, tároltam, mivel a minta kódhoz nem lehetett includolni újabb könyvtárakat.

A konkrét feladat egy szép kis történetbe volt ágyazva szivárványszínű  balettozó görbe lányokról: Placcs Bereniké, Placcs Cezarina és Placcs Nikodémia, de lényegében három görbét kellet tesszellálni, azt felbontani háromszögekre és a szivárvány spektrumát rá illeszteni, kiegészítve pár aprósággal. A megoldásom egy pillanat képe (bár nincs animálva, csak gombnyomásra és kattintásra történik valami, kicsit túlzás a pillanat :)).
Remélem erre is megkapom a “A feltöltött program a specifikációnak megfelelően fut.” értékelést.

A bezier görbe “csaj” nem a legszebb, de hát emiatt olyan nagy szó a lokális vezérelhetőség. :P És a “görbék” ekkora felbontással is elérték a 200 kontroll pontot pontot, és azokon kellett füleket vágni, egérkattintást vizsgálni stb.
Ezek után kicsit furcsán nézek azokra akik fennakadnak, ha egy game meg-megakad néha egy pillanatra. És szerintem még furcsábban fogok a következő házi után, ami már 3D-ben lesz!

Advertisements
Kategória: Egyetem, Informatika, Napló
Címke: , , , ,
Közvetlen link a könyvjelzőhöz.

4 hozzászólás a(z) Fülvágó Algoritmus bejegyzéshez

  1. keeroy szerint:

    Szép leírás. A harmadik és azutáni házikhoz viszont érdemes alaposan felkötni a nadrágot. :)

    • kdanni szerint:

      Kösz, már előre is félek mert most nem lesz egy ZH mentes hetem, mint legutóbb. :)

      És most nézem 39 kereső találat, és 79 megtekintés volt egy nap alatt a bejegyzésre. Sokan hagyhatták az utolsó pillanatra a dolgot.

  2. johny szerint:

    Keeroy:
    probálj vmi egyszerübbet kitalálni a népnek ;)

  3. kdanni szerint:

    Úgy néz ki ebben az évben is a fülvágó algoritmust kellett felhasználni a grafika házikhoz a bme info-szakának grafika kurzusán. :)

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s