generateNavigationGraph

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.

Parameters

    the origin of the environment, defaults to (0,0).

    the width of the environment (only positive).

    the height of the environment (only positive).

    the obstacles of the environment (only convex polygonal obstacles
    are supported).

    a collection of positions where to plant initial seeds. In indoor
    environments, these positions are usually located inside rooms
    (and corridors), hence the name of the parameter.

    the quantity considered to be a unit in the environment (defaults
    to 1.0 because this algorithm works best with environments featuring
    integer coordinates). In the growing phase, each side of each seed
    will be advanced of a quantity equal to unity iteratively, hence the
    smaller this value is the slower the algorithm will be.