I am experimenting with the RVO2 library for collision avoidance in a 2D simulation. This library supports specifying arbitrary obstacles as a list of vertices. The obstacles must be full shapes, i.e. they must not contain holes.
I've pretty much figured out how to find the contour of a shape (using algorithms such as these), but holes are giving me trouble. Basically I need to solve the following questions:
- How to tell if a contour is inside or outside the shape?
- How to tell if a shape has a hole inside?
- Once a shape has been determined to have a hole, how to segment it to form a shape without hole?
This drawing illustrates the third idea: the outer shape has been segmented so the contour is continuous, i.e. RVO2 can consider it as a shape without hole.