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.

Outer shape has been segmented so that contour is continuous

  • 1
    \$\begingroup\$ Why do you need to know if obstacles have holes? If there are agents outside of the obstacle, then even if it doesn't have a hole it won't be able to enter it. If the agents are inside an obstacle, then they must be inside the "hole"... in which case it doesn't matter what the outside boundary is. \$\endgroup\$
    – Mokosha
    Mar 16, 2013 at 14:21
  • \$\begingroup\$ If I don't know, then the obstacle will be considered full, and so any unit inside the hole will be considered as inside an obstacle by the collision avoidance library. This means they would not behave as intended, i.e. they'll probably just refuse to move. \$\endgroup\$
    – Asik
    Mar 16, 2013 at 14:31
  • \$\begingroup\$ I believe the obstacles work like backfacing triangles... If it's inside the obstacle it won't be able to "see" the outside boundaries. I haven't tried this to see what happens... Have you tried it to see what happens? (i.e. not "probably" but "definitely" refuse to move) \$\endgroup\$
    – Mokosha
    Mar 16, 2013 at 14:38
  • \$\begingroup\$ Yes, I just tested it and the behavior I described seems to be accurate... agents will not respond to boundaries of obstacles that they are currently inside of. Hence, I don't think you need to worry about the issues in this question. \$\endgroup\$
    – Mokosha
    Mar 16, 2013 at 14:53


You must log in to answer this question.

Browse other questions tagged .