I've written a contouring class that produces "nested polygons" and I would like to create Path2D objects that can be used for rendering area-fill operations with embedded "holes" for the interior polygons. Path2D provides the option of using two different winding rules, WIND_EVEN_ODD and WIND_NON_ZERO. I can use either, but I was wondering if one or the other would be preferred in terms of robustness and speed. While the polygons I produce are generally non-self intersecting, they can be rather complex and have fine-level details along their borders. I am a bit concerned about issues with closely spaced polygons or numerical errors.
I think the even-odd rule would be a bit faster computationally, simply since for non-zero, you need to not only find the intersections, but also work out the directionality. Though I suspect the performance difference is small. I also personally favor the even-odd rule, simply because I can easily look at a shape and tell whether a region is inside or out; it's not hard. Whereas for non-zero I find it confusing to work out in my head.
More importantly, are there any cases where your application would actually encounter a difference? From your description, it seems the answer is likely no. And if there are any overlap areas where a difference might occur, due to numerical error, they would be very small. Unless you're making maps of a TARDIS, or a land designed by Escher perhaps.
Perhaps the best approach might be to run some tests by applying both rules to a large set of sample data, to discover (a) if any of the data actually give different results for the two different rules, and (b) if there's any difference in performance. I suspect the answer to the first is no, and quite possibly for the second as well.
Thanks for the responses. Basically, you've confirmed what I suspected.
In testing with a large number of polygons, I haven't seen any significant performance difference between the two approaches. And, certainly, the graphical part of the process is so fast that it's not worth worrying about.
I was more concerned about robustness in the face of problematic geometries. Since the contours are built from real-world data sources, locally steep gradients can lead to closely spaced contours. Occasionally, there might be "spike" features where the angle between two subsequent segments is small. I have pre-processing I can run to eliminate some of this, but I am sure sooner or later something will slip through. I wondered if one approach might be less likely than the other to produce strange-looking graphics.
In theory, and by definition, contouring will never give rise to polygons that self-intersect or intersect or cross other polygons. But the edges of a contour may contain small-scale features that potentially complicate the rendering. You can see some of this in the "smoothing" image in the web article I cited (picture below):
Very cool. OK, I think we would agree that both algorithms would produce the same result for a single non-intersecting closed path. So one potential problem is if the path does self-intersect due to some error. For the simplest example I can think of where this would make a difference, consider a piece of rubber shaped as the letter "C", and consider what would happen if we bend it so that the two tips of the C touch, and then bend it a little more so the tips overlap. In this case, even-odd will tell you that the overlap area is outside the C, and non-zero will tell you that it's inside. Which would be correct, for your application? I suspect the overlap area should still be part of the C, so non-zero would be more accurate in this case. So if this type of accidental overlap is possible, you would want non-zero.
On the other hand, forget about self-intersection - what if there's more than one path? For example, what if we have an island with a lake in its interior, represented as two concentric circles? Or, what if that interior lake also has an island within it (three concentric circles)? If you're trying to use these algorithms to separate land from water... seems like even-odd gives you the correct answers regardless, while for non-zero, it will depend on which direction you draw each path. I think that to get correct answers with non-zero, you would need to make all island borders clockwise, and all lake borders counterclockwise - or vice versa.
Of course, if you're not trying to separate land from water, but simply identify everywhere that is "inside" the island, then the answers change again. So, I guess it depends what you're trying to do. But maybe these questions will give you a reason to prefer one algorithm to the other.
Thanks for your analysis. You picked up on a lot of the nuances of the problem.
I think that I may be leaning toward your suggestion for the non-zero winding rule. Based on your example of the C-shape, I can see where it might be less likely to produce a terrible-looking graphic in the event of a malformed polygon. Ideally, as long as the contouring software works, things like that shouldn't happen. But practically, I suspect that floating-point round-off or just the truncation to integer pixel coordinates could lead to issues.
In terms of nesting...
For contour polygons, you can have any number of nested polygons (as in the a set of concentric rings). The standard way of dealing with this is to have one enclosing polygon that includes holes for just the outermost of its nested children. So in the pond-inside-an-island case, you have:
1. The mainland polygon contains the lake as a hole
2. The lake polygon contains the island as a hole
3. The island contains the pond as a hole
4. The pond stands alone
In mapping and Geographic Information Systems (GIS), there is a standard file format for this called the "Shapefile format" which gives enclosing polygons in clockwise order and enclosed polygons in counter-clockwise order. So an enclosed polygon would be given in the file twice: once as itself (clockwise) and once as a hole (counterclockwise). The contouring implementation that I wrote has orientation information available to it (though it uses the opposite order: regular polygons are counterclockwise and holes are clockwise). So it is easy enough for me to adopt to whatever conventions would be required for either winding rule.
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop