Open space routing

[Chwiggy]

Is there an existing issue for this?

• I have searched the existing issues

Feature/Enhancement Proposal

Currently routing doesn't work across area features in open route service, but you will be routed along the edges or other paths within that feature even when the natural and shortest path would usually entail crossing the feature diagonally. This would especially make sense for routing with foot profiles.

Additional context

No response

Possible Implementation

There's a recent pull request in OSRM that tackles this issue here: Project-OSRM/osrm-backend#7161

Forum Topic Link

No response

[sfendrich]

Thanks for reporting. This is a well-known issue which we probably won't address unless there is a very strong requirement from our customers.

The major draw backs with open-space routing are:

• Although there are well-known algorithms to solve this problem, it is a quite difficult task in practice. You have chosen a particularly good example for illustration. To compute a route over Universitätsplatz one would need to consider all the trees, benches, bike parking lots, etc.. And then, in the real world, there are so many bikes parked on Universitätsplatz that the computed route would not be walkable.
• Open space routing needs substantial additional resources to find all obstacles mapped on the space and to solve the Euclidean Shortest Paths. One can either (a) compute this at request time, or (b) precompute it for all open spaces during graph building. Case (a) would substantially slow down routing, case (b) would require a lot of additional precomputation and increase the graph size significantly.

[aoles]

Thanks @sfendrich for your feedback and for pointing out the challenges open space routing entails. It would probably be good to know where this requirement comes from @Chwiggy?

A few years ago, the GIScience group actually had a research project on open space routing, which was briefly mentioned in the blog post. The following screenshot shows an original example from it. Further details can be found in the paper.

Unfortunately, the integration of open space routing from back then has been removed from ORS in the process of refactoring and cleaning up the code base. This is because this feature hasn't been used in practice for the reasons mentioned by @sfendrich. However, if the need arises, it should be relatively easy and straightforward to reintroduce it.

[Chwiggy]

This came up during a review of the climate action issues and code bases. There's a desire to acount for open spaces in walkability analyses, be that areas you're supposed to walk on like Universitätsplatz in the example here, or maybe a bit more out there as a way to think about other miscellaneous spaces where people might decide to walk across walkable surfaces (grass in parks, parking lots etc)

I don't think there's an immediate need to have this implemented, but wanted to document that desire, and also the approach OSRM have taken

[aoles]

For the record, the code for open space routing has been living happily in the InFieldGraphBuilder until only recently, when it was removed for no obvious reason via commit afc617e. Maybe @takb or @jhaeu who were involved in this change could further explain the rationale behind it and what issues might come up, if we decide to bring it back again? Cheers!

openrouteservice/ors-engine/src/main/java/org/heigit/ors/routing/graphhopper/extensions/graphbuilders/InFieldGraphBuilder.java

Lines 1 to 257 in 9fdf860

	/* This file is part of Openrouteservice.
	*
	* Openrouteservice is free software; you can redistribute it and/or modify it under the terms of the
	* GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1
	* of the License, or (at your option) any later version.
	* This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
	* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
	* See the GNU Lesser General Public License for more details.
	* You should have received a copy of the GNU Lesser General Public License along with this library;
	* if not, see <https://www.gnu.org/licenses/>.
	*/
	package org.heigit.ors.routing.graphhopper.extensions.graphbuilders;
	import com.carrotsearch.hppc.IntIndexedContainer;
	import com.carrotsearch.hppc.LongArrayList;
	import com.graphhopper.GraphHopper;
	import com.graphhopper.coll.LongIntMap;
	import com.graphhopper.reader.ReaderWay;
	import com.graphhopper.routing.Dijkstra;
	import com.graphhopper.routing.Path;
	import com.graphhopper.routing.util.EncodingManager;
	import com.graphhopper.routing.util.FootFlagEncoder;
	import com.graphhopper.routing.util.TraversalMode;
	import com.graphhopper.routing.weighting.FastestWeighting;
	import com.graphhopper.routing.weighting.Weighting;
	import com.graphhopper.storage.GraphHopperStorage;
	import com.graphhopper.storage.IntsRef;
	import com.graphhopper.storage.RAMDirectory;
	import com.graphhopper.util.DistanceCalc;
	import com.graphhopper.util.DistanceCalcEarth;
	import com.graphhopper.util.EdgeIteratorState;
	import org.heigit.ors.routing.graphhopper.extensions.DataReaderContext;
	import org.locationtech.jts.geom.*;
	import java.util.*;
	public class InFieldGraphBuilder extends AbstractGraphBuilder {
	private final GeometryFactory geometryFactory = new GeometryFactory();
	private final Map<Integer, Integer> intId2idx = new HashMap<>();
	private final Map<Integer, Integer> idx2intId = new HashMap<>();
	private final Map<Integer, Long> intId2osmId = new HashMap<>();
	private final ArrayList<Integer> internalTowerNodeIds = new ArrayList<>();
	private Coordinate[] coordinates;
	private final Set<ArrayList<Integer>> edges = new HashSet<>();
	private final ArrayList<Integer> tmpEdge = new ArrayList<>();
	private List<Weighting> weightings;
	private EncodingManager encodingManager;
	@Override
	public void init(GraphHopper graphhopper) throws Exception {
	// create local network taken from
	// https://github.com/graphhopper/graphhopper/blob/0.5/core/src/test/java/com/graphhopper/GraphHopperTest.java#L746
	FootFlagEncoder footEncoder = new FootFlagEncoder();
	encodingManager = EncodingManager.create(footEncoder);
	weightings = new ArrayList<>(1);
	weightings.add(new FastestWeighting(footEncoder));
	}
	@Override
	public boolean createEdges(DataReaderContext readerCntx, ReaderWay way, LongArrayList osmNodeIds, IntsRef wayFlags, List<EdgeIteratorState> createdEdges) {
	if (!hasOpenSpace(way, osmNodeIds))
	return false;
	LongIntMap nodeMap = readerCntx.getNodeMap();
	Polygon openSpace = osmPolygon2JTS(readerCntx, osmNodeIds);
	internalTowerNodeIds.clear();
	intId2osmId.clear();
	idx2intId.clear();
	intId2idx.clear();
	// fill list with tower nodes
	// fill map "internal ID 2 OSM ID"
	for (int j = 0; j < osmNodeIds.size() - 1; j++) {
	long osmNodeId = osmNodeIds.get(j);
	int internalOSMId = nodeMap.get(osmNodeId);
	intId2osmId.put(internalOSMId, osmNodeId);
	if (internalOSMId < -2) //towernode
	{
	internalTowerNodeIds.add(internalOSMId);
	}
	}
	DistanceCalc distCalc = DistanceCalcEarth.DIST_EARTH;
	try (GraphHopperStorage graphStorage = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(20)) {
	for (int idxMain = 0; idxMain < osmNodeIds.size() - 1; idxMain++) {
	long mainOsmId = osmNodeIds.get(idxMain);
	int internalMainId = nodeMap.get(mainOsmId);
	// coordinates of the first nodes
	double latMain = readerCntx.getNodeLatitude(internalMainId);
	double lonMain = readerCntx.getNodeLongitude(internalMainId);
	// connect the boundary of the open space
	int idxNeighbor = idxMain + 1;
	long neighborOsmId = osmNodeIds.get(idxNeighbor);
	int internalNeighborId = nodeMap.get(neighborOsmId);
	double latNeighbor = readerCntx.getNodeLatitude(internalNeighborId);
	double lonNeighbor = readerCntx.getNodeLongitude(internalNeighborId);
	double distance = distCalc.calcDist(latMain, lonMain, latNeighbor, lonNeighbor);
	graphStorage.edge(idxMain, idxNeighbor).setDistance(distance);
	// iterate through remaining nodes,
	// but not through the direct neighbors
	for (int idxPartner = idxMain + 2; idxPartner < osmNodeIds.size() - 1; idxPartner++) {
	long partnerOsmId = osmNodeIds.get(idxPartner);
	int internalPartnerId = nodeMap.get(partnerOsmId);
	// coordinates of second nodes
	double latPartner = readerCntx.getNodeLatitude(internalPartnerId);
	double lonPartner = readerCntx.getNodeLongitude(internalPartnerId);
	// connect nodes
	LineString ls = geometryFactory.createLineString(new Coordinate[]{new Coordinate(lonMain, latMain), new Coordinate(lonPartner, latPartner)});
	// check if new edge is within open space
	if (ls.within(openSpace)) {
	// compute distance between nodes
	distance = distCalc.calcDist(latMain, lonMain, latPartner, lonPartner);
	// the index number of the nodes in the local network
	// necessary, because it does not accept big values
	// fill
	intId2idx.put(internalMainId, idxMain);
	intId2idx.put(internalPartnerId, idxPartner);
	// fill
	idx2intId.put(idxMain, internalMainId);
	idx2intId.put(idxPartner, internalPartnerId);
	// add edge to local graph
	graphStorage.edge(idxMain, idxPartner).setDistance(distance);
	}
	}
	}
	// a set with all created edges.
	// the nodes which create the edge are stored in a ArrayList.
	// it is important that the first node is smaller than the second node.
	// TODO maybe a treeset would make the code more elegant
	edges.clear();
	// compute routes between all tower nodes using the local graph
	for (int i = 0; i < internalTowerNodeIds.size(); i++) {
	int internalIdTowerStart = internalTowerNodeIds.get(i);
	// check if tower node is in map
	// it can miss if no edge is starting from here
	if (!intId2idx.containsKey(internalIdTowerStart)) {
	continue;
	}
	int idxTowerStart = intId2idx.get(internalIdTowerStart);
	for (int j = i + 1; j < internalTowerNodeIds.size(); j++) {
	int internalIdTowerDestination = internalTowerNodeIds.get(j);
	// check if tower node is in map
	// it can miss if no edge is starting from here
	if (!intId2idx.containsKey(internalIdTowerDestination)) {
	continue;
	}
	int idxTowerDest = intId2idx.get(internalIdTowerDestination);
	// compute route between tower nodes
	try {
	Dijkstra dijkstra = new Dijkstra(graphStorage, weightings.get(0), TraversalMode.EDGE_BASED);
	Path path = dijkstra.calcPath(idxTowerStart, idxTowerDest);
	IntIndexedContainer pathNodes = path.calcNodes();
	// iterate through nodes of routing result
	for (int k = 0; k < pathNodes.size() - 1; k++) {
	// local index
	int idxNodeA = pathNodes.get(k);
	int idxNodeB = pathNodes.get(k + 1);
	// internal Node IDs
	int nodeA = idx2intId.get(idxNodeA);
	int nodeB = idx2intId.get(idxNodeB);
	// add to nodes to array sorted
	int minNode = Integer.min(nodeA, nodeB);
	int maxNode = Integer.max(nodeA, nodeB);
	tmpEdge.clear();
	tmpEdge.add(minNode);
	tmpEdge.add(maxNode);
	boolean edgeIsNew = edges.add(tmpEdge);
	if (edgeIsNew) {
	// it is necessary to get the long node OSM IDs...
	long osmNodeA = intId2osmId.get(minNode);
	long osmNodeB = intId2osmId.get(maxNode);
	addNodePairAsEdgeToGraph(readerCntx, way.getId(), wayFlags, createdEdges, osmNodeA, osmNodeB);
	}
	}
	} catch (Exception ex) {
	// do nothing
	}
	}
	}
	// TODO this loop can maybe be integrated at the part where the boundary edges are handled alread<
	// add boundary of open space
	for (int i = 0; i < osmNodeIds.size() - 1; i++) {
	long osmIdA = osmNodeIds.get(i);
	long osmIdB = osmNodeIds.get(i + 1);
	int internalIdA = nodeMap.get(osmIdA);
	int internalIdB = nodeMap.get(osmIdB);
	// add to nodes to array sorted
	int minIntId = Integer.min(internalIdA, internalIdB);
	int maxIndId = Integer.max(internalIdA, internalIdB);
	// create a boundary edge
	tmpEdge.clear();
	tmpEdge.add(minIntId);
	tmpEdge.add(maxIndId);
	// test if already exists
	boolean edgeIsNew = edges.add(tmpEdge);
	if (edgeIsNew) {
	// edge is added to global GraphHopper graph
	addNodePairAsEdgeToGraph(readerCntx, way.getId(), wayFlags, createdEdges, osmIdA, osmIdB);
	}
	}
	}
	return true;
	}
	private void addNodePairAsEdgeToGraph(DataReaderContext readerCntx, long wayOsmId, IntsRef wayFlags, List<EdgeIteratorState> createdEdges, long node1, long node2) {
	// list which contains the Nodes of the new Edge
	LongArrayList subgraphNodes = new LongArrayList(5);
	subgraphNodes.add(node1);
	subgraphNodes.add(node2);
	createdEdges.addAll(readerCntx.addWay(subgraphNodes, wayFlags, wayOsmId));
	}
	private Polygon osmPolygon2JTS(DataReaderContext readerCntx, LongArrayList osmNodeIds) {
	// collect all coordinates in ArrayList
	if (coordinates == null || coordinates.length < osmNodeIds.size())
	coordinates = new Coordinate[osmNodeIds.size()];
	for (int i = 0; i < osmNodeIds.size(); i++) {
	long osmNodeId = osmNodeIds.get(i);
	int internalID = readerCntx.getNodeMap().get(osmNodeId);
	coordinates[i] = new Coordinate(readerCntx.getNodeLongitude(internalID), readerCntx.getNodeLatitude(internalID));
	}
	Coordinate[] coords = Arrays.copyOf(coordinates, osmNodeIds.size());
	LinearRing ring = geometryFactory.createLinearRing(coords);
	// a JTS polygon consists of a ring and holes
	return geometryFactory.createPolygon(ring, null);
	}
	@Override
	public void finish() {
	// do nothing
	}
	/* * checks if the OSM way is an open space *
	*
	* @param way
	* @param osmNodeIds
	* @return */
	private boolean hasOpenSpace(ReaderWay way, LongArrayList osmNodeIds) {
	long firstNodeId = osmNodeIds.get(0);
	long lastNodeId = osmNodeIds.get(osmNodeIds.size() - 1);
	return (firstNodeId == lastNodeId) && way.hasTag("area", "yes");
	}
	@Override
	public String getName() {
	return "InField";
	}
	}