Find the convex hull of a set of points in C#

convex hull

This example shows how to find the convex hull for a set of points. The details are fairly complicated so I’m not going to show them all here, but the basic ideas are relatively straightforward.

A convex hull is a smallest convex polygon that surrounds a set of points. If you imagine the points as pegs sticking up in a board, then you can think of a convex hull as the shape made by a rubber band wrapped around them all. Some of the points may lie inside the polygon. They are not part of the convex hull.

This program demonstrates several useful techniques for finding convex hulls.

First, the program culls some points out to make finding the convex hull faster. To do this, it finds the points that most closely represent the set’s upper left, upper right, lower left, and lower right corners. It finds the largest rectangle parallel to the X and Y axes that fits within the quadrilateral defined by those points. This rectangle is guaranteed to lie within the convex hull so any point that lies entirely within the rectangle cannot be on the convex hull. That lets the program remove those points from consideration quickly.

Similarly the program finds the quadrilateral defined by those four points and culls any points that lie inside it. It’s harder to determine whether a point lies inside a quadrilateral than inside a rectangle parallel to the X and Y axes, so the program performs the rectangle culling first.

After it has finished culling, the program uses an AngleValue method to order the points. Suppose dx and dy represent the difference between two points. The AngleValue method uses the numeric value dy / (dy + dx) to order the angle from one point to another with respect to the horizontal. This number is not the angle itself, but it has the property that AngleValue(x) < AngleValue(y) if Angle(x) < Angle(y).

The program starts with a point guaranteed to be on the convex hull. For example, the point with the smallest X coordinate or the smallest Y coordinate. Then it begins sweeping around to find the point with the smallest AngleValue. It adds that point to the hull and repeats the sweep from the new point starting with the sweep angle it used in the last test. This process continues until the program finds the start point again. (Basically this lets the program work its way around the convex hull, adding the next point along the polygon at each step.)

To use the program, click several times to select points. Each time you select a point, the program draws the points, highlights those that are culled, draws the culling rectangle and quadrilateral, and draws the convex hull.

Download the example program and look at the code for additional details.

Download Example   Follow me on Twitter   RSS feed

This entry was posted in algorithms, geometry, graphics and tagged , , , , , , , , , , . Bookmark the permalink.

12 Responses to Find the convex hull of a set of points in C#

  1. Find a minimal bounding circle of a set of points in C#

    The example Find the convex hull of a set of points in C# finds the convex hull of a set of points. A convex hull is the smallest polygon that encloses the points. This example extends that result to find a minimal circle enclosing the points. The key is to note that a minimal bounding circle passes through two or three of the convex hull’s points. The following picture shows the two possible scenarios. In the pictures, blue shows the convex hull, red shows a culling trapezoid, and orange shows a culling rectangle, all as …

  2. Pingback: Find a minimal bounding circle of a set of points in C# -

  3. mm says:

    can I ask what method you are exactly using? is it quickhull?

  4. solomon borodkin says:

    I would appreciate any reference to programs in C#, C++, C for getting edge points of multi-dimensional convex hull of finite set of points. I see only planar and 3-dimential cases, but need general n-dimensial case (even not optimal algorithm – any one working).
    Thanks much in advance.

  5. Eric Ouellet says:

    Hi Rod,

    I used your Smallest Enclosing Circle code in my article about Convex Hull ( I would like to add your Convex Hull code as a reference. But I would like to know if you authorize me to do so and what algorithm did you used (Graham Scan, Monotone Chain, …) ?


    • RodStephens says:

      Yes, feel free to refer to these examples.

      This example uses a method somewhat similar to Graham scan but a bit slower and simpler. At each step, Graham scan pick a point to visit next and then later may undo that decision and replace it with some other point. The method used here examines all remaining points and picks the one that makes the next smallest angle. That means Graham scan has runtime O(n log n) but the method used here is O(N2).

      It works well in practice if you don’t have too many points, and that’s true if the culling steps work well. For a random selection of points in an area, that should be true. It would have problems if the points lie near the edge of a circle so most of the points were in the convex hull.

      • Eric Ouellet says:

        Thanks. I already included it as a new algorithm in my benchmark. It is nice because it should help to see the difference in performance related to complexity. My code is actually broken because I’m in a middle of something. I will let you know when I can test and update my article. Just FYI, I’m now using Point from WPF (instead of Winform Point) and I modified Sytem.Drawing.Rectangle to use double instead of int. Also, I use double instead of float and convert List to IList parameters in order to be compatible with my code. I’m sure it will work great. Very big thanks for this code and the Smallest Enclosing Circle which is pretty much the only code I found.

  6. Wayne says:

    Does this function only work in the first quadrant?
    What’s the geometrical meaning of the following method:

    foreach (Point pt in points)
        if (-pt.X - pt.Y > -ul.X - ul.Y) ul = pt;
        if (pt.X - pt.Y > ur.X - ur.Y) ur = pt;
        if (-pt.X + pt.Y > -ll.X + ll.Y) ll = pt;
        if (pt.X + pt.Y > lr.X + lr.Y) lr = pt;
    • RodStephens says:

      That code is finding the upper left, upper right, lower left, and lower right points. Looking at it now, I see that it’s kind of sneaky so I should have said more.

      To get a large culling rectangle, you want the points that are most in those directions, not just the points with the largest and smallest X and Y coordinates. For example, consider the first if statement. It’s considering lines pointed up and to the right at a 45 degree angle and passing through the points. Those lines look like y - y1 = m (x - x1) for a point (x1, y1) on the line.

      Because we’re looking at the upper left corner, the slope m is -1. You would think the slope should be 1, but remember in graphics programming Y coordinates increase from the top to the bottom, so this is switched. (And it makes things more confusing.)

      If we plug in m = -1 and the point (pt.X, pt.Y) for the point (x1, y1) and rearrange a bit, we get y = pt.Y - x + py.X.

      Now the question is, for two points (pt.X, pt.Y) and (ul.X, ul.Y), which line lies above the other. To decide, we can plug in x = 0 and see which equation gives a value for y that puts the line on top. So we compare y = pt.X + pt.Y and y = ul.Y + ul.X. Again we need to flip thing upside down because Y coordinates increase downward, so the line passing through (pt.X, pt.Y) lies above the line passing through (ul.X, ul.Y) if pt.X + pt.Y < ul.Y + ul.X.

      That should be the equation I used, but I must have been thinking about this from another direction because I reversed the signs of the values to get -pt.X - pt.Y > -ul.X - ul.Y. I probably wanted them all to use >.

      So the code loops through the points and uses that equation to find the point that lies on a line with slope -1 that is closest to the top of the picture.

      The other three tests are similar, just with slope 1 for the upper right and lower left corners and the inequalities switched as appropriate.

      I hope that helps.

Comments are closed.