Fast algorithm for calculating union of 'local convex hulls'

3
votes

I have a set of 2D points from which I want to generate a polygon (or collection of polygons) outlining the 'shape' of those points, using the following concept:

For each point in the set, calculate the convex hull of all points within radius R of that point. After doing this for each point, take the union of these convex hulls to produce the final shape.

A brute force approach of actually constructing all these convex hulls is something like O(N^2 + R^2 log R). Is there a known, more efficient algorithm to produce the same result? Or perhaps a different way of expressing the problem?

Note: I am aware of alpha shapes, they are different; I am looking for an algorithm to perform what is described above.

The following solution does not work - disproved experimentally in MATLAB.

Update: I have a proposed solution.

Proposition: take the Delaunay Triangulation of the set of points, remove all triangles having circumradius greater than R. Then take the union of the remaining triangles.

3
algorithmlanguage-agnosticgeometry
I am not sure what you are trying to achieve. Is it a non-convex hull that represents the shape of the point-cloud better than a convex one? – Rafał Dowgird
Yes, that is correct. A bit like alpha shapes: cgal.org/Manual/3.4/doc_html/cgal_manual/Alpha_shapes_2/…. Except that my method produces visually nicer results (IMO) for the data I am working with. – James

3 Answers

1
votes

A sweep line algorithm can improve searching for the R-neighbors. Alternatively, you can consider only pairs of points that are in neighboring squares of square grid of width R. Both of these ideas can get rid of the N^2 - of course only if the points are relatively sparse.

I believe that a clever combination of sweeping and convex hull finding cat get rid of the N^2 even if the points are not sparse (as in Olexiy's example), but cannot come up with a concrete algorithm.

0
votes

Yes, using rotating calipers. My prof wrote some stuff on this, it starts on page 19.

0
votes

Please let me know if I misunderstood the problem.

I don't see how do you get N^2 time for brute-forcing all convex hulls in the worst case (1). What if almost any 2 points are closer than R - in this case you need at least N^2*logN to just construct the convex hulls, leave alone computing their union.

Also, where does R^2*logR in your estimation comes from?

1 The worst case (as I see it) for a huge N - take a circle of radius R / 2 and randomly place points on its border and just outside it.