Does the even-odd rule ever have false positives for deciding a point in a complex polygon?

Question

The wikipedia for even-odd rule says

On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.

On a complex polygon, there are clearly false negatives in the holes. For example, the hole in the middle of a pentagram is within the boundary of the polygon, but any ray to the hole intersects an even number of lines.

However, I can't think of a way to put a point outside the boundary of a complex polygon that has an odd numbered ray. Are there any false positives like this?

Answer 1

The odd-even rule does not require a half-line from the test point, any continuous curve can do (you can deform any area of the plane).

If there is a curve from the point that goes to infinity without meeting the polygon boundary, then the point is outside in the ordinary sense. In that case, the number of intersections is zero, an even number, so the odd-even rule holds.

---

On the opposite, for a point that is inside in the ordinary sense, there cannot be a curve that goes to infinity without crossing the outline, but the number of intersections can be even or odd.

Answer 2

No, there is no "false positive".

What is the meaning when a rule determines the "insideness"?

The SVG defines the even–odd rule by saying:

This rule determines the "insideness" of a point on the canvas by drawing a ray from that point to infinity in any direction and counting the number of path segments from the given shape that the ray crosses. If this number is odd, the point is inside; if even, the point is outside.

The correct interpretation of
$\quad$ "this rule determines the 'insideness' of a point ..."
is
$\quad$ "this rule defines the 'insideness' of a point ...".

Since it is a definition, the rule cannot have false negatives nor false positive.

Are all definitions for "insideness" equivalent? No.

Suppose we are given a closed curve on a plane.

If the curve is simple, i.e., it does not intersect itself, it divides the plane into three parts: itself, an inside part and an outside part. There is no question.

However, when the curve intersects itself, there are several reasonable choices to define what is "inside" and what is "outside" with respect to the curve.

The natural definition is to define a point not on the curve

• as outside if it is connected to the infinity. This condition is the same as it can be moved to infinity without passing through the curve or it is not confined/surrounded by the curve.
• Otherwise, it is inside.

This definition will be called "the natural rule". Only the "outermost perimeter" of the curve is significant for this rule; the "inner segments" of the curve is irrelevant.

Another definition is "the even-odd rule".

A third definition is "the non-zero winding rule".

These three definitions may not agree on which points are inside or outside, as shown by the illustration above provided by Wikipedia.

However, what is "really" outside is outside by any rule.

Your question is asking, given a closed curve, whether a point that is outside by the natural rule could possibly be identified as inside by the even-odd rule.

The answer is no since the outside part defined by the natural rule is "really" outside. It is outside by any rule. We would not adopt a potential rule if it could identify a point that is outside by the natural rule as inside.

Is the even-odd rule consistent? Yes.

Another basic requirement of a rule is, of course, it should be consistent. Given any point not on the curve and any possible way of applying the same rule, the verdict should be either inside always or outside always.

Let us understand why the even-odd rule is consistent.

Given a closed curve that intersects itself, we can split it naturally into simple closed curves ("simple" means non-self-intersecting) that touches each other only at finitely many points. For example, the curve on the left side is split into 5 distinctively colored closed curves as illustrated in the middle part, each of which does not intersect itself. Fill the inside area of each simple closed curve with the same color of that curve.

Let $P$ be any point on the plane.

Following Yves's suggestion, let us draw a curve $\mathscr C$ (which is more general than a ray) from $P$ to infinity. Since the number of path segments from the given curve $\mathscr C$ crosses is the same as the number of intersection points between $\mathscr C$ and the given curve, let us check the intersection points instead.

For simplicity, assume

• $\mathscr C$ does not pass any point that is shared by two or more colored area, i.e., any point that are shared by two or more simple closed curves. If it does, we can perturb $\mathscr C$ around any of those points so that it will not pass them. The perturbation can be made as arbitrarily small as wanted. (If $\mathscr C$ must be a ray, perturb the slope of $\mathscr C$.)
• When $\mathscr C$ passes a point on the given curve, it will enter immediately an neighborhood that is enclosed by a different simple closed curve, leaving its previous neighborhood. If it does not, we can perturb $\mathscr C$.
  In particular, $\mathscr C$ intersects the given curve on finitely many points.

Let us follow the curve starting at $P$, going to infinity.

1. At first, if the starting point $P$ is in a color area, it will exit that area first, intersecting the enclosing simple closed curve once. This event, if it happens, contributes exactly one intersection point.
2. After the previous step, $\mathscr C$ enters a colored area. It must exit that area next into an uncolored area. Then it enters another colored area. It must exit that area next into another uncolored area. After a number of such entering-exiting pairs, it goes to infinity without intersecting the given curve anymore.
   For each pair of entering and exiting, there is a pair of intersection points: the point where $\mathscr C$ enters and the point where $\mathscr C$ exits. As pairs of points, these intersection points do not affect the parity of the number of intersection points between $\mathscr C$ and the given curve.

Hence, if the starting point is in a colored area, the parity is odd. Otherwise, it is even. The parity of the number of intersection points between $\mathscr C$ and the given curve depends only on the starting point $P$, not depending on how we draw $\mathscr C$.

In particular, if there is a curve from $P$ that goes to infinity without intersecting the given curve, then any curve from $P$ that goes to infinity will intersect the given curve an even number of times. In that case, the even-odd rule considers $P$ outside with respect the given curve.

However, a rigorous proof for this consistency might be well beyond the usual course of study. It is highly nontrivial to prove rigorously even the easy and obvious fact that a simple closed curve divides the plane into an inside part and an outside part. Fortunately, a rigorous proof is not necessary for intuitive and effective understanding here, either.