Computes the 2d convex hull of a planar point set.

Namespace:  ceometric.ComputationalGeometry
Assembly:  ceometric.ComputationalGeometry (in ceometric.ComputationalGeometry.dll) Version: (


public class ConvexHull2d
Visual Basic (Declaration)
Public Class ConvexHull2d
Visual C++
public ref class ConvexHull2d


The convex hull of a set P of n points is a convex polytope whose vertices are points in P. This is, all points of a set of points lie within the convex hull or on its boundary. A 2d convex hull is the convex hull of the projection of the point set onto the XY-plane. This class computes the 2d convex hull of n points in O(n * log(n)) time. Exact arithmetic provides ultimate robustness. Collinear boundary edges are not merged.


// instantiate a 2d convex hull
ConvexHull2d hull2d = new ConvexHull2d();
// assign the points for which to find the hull
hull2d.InitialPoints = SamplePoints.RandomInRectangle(10000, 1, 1);
// compute the hull
// output some interesting properties
Console.WriteLine("Number of vertices: " + hull2d.Vertices.Count);
Console.WriteLine("Area of hull      : " + hull2d.AreaXY);
// Visualize the hull
Scene sc = new Scene();
sc.Add(hull2d.InitialPoints, "Points", 1); // Add the initial points on a red layer "Points"
sc.Add(hull2d.Edges, "Hull", 2);           // Add the hull edges on a yellow layer "Hull"

Inheritance Hierarchy


See Also