Defining Vias with (Loc or Vertex or Edge) and Heading - pgRouting/pgrouting GitHub Wiki

Terminology

  • point - an abstract position definition. like "here", "there", it does NOT imply and specific method of definition.
  • latlon - a point described by (lat, lon) tuple
  • vertex - a point described by a node in a graph
  • edgepos - a point described by an (edge_id, pos) tuple
  • heading - an angle describing a direction of travel from a point, where 0=north, 90=east, etc.
  • gpspnt - a point described by a (lat, lon, heading) tuple

Currently

  • pgr_dijkstra() take points start, end and via points as vertex ids.
  • pgr_trsp() can take points start, end, vias as vertex ids or (edge id, pos) It would be nice if these functions or new equivalent functions could also incorporate heading information into the points used to request routes.

Use Cases

I believe we want to extend this by also adding heading at any given point. The uses of this fall into two separate patterns within pgrouting. 1) is the ability to establish the preferred direction of travel when the route arrives, departs or passes through a given point. 2) as a heuristic aid when selecting an edge that might be used in pgr_trsp() or for select a vertex that is used in dijkstra. Some of the use cases for this are:

  1. when we are computing routes the heading is used to establish the starting or ending direction of the route when there are multiple choices. (see examples below).
  2. gps data often comes with (lat, lon, heading) and/or heading can be derived from the prior gps location if it is not provided depending on the reporting frequency.
  3. we need heading to control the direction of travel at a given point
    • like to pickup or drop off of passengers or packages without the need to cross the street
    • like for trash collection when a vehicle can only service from one side that needs to be curb facing
  4. when selecting edges from a graph using a latlon or gpspnt, having heading information, allows us to pick an edge based on not only the distance from a (lat, lon) but also comparing the heading to the azimuth of the edge and other information like direction of travel allow on the edge. Think of a point between a divided highway going north-south, even if the point is closer to the south bound segment, if the heading is north bound we can select the better match using a heuristic.

Equivalences

It would be useful to be able to convert between the various point classes, so lets look briefly at how we can do that.

We already have functions that do these (I think):

  • latlon -> vertex - simple spatial search for nearest vertex
  • latlon -> vertex - simple spatial search for nearest edge, get position along edge then select edge vertex start if pos<0.5 else end vertex
  • latlon -> edgepos - simple spatial search for nearest edge, get position along edge

We can do this for some other conversions (I have written function for these in other projects and they are simple and straight forward):

  • gpspnt -> vertex - simple spatial search for nearest vertex like: latlon -> vertex
  • gpspnt -> edgepos - this is similar to latlon -> edgepos but we can use the heading in a heuristic as described above to improve the edge selection.
  • gpspnt -> vertex - we can use gpspnt -> edgepos to pick a better edge and then to pick the best vertex associated with that edge.
  • edgepos -> vertex - just as we take a latlon or gpspnt and get and edge, then pick a vertex from that edge we can do the same with this conversion.

Examples

TODO