Given a polygon map (main & holes) and list of vertices, makes the graph.

Params

• cost_fun, a node, node :: cost function, defaults to Vector.distance

TODO: this should ideally take line_of_sight as a function so users can customise which vertices can reach each other. But for now, users can make the graph themselves just as easily.

Given a polygon map (main & holes), list of vertices and the initial graph, extend the graph with extra points.

This is used to "temporarily" expand the fixed walk graph with the start and end-point. This is a performance optimisation that saves work by reusing the fixed nodes and extend it with the moveable points.

Params

• polygons, a %{main: [...], hole: [...], hole2: [...]} polygon map.
• graph, the fixed graph, eg. created via create_graph/2.
• vertices the nodes used to create graph.
• points a list of coordinates, [{x, y}, {x, y}...], to extend
• cost_fun, a node, node :: cost function, defaults to Vector.distance

Returns an extended graph plus the combined list of vertices and new points, {new_graph, new_vertices}.

Given a polygon map (main, & holes), returns a list of vertices.

The vertices are the main polygon's concave vertices and the convex ones of the holes.

Checks if there's a line-of-sight (LOS) from start to stop within the map.

Params

• polygon, a list of {x, y} vertices. This is the main boundary map.
• holes, a list of lists of {x, y} vertices. These are holes within polygon.
• line a tuple of points ({{ax, ay}, {bx, by}}) describing a line.

Returns true if there's a line-of-sight and none of the main polygon or holes obstruct the path. false otherwise.

As the map consists of a boundary polygon with holes, LOS implies a few things;

• If either start or stop is outside polygon, the result will be false. Even if both are outside, that's not considered a valid LOS.
• If the distance between start and stop is tiny (< 0.1 arbitrarily), LOS is true.
• Next, it checks that the line between start and stop has no intersections with polygon or holes.
• Finally it checks if the middle of the line between start and stop is inside polygon and outside all holes - this ensures that corner-to-corner across a hole isn't considered a LOS.

Find the nearest point on the line that is inside the map and outside a hole.

Params

• polygon, a list of {x, y} vertices. This is the main boundary map.
• holes, a list of lists of {x, y} vertices. These are holes within polygon.
• point a tuple of coordinates ({x, y}) describing a point

The function will return a new point {bx, by} for b such that;

• if {bx, by} is outside the main map, the new b is the closest point on the main map.

• if b is inside the main map, but also inside a hole, the new bis the closest point on the holes edges.