11. Előadás - Grafikai algoritmusok

Konvex burok számítása

Tegyük fel, hogy adott \(n\) számú pont egy vektortérben!

A feladat az, hogy meghatározzuk a ponthalmaz adott részhalmazát, amelyek kifeszítik a teljes ponthalmaz konvex burkát.

A problémát megfogalmazhatjuk úgy is, hogy meg szeretnénk határozni azon minimális elemszámú részhalmazt, amelynek a konvex burka megegyezik az eredeti ponthalmazéval.

QuickHull algoritmus

Feltételezzük, hogy síkbeli pontokról van szó. Az algoritmus működése az alábbi formában foglalható össze.

• Kiválasztunk 2 pontot, amely biztosan a konvex burkon van.

• Húzunk egy ezeken áthaladó egyenest. A problémát ezzel 2 részre bontottuk.

• Meghatározzuk az egyenestől legtávolabb eső pontot (a felosztás során kapott ponthalmazon belül). Ez így szükségszerűen a konvex burkon lesz.

• Ezt a pontot tekintjük a felosztáshoz használt új pontnak.

• Az új ponttal, és az első lépésben kiválasztott pontokkal rekurzív módon elvégezhetjük a felosztást.

• A leállási feltételt az adja, hogy a halmazokból a pontok elfogynak.

Figyelem

A pontok megadási sorrendje számít a felosztásnál, mivel az alapján lehet eldönteni, hogy az egyenes melyik oldalára esnek a pontok!

A munka bonyolultsága hasonló a Gyorsrendezéséhez:

• legrosszabb esetben: \(\mathcal{O}(n^2)\),

• átlagos esetben: \(\mathcal{O}(n \cdot \log n)\).

\(\rhd\) Hogyan oldható meg a ponthalmaz ábrázolása a hatékony implementációhoz?

Kérdések

• Definiálja a konvex burok fogalmát!

Feladatok

• Implementáljuk a QuickHull algoritmust!

• Készítsen hozzájuk konkrét példákat!