Find point inside simple polygon (closed loop), part two

Alec Jacobson

August 06, 2010

weblog/

Yesterday I promised I would post the solution I came up with for retrieving a point inside a given polygon. My algorithm is inspired by the ray casting algorithm for determining if a given point is inside a given simple polygon (note the difference in the problem statement). My algorithm hinges on the fact that a ray cast from a point outside the polygon will hit the boundary of the polygon an even number of times, and a point inside the polygon will the boundary of the polygon an odd number of times (there's a few degeneracies here but they are known and easily handled). My algorithm goes as follows.
  1. Fix a point p, that is definitely outside of the polygon, you could just go far enough above the bounding box center.
  2. Shoot a ray from point p. (Yesterday I was shooting rays at the midpoints of all the polygon's sides and then using the one that hits closest to p, but I did find a degeneracy when the rays perfectly align with the sides.) If you chose p as somewhere far enough above the bounding box center, then just shoot the ray straight down.
  3. Let a be the point at which the ray from p first passes through the boundary into the polygon (here we're careful to ignore passing through sides parallel to the ray and through corners that don't pass the ray through the boundary).
  4. Let b be the point at which the ray from p hits the boundary again after hitting a
  5. The mid point between a and b is guaranteed to be within the polygon.
internal point of polygon The brief version goes:
  1. Fix a point p definitely outside the polygon
  2. Shoot a ray from p at the polygon
  3. Collect the first hit, a, and second hit, b
  4. The midpoint of a -> b is an internal point

Proof

It is trivial to show that we can find a point p outside and above the polygon. Now, when shooting a ray at the polygon from p we do have to be careful the our "first hit", a, is recorded as the point at which the ray is really about to enter the polygon. This means if we pass through a corner without going into the polygon we ignore that contact. If we pass through a parallel side of the polygon, then we need to determine if at the far end point of the line we have entered the polygon. These are both easy to check using the angle at the corners in question. internal point of polygon degeneracies With the "second hit", b, we must be careful in sort of the opposite sense. Since we know that just after the ray leaves a we are definitely inside the polygon we need b to be the next time we hit the boundary in any fashion. Now, a quick proof by contradiction that the midpoint of a and b is internal. Assume that the midpoint of a and b is external. Then the ray from a to b must have left the polygon at least once before reaching b in order to reach the midpoint on the exterior. This is a contradiction to the fact that b was chosen to be the closest boundary point on the ray to a. ￭