2

I'd like to find the largest convex hull which fits in the interior of a set of points. I have a set of points which are roughly circular, with a large number of outlier points outside of the circle I'd like to fit. Imagine a circle with "solar flares"... I want to fit the circle and completely ignore the flares. I've tried various fit and culling strategies, but they aren't working well.

I've searched quite a bit and not found a solution. Thanks in advance.

Mark Allen Neil
  • 21
  • 2
  • Could you post a sample or two of what the points might look like? – Nuclearman May 02 '13 at 04:57
  • You might want to look [Gabriel graph](http://en.wikipedia.org/wiki/Gabriel_graph). That should at least be able to limit you to the most relevant edges. If you answer the above question, I can probably extend this into an answer. – Nuclearman May 02 '13 at 05:07
  • I've posted an [image](http://i43.tinypic.com/2entj69.jpg) for reference - it isn't exactly as I described, but similar enough. I ended up not using alpha shapes, as the connectivity between points is dependent on the alpha chosen. Too small an alpha may not close the shape. Too large an alpha will exclude valid points. What I ended up doing was masking out the data I didn't want by multiplying by an annular mask, mirroring the points about the outer edge of the annulus, fitting a convex hull, then mirroring that convex hull about the annular ring again. Works perfectly. – Mark Allen Neil May 04 '13 at 04:29
  • Ah, that's about the worst case I could think of for something like that. I would have suggested a different approach, but unless I missed something, it doesn't sound like mine would be more efficient (O(N log N)). Also it may not have given exactly what you seek. That said, you may want to consider answering your own question with a more detailed explanation of your approach as it may be beneficial to others. – Nuclearman May 06 '13 at 05:19

1 Answers1

0

The notion you need may be alpha shapes. The convex hull is a sub-set of the alpha-shape for an extreme value for alpha. The alpha shape is fitting a set of point closer than the convex hull with some values for alpha.

Theory has been developed by Edelbrunner. This is a good start: http://www.mpi-inf.mpg.de/~jgiesen/tch/sem06/Celikik.pdf

For computation, you must: compute delaunay triangulation and/or voronoi diagram, then select points that observe one condition.

Example alpha shape:

enter image description here

This is in fact a concave hull, and it may disregard outliers.

kiriloff
  • 25,609
  • 37
  • 148
  • 229
  • 1
    Not exactly what I was looking for, but I was able to use this strategy to get something close-enough to what I need. Thank you very much for steering me in this direction. I found the following website truly invaluable for understanding alpha shapes - the Java applet shows you how thing work quite nicely. http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html – Mark Allen Neil May 02 '13 at 00:50