Convex Hulls
Example of how to compute a convex hull The function list<POINT> CONVEX_HULL(const list<POINT>& L)computes the convex hull of the points in L and returns its
list of vertices. The cyclic
order of the vertices in the result corresponds to the counter-clockwise
order of the vertices on the hull. We use the notation POINT to indicate that the algorithm works
both for points and rat_points . See also Writing
Kernel Independent Code.
Alternative Algorithms for Convex HullLEDA provides three different algorithms for computing the convex hull of a point set
The randomized incremental construction is the default algorithm for convex hull. It is generally faster in practice than incremental construction. It is also faster than the sweep algorithm if there are only few hull vertices. If the input points are on the unit circle the sweep algorithm is faster. More details can be found in the LEDA Book. Convex Hulls in 3DThe function void CONVEX_HULL(list<d3_rat_point> L, GRAPH<d3_rat_point,int>& H) takes as argument a Running Time: |
See also:Writing Kernel Independent Code Manual EntriesManual Page of Geometry Algorithms Manual Page 3D Convex Hull Algorithms |