Polygon region computation

Question

So, for work I'm working on a robot controller that explores an arbitrary region. The region is defined by a series of vertices (it's a polygon). Here's an example:

The robot starts in the middle and tries to reach the outermost boundary and then follow it all the way around. However, due to the nature of terrain, it may be unable to reach certain areas, and can only explore a given region:

What I want to do is calculate all individual regions that have not been explored, and return the vertices that defines their boundaries, like this:

After this is computed, I should have a new array of polygons, containing the geometry for A, B, and C.

Unfortunately, I can't come up with a good, fast algorithm to do this. What's the best way to compute this?

Answer 1

One method is to define a predicate for a point p to be "touching" the boundary of the enclosing region, perhaps according to some tolerance ε > 0, e.g., T if and only if p is within a distance of ε of the boundary. Then traverse the boundary of the explored region, noting this predicate for each vertex: ..,T, T, T, F, F, F, F, F, T, T,... Then your regions are delimited by maximal strings of Fs, the two T vetices bounding those Fs, and the bounding region's boundary between. The string I just used as an example outlines your region B: five Fs.

Answer 2

ISTM that you're wanting the boolean difference of the outer bounding polygon minus the inner pink (explored) polygon. However there's no simple algorithm for this, so I suggest you look at and choose from the various polygon clipping libraries.

Here's a fairly recent comparison of a number of clipping libraries - http://rogue-modron.blogspot.com.au/2011/04/polygon-clipping-wrapper-benchmark.html

And also a shameless plug for my own open source freeware polygon clipper - http://angusj.com/delphi/clipper.php