Opgave
Gegeven is een verzameling P van punten in het vlak. De convexe omhullende van S is de unieke convexe veelhoek wiens hoekpunten tot P behoren en die alle punten van P omvat.
Implementeer twee algoritmen naar keuze uit onderstaande referenties voor het bepalen van de convexe omhullende van een gegeven verzameling punten.
Schrijf daartoe twee Python-functies convex_hull_a1 en convex_hull_a2 die als parameter de naam van een bestand krijgen, waarin elke regel de x- en y-coördinaat van een punt in het vlak bevat, gescheiden door een spatie. De functie geeft de convexe omhullende terug als een lijst van tuples, waarbij elk tuple de x- en y-coördinaat van een punt bevat; de lijst begint met het meest linkse punt (met de kleinste x-coördinaat). Coördinaten zijn gegeven als float-getallen met 8 cijfers na de komma.
Voorbeeld
In onderstaand voorbeeld veronderstellen we dat het bestand test01.txt1 zich in de huidige directory bevindt.
>>> convex_hull_a1("test01.txt")
[(0.04580177,0.50247438), (0.22893588,0.85947702), (0.53970795,0.94760802),
(0.65911670,0.97167685), (0.79112422,0.97933185), (0.95936494,0.82389217),
(0.99420332,0.51532700), (0.98767487,0.04874969), (0.76717602,0.02106570),
(0.20726929,0.03690879), (0.05741439,0.17911533), (0.04580177,0.50247438)]
Referenties
- Thomas Cormen, et al., “Introduction to Algorithms”, MIT Press, 2009 (hoofdstuk 33).
- Mark de Berg, et al., “Computational Geometry: Algorithms and Applications”, Springer, 2008 (hoofdstuk 1).
- Graham scan2
- Gift wrapping algorithm3
- QuickHull4