3
$\begingroup$

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

A heart shape with mirrored spiral tails at the bottom.

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?

$\endgroup$
  • $\begingroup$ I think most graphics programs use what wikipedia describes in its article on "point in polygon". I think they use the "even-odd rule." But as you point out, that will cause strange filling to occur in the spirals. $\endgroup$ – Wandering Logic Sep 2 '13 at 16:38
  • $\begingroup$ I don't understand what you are trying to accomplish. If you want the user to be able to ask that a particular region be filled, why don't you have the user select a single point and then flood-fill in everything in the same connected component as that point? I suspect I must have misunderstood some aspect of the question... $\endgroup$ – D.W. Sep 3 '13 at 1:49
  • 1
    $\begingroup$ Are asking for a ready-made tool, implementations or for algorithmic approaches? The former two are offtopic here, the latter is ontopic, so I suggest you edit your question to clarify. $\endgroup$ – Raphael Sep 3 '13 at 10:04
  • $\begingroup$ @D.W. I guess the challenge will be to figure out this region given a vector graphic. $\endgroup$ – Raphael Sep 3 '13 at 10:05
  • $\begingroup$ I don't understand your question. The behaviour entirely up to the implementor of the system, and you haven't even specified a system. $\endgroup$ – David Richerby Dec 29 '18 at 5:45
0
$\begingroup$

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....

$\endgroup$
  • $\begingroup$ This is probably the neatest possible solution, since any filling algorithm needs to inspect every pixel anyway. A "flood fill starting point", as you suggested in your earlier comment, would also take care of the ambiguity. Now the only question that remains is whether there are any vector graphics formats/tools that actually support such an operation... but as @Raphael said, that's not a question for this forum. Anyways, thanks. Marked as accepted. $\endgroup$ – Guest Sep 3 '13 at 23:37
1
$\begingroup$

In CAD systems this is done

  • On user side
    • find intersection of two curves
    • split curves by their intersection
    • make closed path to form a polygon
    • fill polygon
    • you can still group separated line into one line and operate with it as previously, change in internal logic (math core side) will be hidden from you
  • On math core side
    • choose appropriate method of intersection of curves based on the type of the curves
    • do intersection either by exact intersection if lines types support this (eg straight lines) or by numerical method (usually iterative) in other cases (eg when you have splines underlying)
    • create new curves based on existent edges of lines and on the found intersection point
    • an so on
$\endgroup$

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.