CodeBunny
CodeBunny

Reputation: 2031

Polygon region computation

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:

An example region.

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:

Full exploration is blocked.

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:

The calculated regions

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?

Upvotes: 2

Views: 364

Answers (2)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

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.

Upvotes: 2

Angus Johnson
Angus Johnson

Reputation: 4643

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

Upvotes: 2

Related Questions