How to determine if the edge of a non-zero filled polygon is an outer edge?
Suppose I have a polygon and I have calculated all of its self-intersections. How do I determine if a particular edge is inside or outside according to a non-zero padding rule? By "outer edge" I mean the edge that lies between the filled area and the unfilled area.
Example:
On the left is an example of a polygon filled with a non-zero fill rule. On the right is the same polygon with its outer edges highlighted in red. I'm looking for an algorithm that, given the edges of a polygon and their intersection with each other, can mark each of the edges both outside and inside.
Preferably, the solution should be generalized to paths that are composed, for example, Bezier Curves.
[EDIT] two more examples:
source to share
I realized that this can be determined in a fairly simple way, using a slight modification of the standard routine that calculates the winding number. This is conceptually similar to evaluating the winding both immediately to the left and right of the target edge. Here's the algorithm for arbitrary curves, not just line segments:
- Select a point in the target segment. Make sure the Y derivative at this point is nonzero.
- Divide the target segment into the Y roots of its derivative. In the next step, ignore the portion of the segment that contains the point you selected in step 1.
- Determine the winding number at the point selected at 1. This can be done by aiming the beam in the + X direction and seeing what crosses it and in which direction. The intersections at the points where the Y-component of the derivative is positive are considered +1. When doing this, ignore the Y-monotone portion containing the point you selected in step 1.
- If the winding number is 0, we're done - this is definitely the outer edge. If it is nonzero and different from -1, 0, or 1, we do so - this is definitely the inner edge.
- Inspect the derivative at the point selected in step 1. If the ray's intersection with this point is considered to be -1, and the number of wrap obtained in step 3 is +1, this is the outer edge; similarly for the + 1 / -1 case. Otherwise, it is the inner edge.
In essence, we check if the intersection of the beam with the target segment changes the number of windings between zero and non-zero.
source to share
I noticed that the "outer edge" enclosed within the form must cross an even number of intersections before they hit the street. "Non-Outer Boundaries" that are enclosed must cross an odd number of intersections.
You can try an algorithm like this
isOutside = true
edge = find first outside edge*
edge.IsOutside = isOutside
while (not got back to start) {
edge = next
if (gone over intersection)
isOutside = !isOutside
edge.IsOutside = isOutside
}
For example:
* I think you can always find the outside edge by trying each line in turn: try to expand it infinitely - if it doesn't cross another line then it should be outside. This seems intuitively correct, but I'm wondering if there are any pathological cases where you cannot find the starting line using this rule. Using this first line search method will not work with curves.
source to share
I think you can solve the problem in two steps.
-
Triangulating the original polygon with an algorithm that supports self-intersecting polygons. A good start is Seidel's algorithm . Section 5.2 of the linked PDF describes self-intersecting polygons.
-
Merge triangles into one polygon with an algorithm that supports holes i.e. Weiler-Atherton algorithm . This algorithm can be used for both clipping and merging, so you need a 'merge'. Perhaps you can simplify the algorithm because the triangles form the first step, do not intersect.
source to share