NaviGator

TODO(improve the quality of this algorithm)

NaviGator (Navigation Graphs Generator) is an algorithm capable of generating an Euclidean2DNavigationGraph of a given environment with obstacles. The nodes of the produced graph are convex polygons representing the areas of the environment traversable by agents (namely, walkable areas), whereas edges represent connections between them.

NaviGator works with rectangular-shaped bidimensional environments with euclidean geometry and double precision coordinates. Note that this algorithm:

• does not guarantee the coverage of 100% of the walkable area.

• is only capable to deal with convex polygonal obstacles (concave ones can be decomposed into convex meshes, whereas for curves bounding boxes can be used).

• is only capable to detect axis-aligned crossings.

• can take a significant amount of time to generate a navigation graph.

Here's a brief description of how the algorithm operates: Firstly, a certain number of seeds is planted in the environment. Each seed is a square-shaped region of unitary side that will grow maintaining a convex shape. Secondly, planted seeds are extended until possible (i.e. until they are in contact with an obstacle or another seed on each side). Finally, crossings are found between the grown seeds.