Point in Polygon algorithm from the viewpoint of a robot

Question

I've come across the following puzzle:

You're on an island, on which there is a fence (which is a simple closed contour). You need to determine whether you're inside or outside the fence.

Now if you had the function defining the contour as well as the point you're in (e.g. you have a GPS), you could calculate the winding number. If you could climb over the fence, you could use ray casting. Both methods are described here.

However, I've come across a claimed solution that presumably does not require any of them: Traverse the fence - say by keeping the fence stuck to your left side, until you've come back where you started, (assuming you can mark your start position). Repeat the process where the fence is always 1 meter to your left, orthogonally (assuming you can maintain orthogonality, maintain the 1 meter distance and the fence is always wide enough for you to maintain it).

The claim is - if the second trip (the one walking 1 meter away from the fence) took more time (assuming you can measure time and maintain the same exact speed throughout both trips), you're in the exterior. otherwise you're in the interior.

I haven't been able to prove this, and I'm not even sure it's right (couldn't find a counterexample, though).

Any thoughts ?

Answer 1

Yes, this is correct, the distance you will traverse will be 6.28 meters greater (if you are outside) and 6.28 meters shorter if you are inside, so you better have a very accurate instrument. The relevant result is Steiner's formula for the measures of parallel sets (see Santalo's book on Integral Geometry and Geometric Probability, which is, happily, re-published, after languishing in Academic Press limbo).

Answer 2

Lookj up "level sets".

The wikipedia page "Point in Polygon" talks about algorithms that can be used when the polygon's coordinates are known. The proposed solution of the length of a path following the fence along the fence (call it $d_0$) and a path following along the fence but maintaining a constant distance of $x=1$ meter (call it $d_1$) will work for a robot that can do the tasks you're asking of it. However, the answer of the difference in length being $2 \pi \sim 6.28$ meters would only apply if the fence is perfectly circular.

Given a map or diagram of the fence, generate multiple contours or level sets of points which are a constant distance from the fence. You'll end up with something that looks like a contour map or topographical map that the U.S. Geological surveys generates. Notice that for each distance $x$ (up to a certain limiting value), the level sets for $d_x$ may contain points inside the fence as well as outside the fence. Once $x$ is greater than the radius of the circle, the level sets for $d_x$ such that $x \gt r$ will only contain points outside the circle. For fences with concavities (like a pinched figure 8), the inner level set may break up into multiple non-connected paths.

If the fence is square, width edge length $2r$, then the close-fence contour $d_0$ will be $4 \times 2r = 8r$, whereas the 1-meter level set will be

• $4 \times (2r) + 4 \times (\frac{1}{2} \pi) = 8r + 2 \pi $ if the robot's path is 1-meter outside the fence (which consists of the edges translated outward a distance of 1-meter, and of quarter-circle arcs at each of the corner, as correctly pointed out by Mark Bennet's comment below).

• $4 \times (2r-2) = 8r - 4$ if the robot path is 1-meter inside the fence.

Thus for square, non-convex, and pretty much any noncircular fence, the level-set path one meter of the fence will not be $2 \pi \sim 6.28$ meters different from the level-set path of distance $0$ from the fence.

The generalization, however, will still apply that the level set path of distance $x$ away from the fence will be smaller ($d_x \lt d_0$) if the robot follows the level set path within the fence, vs. larger if the robot follows the level set path outside the fence ($d_x \gt d_0$).