How to determine whether an edge of a nonzero-fill polygon is an outside edge?

Question

Let's assume I have a polygon and I have computed all of its self-intersections. How do I determine whether a specific edge is inside or outside according to the nonzero fill rule? By "outside edge" I mean an edge which lies between a filled region and a non-filled region.

Example:

On the left is an example polygon, filled according to the nonzero fill rule. On the right is the same polygon with its outside edges highlighted in red. I'm looking for an algorithm that, given the edges of the polygon and their intersections with each other, can mark each of the edges as either outside or inside.

Preferably, the solution should generalize to paths that are composed of e.g. Bezier curves.

[EDIT] two more examples to consider:

Answer 1

I've noticed that the "outside edge" that is enclosed within the shape must cross an even number of intersections before they get to the outside. The "non-outside edges" that are enclosed must cross an odd number of intersections.

You might 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 that you can always find an outside edge by trying each line in turn: try extending it infinitely - if it does not cross another line then it should be on the outside. This seems intuitively true but I wonder if there are some pathological cases where you cannot find a start line using this rule. Using this method of finding the first line will not work with curves.

Answer 2

I think, you problem can be solved in two steps.

1. A triangulation of a source polygon with algorithm that supports self-intersecting polygons. Good start is Seidel algorithm. The section 5.2 of the linked PDF document describes self-intersecting polygons.

2. A merge triangles into the single polygon with algorithm that supports holes, i.e. Weiler-Atherton algorithm. This algorithm can be used for both the clipping and the merging, so you need it's "merging" case. Maybe you can simplify the algorithm, cause triangles form first step are not intersecting.

Answer 3

I realized this can be determined in a fairly simple way, using a slight modification of the standard routine that computes the winding number. It is conceptually similar to evaluating the winding both immediately to the left and immediately to the right of the target edge. Here is the algorithm for arbitrary curves, not just line segments:

1. Pick a point on the target segment. Ensure the Y derivative at that point is nonzero.
2. Subdivide the target segment at the Y roots of its derivative. In the next point, ignore the portion of the segment that contains the point you picked in step 1.
3. Determine the winding number at the point picked in 1. This can be done by casting a ray in the +X direction and seeing what intersects it, and in what direction. Intersections at points where Y component of derivative is positive are counted as +1. While doing this, ignore the Y-monotonic portion that contains the point you picked in step 1.
4. If the winding number is 0, we are done - this is definitely an outside edge. If it is nonzero and different than -1, 0 or 1, we are done - this is definitely an inside edge.
5. Inspect the derivative at the point picked in step 1. If intersection of the ray with that point would be counted as -1 and the winding number obtained in step 3 is +1, this is an outside edge; similarly for +1/-1 case. Otherwise this is an inside edge.

In essence, we are checking whether intersection of the ray with the target segment changes the winding number between zero and non-zero.

Answer 4

I'd suggest what I feel is a simpler implementation of your solution that has worked for me:

1. Pick ANY point on the target segment. (I arbitrarily pick the midpoint.)

2. Construct a ray from that point normal to the segment. (I use a left normal ray for a CW polygon and a right normal ray for a CCW polygon.)

3. Count the intersections of the ray with the polygon, ignoring the target segment itself. Here you can chose a NonZero winding rule [decrement for polygon segments crossing to the left (CCW) and increment for a crossing to the right (CW); where an inside edge yields a zero count] or an EvenOdd rule [count all crossings where an inside edge yields an odd count]. For line segments, crossing direction is determined with a simple left-or-right test for its start and end points. For arcs and curves it can be done with tangents at the intersection, an exercise for the reader.

My purpose for this analysis is to divide a self-intersecting polygon into an equivalent set of not self-intersecting polygons. To that end, it's useful to likewise analyze the ray in the opposite direction and sense if the original polygon would be filled there or not. This results in an inside/outside determination for BOTH sides of the segment, yielding four possible states. I suspect an OUTSIDE-OUTSIDE state might be valid only for a non-closed polygon, but for this analysis it might be desirable to temporarily close it. Segments with the same state can be collected into non-intersecting polygons by tracing their shared intersections. In some cases, such as with a pure fill, you might even decide to eliminate INSIDE-INSIDE polygons as redundant since they fill an already-filled space.

And thanks for your original solution!!