2

I'm working with a graph, where I need to highlight subgraphs. The graph is in 2D. Right now, I generate a set of points from bounding rectangles of all objects that need to be highlighted, and find a convex hull of these points, like this:

Convex hull

However, this doesn't work that well, since a convex hull can potentially have huge empty gaps in it. If there were another subgraph going through that empty space, it would incorrectly represent two graphs intersecting.

I've been playing around with different algorithms, but I can't find the one that works reliably and would produce desired results. The best I've come up with is this:

"Deflated" Convex hull

...but it's unstable and very hard to debug. Before I dive back into it, I was wondering if there are any well-known algorithms to shrink-wrap a set of points. If you were to represent a convex hull as something made of an elastic material, imagine if the air was sucked out of the graph, so the empty areas of the convex hull would cave in.

Are there any well-known algorithms to do this, or is this problem too specific?

Nik I.
  • 177
  • 1
  • 11
  • Perhaps [this question on the 3D version of this problem](http://stackoverflow.com/questions/4882993/mesh-generation-from-points-with-x-y-and-z-co-ordinate) can help? Note, though, that the problem itself is somewhat ill-defined, since the "deflated convex hull" is not unique - you probably need some kind of measure of how large gaps you will accept (for instance, the ninth point from the bottom left in your illustration could have been skipped, and the hull would still look quite well-fitted). – Aasmund Eldhuset Feb 07 '12 at 22:58
  • Right, the deflation factor would have to be parameterized, of course. This looks promising, I'll check it out. Thanks! – Nik I. Feb 07 '12 at 23:19

0 Answers0