[Solved]: Closing shapes at non-endpoints

Problem Detail: 

Consider how one would represent the following image in vector graphics:

Pretty simple, right? The entire shape can be represented by a single path element.

But suppose additionally that you want to color the heart at the top red. The path element is an open shape, so trying to fill it results in an appropriately red heart but also implementation-dependent bleeding between the spiral endpoints.

Obviously, one could just draw the heart and the spiral tails as separate elements, but then the vector graphics representation no longer mirrors how a human being would draw the same image, and makes it more difficult to manipulate as a single object. One needs a way to communicate to the computer that two particular path segments within the larger path intersect in such a manner that they close a sub-shape.

Is there a vector graphics format capable of doing this? More relevantly, how is it implemented and are there any papers on it?

Asked By : Guest

Answered By : D.W.

If we are not given the region to fill and have to figure that out for ourselves, one simple heuristic is:

• We're probably looking for a closed, bounded region. If the region is unbounded (it connects to the edges of the frame), it's probably not the one we're looking for.

So, you could compute connected components and look for a bounded component.

In your example, this means: look just at the white pixels, and consider two white pixels to be connected to each other if they are adjacent. Now compute the connected components of the resulting set. In your picture, there are 7 connected components, but only one of them is bounded (it does not intersect the top edge, bottom edge, right edge, or left edge of the picture). Therefore, that's probably the one that we want to fill. If you follow this heuristic, it does indeed fill the heart shape.

If there are multiple components that are all bounded (have no intersection with any of the edges), then this heuristic fails and some interaction with the user is required to determine which component the user wanted to fill. But that's probably unavoidable. Your problem statement is ambiguous and does not give us enough information to disambiguate which was desired, so it's not surprising that this might require user interaction in some cases. After all, the computer can't read our minds....

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14086