Skip to main content
1 of 2
ohadsc
  • 163
  • 5

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.

Any thoughts ?

ohadsc
  • 163
  • 5