So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm would define a pentagon around a five-point star and call that the convex hull, but if I wanted to identify the shape as a five-pointed star that would be insufficient.

How then could I tell the computer to define a polygon that may be concave, which would contain all the points in Q and has nonzero area, but would minimize areas bounded by the shape in which there are no points from Q?

I'm thinking a simple tweak of the Graham Scan to allow right turns, but that would instead not allow lines to cross, might do it, but that's just a wild shot in the dark which I haven't tried. I'm also thinking that, given the normal application of this in computers (image pattern recognition), that I would also have a set of points R that should NOT be contained in the polygon, and after finding the "convex hull" of the points Q I can then run a variation of the algorithm that adds "right turns" at points that should lie outside the shape but currently are contained within.

So first define the subset H that define the convex hull of a set of points Q. Now, take each point X from a set R of points that must not be contained in the final polygon. Determine if that point lies within the polygon (it does if a line from any point in Q to X intersects zero or an even number of line segments defining the current polygon). If so, insert X into H between the two adjacent points M and N in H that have the lowest mean distance from X. Then, for all P in Q that are not in H, if P now lies outside the shape defined by H, add P to H between either M and X, or X and N, depending on which two points have the lowest mean distance. Repeat for all X in R.

Are there any proven algorithms that would accomplish this (and be less complex than O(N^2logN) given that Q and R are roughly equal in cardinality)?

  • $\begingroup$ The concave hull of a polygonal domain would be the polygonal domain itself after your definition of concave hull, so there is no new mathematical object. $\endgroup$ – Beni Bogosel Apr 10 '12 at 22:38
  • $\begingroup$ OK, yes, a line connecting all dots in order without crossing over itself would be a "convex hull"; however, it would have zero area. So, the shape I'm looking for must have nonzero area. We can also state that no point may occur twice in the list of vertices produced by traversing the perimeter of the shape in one direction. $\endgroup$ – KeithS Apr 10 '12 at 22:46
  • $\begingroup$ If you have a finite set of points $Q$ then there are polygons with vertices in $Q$ with area arbitrarily small. $\endgroup$ – Beni Bogosel Apr 10 '12 at 22:51
  • $\begingroup$ Is minimum area really what you want? Perhaps a curve reconstruction algorithm would be better? $\endgroup$ – Rahul Apr 10 '12 at 23:34

You might get something like what you want using an optimization approach. Start with the convex hull, then test the points not on the hull to see if they can be added to the polygon between a pair of vertices. The decision is made 1) it is absolutely prohibited to make a polygon that has points outside it. 2) add the point if the area of the polygon decreases enough to pay for the increase in perimeter. 3) don't let the sides of the polygon get too noisy-maybe point 2 will take care of this. Keep trying to add new points until you can't find one to put in. You'll have to play with the weighting between area reduction and perimeter increase.


You may want to try Alpha Shapes though they're not designed to minimize area.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.