Az algoritmusok

A ponthalmaz konvex burkát síkban és térben kiszámító algoritmusok csak részben illeszkednek a Preparata-Shamos könyvben leírtakhoz. Ennek az az oka, hogy az algoritmus elkészítése során néhány hiányosságra derült fény. 
A javasolt módszer áttanulmányozása után látszott, hogy az algoritmus hatékonyságáért annak bonyolultságával kell fizetni. Ez még nem okozott volna problémát, de voltak hibás részeljárások (például Graham-féle scan, ami a maga nyolc sorával sem mûködik), és kidolgozatlan részek. 
A rekurzív algoritmus fô része két ponthalmaz által meghatározott konvex burok összefuttatását jelentette egy konvex burokká. Ennek kezdeti lépéseként a két ponthalmaz síkbeli konvex burkát is meg kellett határozni, amirôl az algoritmus említést sem tett. A síkbeli konvex burok elôállítását végzô osztály ezzel a céllal készült. 
Következô problémát az jelentette, hogy a két burok összefuttatásakor keletkeznek belsô csúcsok és élek, amelyek közül az algoritmus csak a palást építésében résztvevô csúcsokat dobja el, a belsôket nem. 
Ezen a ponton felhagytam az algoritmus további implementálásával, mivel további problémákat is láttam, melyek lassan oda fajultak, hogy az algoritmust teljesen nekem kell kitalálnom. A feladat megoldásához kitaláltam egy kevésbé hatékony, de könnyen érthetô térbeli algoritmust, ami láthatóan mûködik, és elôállítása még a félkész algoritmushoz képest is kevesebb veszôdséggel járt. 

Ponthalmaz konvex burkának kiszámítása két dimenzióban

Ez a síkbeli konvexburok eljárás hasonlít a Preparata-Shamos-ban leírtakhoz, de nem mûködik három dimenzióban.  Elsôdleges célja az lett volna, hogy a háromdimenziós eljárás részét képezze. 
Az algoritmus rekurzív,  egy lépésben mindig a ponthalmaz két részhalmazához elôállított konvex burokból képez egyet, mely az egész halmaz burkát alkotja. 
Az algoritmus elsô lépésként a kapott ponthalmazt rendezi x koordináta szerint. Erre azért van szükség, hogy az összefuttatásra kerülô halmazok ne fedhessék át egymást. A  fô eljárás a kapott ponthalmazhoz konvex burkot hoz létre. A z eljárás a halmazt elôször számosság szempontjából vizsgálja. Négynél több pont esetén a ponthalmazt elfelezi, páratlan számnál az elsô részbe kerül több pont. A  két részhalmazzal rekurzívan meghívja önmagát, végül a visszakapott részburkokat összefuttatja. Négynél kevesebb pont esetén a konvex burok egyértelmû, minden pont benne van. Négy pontnál a rekurzív híváshoz képzett elsô vektor három, a második egy elemû. 
A  lényegi munkát az összefuttató eljárás végzi. Az elsô feladat a két konvex burokban található pontok rendezése oly módon, hogy egy közös belsô  pont körül fix körüljárással felsorolhatók legyenek. Erre az állapotra alkalmazva a Graham-féle scan javított változatát az egy körüljárással kiszûri a burok részét nem képezô pontokat. 
Az összefuttatott burok elôállításához meg kell határozni az elsô halmaz egy belsô pontját. Erre a három elsô pont által alkotott háromszög súlypontja megfelel.  Ezek után meghatározható a másik buroknak az a két pontja, melyekhez a belsô pontból húzott egyenes nem metszi a másik burok határát. Ez a két pont a második burkot két csoportra bontja, melyek közül az elsô burok felé nézô halmaz biztosan nem része az elôállítandó buroknak, így elhagyható. Az elsô  burokból és a második burok maradék részébô l képezni kell egy poligont, aminek szomszédos csúcsai a belsô pont körül felsorolhatók fix körüljárással.  Ez a poligon kerül átadásra a Graham-féle scan-nek, ami egy tetszôleges pontból kiindulva körbejárja a halmazt és visszalépéses módon eldobja azokat a pontokat, amelyek nem elemei a konvex buroknak.     

Ponthalmaz konvex burkának kiszámítása három dimenzióban

A térbeli burok kiszámítása lényegesen eltér a síkbeli megoldástól. 
Itt a feladat olyan háromszögek megtalálása, melyeknek csak egyik oldalán találhatók pontok a halmazból. Az ilyen tulajdonságú háromszögek nyilvánvalóan a burok részét alkotják. Mivel a pontok koordinátái dupla pontosságú számok, ezért annak a valószínûsége, hogy négy vagy több pont is egy síkba esik minimális. 
Az algoritmus kezdeti lépéseként a legnagyobb x koordinátájú pont meghatározása történik, ez a pont biztosan része a buroknak. Ezek után egy kettôs ciklusban a halmazból pontpárokat kell hozzá kiválasztani és megnézni, hogy az így kialakult háromszögnek csak az egyik oldalán vannak-e pontok. Ha ez teljesül, akkor a burok kezdô háromszöge megvan, a megtalált élek és a megtalált háromszögek egy-egy vektorba kerülnek a késôbbi használathoz. 
Ezek után az algoritmus további ciklikus futása során az éleket alkotó vektorból mindig egy újabb kerül kiválasztásra, melyhez a ponthalmazból egy harmadik pontot kell keresni, és megnézni, hogy ez a háromszög a burok része-e. Ha igen, akkor az élek és a háromszög bekerül a neki megfelelô vektorba. 
Ha egy olyan él lesz kiválasztva, amelynek már mindkét oldalán meg lett határozva a burkot alkotó háromszög, akkor az él kikerül az élvektorból. Mivel véges ponthalmazról van szó, ezért ez a vektor elôbb-utóbb kiürül, a burok bezárul. 
Az eljárás befejeztével a visszatérô érték egy a háromszögekhez tartozó oldaléleket tartalmazó vektor lesz, melyet a kirajzoló osztály tud felhasználni. 
Lényeges elem még az eljárás megértéséhez, hogy az algoritmus miként számítja ki mikor van egy pont egy háromszög egyik oldalán. Ehhez meg kell határozni a háromszöget alkotó síkot a normálvektorával megadva, majd a normálvektor segítségével elôjelesen meg lehet határozni egy tetszôleges pont távolságát a síktól. Így csupán azt kell figyelni, hogy következik-e be elôjelváltás a keresés közben, mert ha igen, akkor a háromszög nem része a konvex buroknak, és új pontokat kell keresni.