Scurry.PolygonMap (Scurry v3.0.1)

View Source

Utility functions to work on a polygon map.

A polygon map is a set of a primary polygon - the main boundary that outlines the world - and a list of polygons that make holes in the main polygon.

See Polygon for details on how polygons are composed.

The use case is eg. making a map (the main polygon) with obstacles (the holes), and use the Astar module to find the shortest path between points in the map.

See Quickstart for a concrete end-to-end example of defining a world and holes/obstacles, then using PolygonMap and Astar modules to do path finding within this.

Summary

Types

cost()

The cost of a traversel between two nodes is a numeric value

cost_fun()

Function that given two gnode/0 graph nodes, computes the cost. Eg. a euclidian 2D vector function like Scurry.Vector.distance/2. (gnode, gnode -> cost)

gnode()

A graph node (spelled gnode since node is reserved) is any type that can be used as a key in a map/0 For instance a vector/0.

graph()

A graph is a map from gnode/0 to a list of gnode/0 and the traversal cost/0, %{gnode => [{gnode, cost}, ...]}

line()

A line is represented by two vertices of type vector/0

polygon()

A polygon is represented by a list of vector/0, each being a tuple of {x, y} coordinates, both number/0. To be properly defined, the vertices of the polygon must be non-closed and clockwise.

vector()

A vector is represented as a tuple {x, y}, it's x and y components, both number/0. These are used for vector math in Scurry.Vector and as 2D points in Scurry.Polygon and Scurry.PolygonMap.

Functions

create_graph(world, holes, vertices, cost_fun \\ nil)

Given a polygon map (world & holes) and list of vertices, makes the walk graph for a A-star search.

extend_graph(graph, world, holes, vertices, points, cost_fun \\ nil)

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

get_vertices(world, holes)

Given a polygon map (world & holes), returns a list of vertices for a walkmap for A-star search

is_line_of_sight?(polygon, holes, line)

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

nearest_point(world, holes, point)

Find the nearest point on the line that is inside the world polygion and outside all hole polygons.

Types

cost()

@type cost() :: number()

The cost of a traversel between two nodes is a numeric value

cost_fun()

@type cost_fun() :: (gnode(), gnode() -> cost())

Function that given two gnode/0 graph nodes, computes the cost. Eg. a euclidian 2D vector function like Scurry.Vector.distance/2. (gnode, gnode -> cost)

gnode()

@type gnode() :: any()

A graph node (spelled gnode since node is reserved) is any type that can be used as a key in a map/0 For instance a vector/0.

graph()

@type graph() :: %{required(gnode()) => {gnode(), cost()}}

A graph is a map from gnode/0 to a list of gnode/0 and the traversal cost/0, %{gnode => [{gnode, cost}, ...]}

line()

@type line() :: {vector(), vector()}

A line is represented by two vertices of type vector/0

polygon()

@type polygon() :: [vector()]

A polygon is represented by a list of vector/0, each being a tuple of {x, y} coordinates, both number/0. To be properly defined, the vertices of the polygon must be non-closed and clockwise.

vector()

@type vector() :: {x :: number(), y :: number()}

A vector is represented as a tuple {x, y}, it's x and y components, both number/0. These are used for vector math in Scurry.Vector and as 2D points in Scurry.Polygon and Scurry.PolygonMap.

Functions

create_graph(world, holes, vertices, cost_fun \\ nil)

@spec create_graph(polygon(), [polygon()], [vector()], cost_fun() | nil) :: graph()

Given a polygon map (world & holes) and list of vertices, makes the walk graph for a A-star search.

Params

The cost_fun is a function that indicates the of traversing between to points. It defaults to Scurry.Vector.distance/2, which is suitable for basic 2D map walking.

Returns

A graph/0, which is a map of all node to node reachable edges and their cost. This graphs is one of the parameters for a call to Astar.search/4.

Todo

This should ideally take line_of_sight/3 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.

extend_graph(graph, world, holes, vertices, points, cost_fun \\ nil)

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

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

Params

  • graph (graph/0) the walk graph, as created by create_graph/4. This is used to return a new graph that's extended with points.
  • world (polygon/0) the polygon that defines the outer boundary.
  • holes (list/0), a list of polygon/0 that define holes/obstacles inside world.
  • vertices (list/0) the list of vertices returned by get_vertices/4 and used for create_graph/4 to get graph.
  • points (list/0) a list of vectors (vector/0), [{x, y}, {x, y}...], to extend with. Eg. a stop
  • cost_fun (cost_fun/0) a "cost" function.

world and holes need to be passed in in addition to graph, so the function can determine line-of-sights between the existing graph and new points from points.

The cost_fun is a function that indicates the of traversing between to points. It defaults to Scurry.Vector.distance/2, which is suitable for basic 2D map walking.

Returns

A tuple with the extended graph plus the combined list of vertices and new points, {new_graph, new_vertices}. The new_graph is intended to be used in calls to Astar.search/4, and new_vertices is solely provided as informational, eg. for displaying the graphs visually.

get_vertices(world, holes)

@spec get_vertices(polygon(), [polygon()]) :: [vector()]

Given a polygon map (world & holes), returns a list of vertices for a walkmap for A-star search

Params

  • world (polygon/0), the polygon that defines the outer boundary.
  • holes (list/0), a list of polygon/0 that define holes/obstacles inside world.

Returns

The walkmap as a list/0 of vector/0 that are the worlds's concave vertices and the convex ones of the holes.

These are used when generating the walk map, since only the world's concave and the holes' convex ones limit where you can traverse in a 2D map. Any path has to walk around the holes' convex points and the world's concave.

See Quickstart for a concrete example.

is_line_of_sight?(polygon, holes, line)

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.

nearest_point(world, holes, point)

Find the nearest point on the line that is inside the world polygion and outside all hole polygons.

The purpose of this function is to determine compute a suitable end for the points parameter for extend_graph/6. Imagine a UI in which the users clicks on a point to walk to. If that click is outside the world map or inside a hole/obstacle, we can either refuse to compute a path, or we can use nearest_point/3 to find the closest reachable point to the click.

Params

  • world (polygon/0) the polygon that defines the outer boundary.
  • holes (list/0), a list of polygon/0 that define holes/obstacles inside world.
  • point (vector/0) the point for which to find the nearst point.

Returns

A new point (vector/0) p={x, y} such that;

  • if point is outside the world polygon, the new p is the closest point on the edge of the world polygon.

  • if point is inside the world polygon, but also inside any hole polygon, the p the closest point on the edge of the hole it's in.