# Point in Polygon algorithm from the viewpoint of a robot

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 ?

-
The fence needs to have measurable finite length for the supposed solution to be meaningful as stated. Pedantically, if you can walk both sides of the fence you are able to cross it. If you can see, and line of sight is blocked only by the fence (island is flat enough), then if you are outside you will come to a point on the convex hull from which you can see that the whole fence is on one side of you and there is no fence on the other side. [again subject to topography, there will be a point from which you can see the sea]. Mark a point on the fence. When you return you know. – Mark Bennet Dec 25 '10 at 7:27
@Mark Why a comment and not an answer ? Anyways "then if you are outside you will come to a point on the convex hull from which you can see that the whole fence is on one side of you and there is no fence on the other side" - at that point, looking at any other angle, you'd see the sea which is simpler right ? This is the algorithm I originally thought about - walk the fence and look at all angles for the sea. Obviously this would work, but the "1 meter" solution seems faster if you don't have line of sight and have to walk every time – ohadsc Dec 25 '10 at 12:55

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).

-
Thanks ! Any chance for a link I can read without getting the book ? – ohadsc Dec 24 '10 at 17:20
A lot of the book is on google books (go to books.google.com, search for Santalo, you will find it, then search for Steiner. The original version of the result is for convex sets, but this is easy to extend by additivity. The original proof of the "Chern-Gauss-Bonnet" formula by Allendorfer and Weil used exactly this method -- you might want to look at that paper (published in the 1940s). – Igor Rivin Dec 24 '10 at 17:28
Thanks, I saw it on google books - will check it out – ohadsc Dec 24 '10 at 17:29
Just a quick question - What are n and W_i in the formula ? – ohadsc Dec 24 '10 at 17:36
@ohadsc: hint: try it with a circle! – Kevin Buzzard Dec 24 '10 at 17:58

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$).

-
On the square example, outside path, why is your path not composed of straight lines parallel to the sides, plus a quarter-circle at each corner? This would give $2 \pi$. – Mark Bennet Dec 24 '10 at 19:44
@Mark-Bennet, you are correct that the exterior level set is $2\pi$ larger. My mistake. The interior level set, however, is a smaller square of edge length $2r-2$ for $r \gt 0$. – sleepless in beantown Dec 24 '10 at 20:24
@sleepless-in-beantown, agreed the interior path is square, and $2 \pi$ is not correct. There are some subtleties in definition too. For example the inner path in the square is uniformly distance 1 from the outer path, in the sense that the minimum distance from any point on the inner path to the nearest point on the square is 1. But the original square is not uniformly distance 1 from the inner path (look at the corners). [there is probably a better word than 'uniformly']. I suspect that the $2 \pi$ figure applies when there is uniform distance 1 both ways in the above sense. – Mark Bennet Dec 24 '10 at 21:09