union with nonzero winding rule

[mbutterick]

Suppose I’d like to reduce a list of Path objects into a single Path with overlaps removed, but winding preserved.

In example A, the crossbar overlaps the sides. If I convert this to an array of Path and reduce into a new Path using union, I get the right result.

In example Q, however, the same approach doesn’t work: union will remove the overlap correctly from the Q tail, but it will also remove the inner contour entirely.

1. Is there a way to invoke union so that it takes account of nonzero winding?
2. Is there a way to test the winding count of a Path? (I see there is an internal windingCount property)
3. Is there a way to combine two Path objects into a new Path without applying any Boolean processing?

[hfutrell]

Hi @mbutterick. Thanks for the helpful diagram in describing your issue.

In the case of the Q the inner contour is removed in your example because when its components are union'd individually the inner contour is treated like a solid oval instead of a hole. Since the inner contour falls completely inside the outer contour, the union of the two is just the outer contour.

I believe that Path.crossingsRemoved() will work in both cases here. The intention of crossingsRemoved is to take a path that normally would be filled using the non-zero winding rule and return a path that can be filled with the even-odd winding rule.

Is there a way to invoke union so that it takes account of nonzero winding?

Right now all boolean operations (union, subtraction, intersection) assume the path can be filled using the even-odd rule. But as a workaround Path.crossingsRemoved() can take a path and make it suitable for that rule. You should be able to pass the results of this method to union and other boolean operations.

Is there a way to test the winding count of a Path?

The closest public method is Path.contains(_ point: CGPoint, using rule: PathFillRule = .winding) which does not give you the count but does tell you if the count is considered inside the path according to the fill rule. Internally as you noticed this method uses Path.windingCount(_ point: CGPoint, ignoring: PathComponent? = nil). In your own fork you could mark this as public. If you let me know your use case I can also weigh making this a public part of the API.

Is there a way to combine two Path objects into a new Path without applying any Boolean processing

You can do let path = Path(components: path1.components + path2.components) If path1 and path2 do not overlap or in some cases even if they do overlap and you are using the non-zero fill rule this can give results that are just fine. In cases where appending path components together doesn't work use Path.union()

[mbutterick]

Thanks — that’s helpful. I got my examples to work by creating a Path for each contour in the glyph, then extracting the Path.components from each of those and combining them into a new Path, and then I did crossingsRemoved on this combined path. (Though with this approach, I didn’t end up needing to use union at all — crossingsRemoved did all the work — does that sound right?)

One case that still behaves oddly is shown below, where opposite-direction paths cross each other, as in the first pic. When I apply crossingsRemoved I get the result in the second pic, with new points at the intersections. However, what I want is to end up with two discrete paths with no overlap. Instead, as depicted in the third pic, the two contours still have the same overlapping area, they just have extra points at the intersection.

[mbutterick]

(To be clear, in the third pic I have taken the contours in #2 and pulled apart the points at the intersection just to reveal how the contours cross)

[hfutrell]

@mbutterick these diagrams are really helpful to illuminate a case where crossingsRemoved is behaving in an unexpected way. I'm not sure what heuristic I need to make the code follow to fix this issue, but it's definitely behaving incorrectly presently. I'm thinking about this ...

Some context: for crossingsRemoved and boolean operations BezierKit builds a graph representation of the Path(s) involved (AugmentedGraph.swift) and inserts nodes that represent the intersections that link one contour to another. To build the resultant path it traverses the graph and visits edges that are determined to be border edges for the specific operation (these can differ between union, subtraction, intersection, etc). Usually there isn't a choice as to which edge to visit next in the graph traversal, but in this case when the code arrives at an intersection node it has several choices, because all 4 edges incident on the intersection nodes are part of the border. In short the graph traversal is presented several choices here and not choosing wisely ...

[hfutrell]

@mbutterick could you do me a favor and try out a branch I've created called issue-64-crossings-removed?

I would like to verify that this fix resolves your issue with the "O" where opposite direction paths cross each other.

[mbutterick]

Yes, the fix does seem to work, thank you. The first pic is another overlap. The second pic shows the immediate result of crossingsRemoved with your patch. The third pic shows the junctions pulled apart. There are two discrete contours now.

The only little glitch is that the right side of the upper contour ends up with two points in that corner instead of one, whereas on the left it only has one. (In some quick tests, the same double-point glitch happens on every curved-segment crossing that results in a new contour; it does not happen when straight segments cross.) Usually a double point like that is a sign of an off-by-one error in closing the path. From the perspective of rendering it's benign, however.

[hfutrell]

@mbutterick I've written a unit test using two ellipses to try to reproduce your issue with the "O", but I'm not seeing a double point.

To help me figure out where the double-point is coming from it would be helpful to know exactly what your path looks like both before and after crossingsRemoved() is called. Something like this:

let path = ... /* your "O" path here */
path.components.enumerated().forEach { print("component \($0.0): curves = \($0.1.curves)") }
let result = path.crossingsRemoved() 
result.components.enumerated().forEach { print("component \($0.0): curves = \($0.1.curves)") }

The crossingsRemoved() method also has an optional accuracy parameter. It would help me to know if you were using the default value here or if not what value you are using.

[mbutterick]

Sorry, my bad — on closer inspection the extra point is my fault. Your revised code is doing the right thing.

[hfutrell]

No problem! I appreciate your help improving the behavior of the API.

For the time being I'd recommend you use the issue-64-crossings-removed branch. Sometime soon I should get the fix into 0.6.6-release at which point I'll close the issue.