ConcaveBallsIsochroneMapBuilder.java

  1. /*  This file is part of Openrouteservice.
  2.  *
  3.  *  Openrouteservice is free software; you can redistribute it and/or modify it under the terms of the
  4.  *  GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1
  5.  *  of the License, or (at your option) any later version.

  7.  *  This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  8.  *  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  9.  *  See the GNU Lesser General Public License for more details.

  11.  *  You should have received a copy of the GNU Lesser General Public License along with this library;
  12.  *  if not, see <https://www.gnu.org/licenses/>.
  13.  */
  14. package org.heigit.ors.isochrones.builders.concaveballs;

  16. import com.carrotsearch.hppc.IntObjectMap;
  17. import com.carrotsearch.hppc.cursors.IntObjectCursor;
  18. import com.graphhopper.coll.GHIntObjectHashMap;
  19. import com.graphhopper.routing.SPTEntry;
  20. import com.graphhopper.storage.GraphHopperStorage;
  21. import com.graphhopper.storage.NodeAccess;
  22. import com.graphhopper.util.*;
  23. import com.graphhopper.util.shapes.GHPoint3D;
  24. import org.apache.log4j.Logger;
  25. import org.heigit.ors.common.TravelRangeType;
  26. import org.heigit.ors.isochrones.GraphEdgeMapFinder;
  27. import org.heigit.ors.isochrones.IsochroneMap;
  28. import org.heigit.ors.isochrones.IsochroneSearchParameters;
  29. import org.heigit.ors.isochrones.builders.AbstractIsochroneMapBuilder;
  30. import org.heigit.ors.routing.graphhopper.extensions.AccessibilityMap;
  31. import org.locationtech.jts.geom.*;

  33. import java.util.ArrayList;
  34. import java.util.List;

  36. public class ConcaveBallsIsochroneMapBuilder extends AbstractIsochroneMapBuilder {
  37.     private static final Logger LOGGER = Logger.getLogger(ConcaveBallsIsochroneMapBuilder.class.getName());

  39.     @Override
  40.     public Logger getLogger() {
  41.         return LOGGER;
  42.     }

  44.     public IsochroneMap compute(IsochroneSearchParameters parameters) throws Exception {
  45.         StopWatch swTotal = null;
  46.         StopWatch sw = null;
  47.         if (LOGGER.isDebugEnabled()) {
  48.             swTotal = new StopWatch();
  49.             swTotal.start();
  50.             sw = new StopWatch();
  51.             sw.start();
  52.         }

  54.         GraphHopperStorage graph = searchContext.getGraphHopper().getGraphHopperStorage();
  55.         String graphdate = graph.getProperties().get("datareader.import.date");

  57.         double maxSpeed = determineMaxSpeed();
  58.         double meanSpeed = determineMeanSpeed(maxSpeed);

  60.         AccessibilityMap edgeMap = GraphEdgeMapFinder.findEdgeMap(searchContext, parameters);

  62.         GHPoint3D point = edgeMap.getSnappedPosition();

  64.         Coordinate loc = (point == null) ? parameters.getLocation() : new Coordinate(point.lon, point.lat);

  66.         IsochroneMap isochroneMap = new IsochroneMap(parameters.getTravellerId(), loc);

  68.         isochroneMap.setGraphDate(graphdate);

  70.         if (LOGGER.isDebugEnabled()) {
  71.             sw.stop();

  73.             LOGGER.debug("Find edges: " + sw.getSeconds());
  74.         }

  76.         if (edgeMap.isEmpty())
  77.             return isochroneMap;

  79.         List<Coordinate> isoPoints = new ArrayList<>((int) (1.2 * edgeMap.getMap().size()));

  81.         if (LOGGER.isDebugEnabled()) {
  82.             sw = new StopWatch();
  83.             sw.start();
  84.         }

  86.         markDeadEndEdges(edgeMap);

  88.         if (LOGGER.isDebugEnabled()) {
  89.             sw.stop();
  90.             LOGGER.debug("Mark dead ends: " + sw.getSeconds());
  91.         }

  93.         int nRanges = parameters.getRanges().length;

  95.         double metersPerSecond = maxSpeed / 3.6;
  96.         // only needed for reachfactor property
  97.         double meanMetersPerSecond = meanSpeed / 3.6;

  99.         double prevCost = 0;
  100.         for (int i = 0; i < nRanges; i++) {
  101.             double isoValue = parameters.getRanges()[i];
  102.             double isochronesDifference = parameters.getRanges()[i];
  103.             if (i > 0)
  104.                 isochronesDifference = isochronesDifference - parameters.getRanges()[i - 1];

  106.             TravelRangeType isochroneType = parameters.getRangeType();

  108.             if (LOGGER.isDebugEnabled()) {
  109.                 sw = new StopWatch();
  110.                 sw.start();
  111.             }

  113.             double maxRadius;
  114.             double meanRadius;
  115.             if (isochroneType == TravelRangeType.DISTANCE) {
  116.                 maxRadius = isoValue;
  117.                 meanRadius = isoValue;
  118.             } else {
  119.                 maxRadius = metersPerSecond * isoValue;
  120.                 meanRadius = meanMetersPerSecond * isoValue;
  121.                 isochronesDifference = metersPerSecond * isochronesDifference;
  122.             }

  124.             double smoothingDistance = convertSmoothingFactorToDistance(parameters.getSmoothingFactor(), maxRadius);

  126.             GeometryCollection points = buildIsochrone(edgeMap, isoPoints, isoValue, prevCost, isochronesDifference, 0.85, smoothingDistance);

  128.             if (LOGGER.isDebugEnabled()) {
  129.                 sw.stop();
  130.                 LOGGER.debug(i + " Find points: " + sw.getSeconds() + " " + points.getNumPoints());
  131.                 sw = new StopWatch();
  132.                 sw.start();
  133.             }

  135.             addIsochrone(isochroneMap, points, isoValue, meanRadius, smoothingDistance);

  137.             if (LOGGER.isDebugEnabled())
  138.                 LOGGER.debug("Build concave hull total: " + sw.stop().getSeconds());

  140.             prevCost = isoValue;
  141.         }

  143.         if (LOGGER.isDebugEnabled())
  144.             LOGGER.debug("Total time: " + swTotal.stop().getSeconds());

  146.         return isochroneMap;
  147.     }

  149.     private void markDeadEndEdges(AccessibilityMap edgeMap) {
  150.         IntObjectMap<SPTEntry> map = edgeMap.getMap();
  151.         IntObjectMap<Integer> result = new GHIntObjectHashMap<>(map.size() / 20);

  153.         for (IntObjectCursor<SPTEntry> entry : map) {
  154.             SPTEntry edge = entry.value;
  155.             if (edge.originalEdge == -1)
  156.                 continue;

  158.             result.put(edge.parent.originalEdge, 1);
  159.         }

  161.         for (IntObjectCursor<SPTEntry> entry : map) {
  162.             SPTEntry edge = entry.value;
  163.             if (edge.originalEdge == -1)
  164.                 continue;

  166.             if (!result.containsKey(edge.originalEdge))
  167.                 edge.edge = -2;
  168.         }
  169.     }

  171.     private GeometryCollection buildIsochrone(AccessibilityMap edgeMap, List<Coordinate> points,
  172.                                         double isolineCost, double prevCost, double isochronesDifference,
  173.                                         double detailedGeomFactor,
  174.                                         double minSplitLength) {
  175.         IntObjectMap<SPTEntry> map = edgeMap.getMap();

  177.         points.clear();

  179.         if (previousIsochronePolygon != null)
  180.             points.addAll(createCoordinateListFromPolygon(previousIsochronePolygon));

  182.         GraphHopperStorage graph = searchContext.getGraphHopper().getGraphHopperStorage();
  183.         NodeAccess nodeAccess = graph.getNodeAccess();
  184.         int maxNodeId = graph.getNodes() - 1;
  185.         int maxEdgeId = graph.getEdges() - 1;

  187.         double bufferSize = 0.0018;
  188.         double detailedZone = isolineCost * detailedGeomFactor;

  190.         boolean useHighDetail = map.size() < 1000 || isochronesDifference < 1000;

  192.         if (useHighDetail) {
  193.             bufferSize = 0.00018;
  194.         }

  196.         StopWatch sw = new StopWatch();

  198.         for (IntObjectCursor<SPTEntry> entry : map) {
  199.             SPTEntry goalEdge = entry.value;
  200.             int edgeId = goalEdge.originalEdge;
  201.             int nodeId = goalEdge.adjNode;

  203.             if (edgeId == -1 || nodeId == -1 || nodeId > maxNodeId || edgeId > maxEdgeId)
  204.                 continue;

  206.             float maxCost = (float) goalEdge.weight;
  207.             float minCost = (float) goalEdge.parent.weight;

  209.             // ignore all edges that have been considered in the previous step. We do not want to do this for small
  210.             // isochrones as the edge may have more than one range on it in that case
  211.             if (minCost < prevCost && isochronesDifference > 1000)
  212.                 continue;

  214.             EdgeIteratorState iter = graph.getEdgeIteratorState(edgeId, nodeId);

  216.             // edges that are fully inside the isochrone
  217.             if (isolineCost >= maxCost) {
  218.                 // This checks for dead end edges, but we need to include those in small areas to provide realistic
  219.                 // results
  220.                 if (goalEdge.edge != -2 || useHighDetail) {
  221.                     double edgeDist = iter.getDistance();
  222.                     boolean detailedShape = (edgeDist > 200);
  223.                     if (maxCost >= detailedZone || detailedShape) {
  224.                         if (LOGGER.isDebugEnabled())
  225.                             sw.start();
  226.                         addBufferedEdgeGeometry(points, minSplitLength, iter, detailedShape, goalEdge, bufferSize);
  227.                         if (LOGGER.isDebugEnabled())
  228.                             sw.stop();
  229.                     } else {
  230.                         addPoint(points, nodeAccess.getLon(nodeId), nodeAccess.getLat(nodeId));
  231.                     }
  232.                 }
  233.             } else {
  234.                 if (minCost < isolineCost && maxCost >= isolineCost) {
  235.                     if (LOGGER.isDebugEnabled())
  236.                         sw.start();
  237.                     addBorderEdgeGeometry(points, isolineCost, minSplitLength, iter, maxCost, minCost, bufferSize);
  238.                     if (LOGGER.isDebugEnabled())
  239.                         sw.stop();
  240.                 }
  241.             }
  242.         }
  243.         if (LOGGER.isDebugEnabled())
  244.             LOGGER.debug("Expanding edges " + sw.getSeconds());

  246.         Geometry[] geometries = new Geometry[points.size()];

  248.         for (int i = 0; i < points.size(); ++i) {
  249.             Coordinate c = points.get(i);
  250.             geometries[i] = geometryFactory.createPoint(c);
  251.         }

  253.         return new GeometryCollection(geometries, geometryFactory);
  254.     }
  255. }
Created with JaCoCo 0.8.10.202304240956