ConcaveBallsIsochroneMapBuilder.java

/*  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.isochrones.builders.concaveballs;

import com.carrotsearch.hppc.IntObjectMap;
import com.carrotsearch.hppc.cursors.IntObjectCursor;
import com.graphhopper.coll.GHIntObjectHashMap;
import com.graphhopper.routing.SPTEntry;
import com.graphhopper.storage.GraphHopperStorage;
import com.graphhopper.storage.NodeAccess;
import com.graphhopper.util.*;
import com.graphhopper.util.shapes.GHPoint3D;
import org.apache.log4j.Logger;
import org.heigit.ors.common.TravelRangeType;
import org.heigit.ors.isochrones.GraphEdgeMapFinder;
import org.heigit.ors.isochrones.IsochroneMap;
import org.heigit.ors.isochrones.IsochroneSearchParameters;
import org.heigit.ors.isochrones.builders.AbstractIsochroneMapBuilder;
import org.heigit.ors.routing.graphhopper.extensions.AccessibilityMap;
import org.locationtech.jts.geom.*;

import java.util.ArrayList;
import java.util.List;

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

    @Override
    public Logger getLogger() {
        return LOGGER;
    }

    public IsochroneMap compute(IsochroneSearchParameters parameters) throws Exception {
        StopWatch swTotal = null;
        StopWatch sw = null;
        if (LOGGER.isDebugEnabled()) {
            swTotal = new StopWatch();
            swTotal.start();
            sw = new StopWatch();
            sw.start();
        }

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

        double maxSpeed = determineMaxSpeed();
        double meanSpeed = determineMeanSpeed(maxSpeed);

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

        GHPoint3D point = edgeMap.getSnappedPosition();

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

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

        isochroneMap.setGraphDate(graphdate);

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

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

        if (edgeMap.isEmpty())
            return isochroneMap;

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

        if (LOGGER.isDebugEnabled()) {
            sw = new StopWatch();
            sw.start();
        }

        markDeadEndEdges(edgeMap);

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

        int nRanges = parameters.getRanges().length;

        double metersPerSecond = maxSpeed / 3.6;
        // only needed for reachfactor property
        double meanMetersPerSecond = meanSpeed / 3.6;

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

            TravelRangeType isochroneType = parameters.getRangeType();

            if (LOGGER.isDebugEnabled()) {
                sw = new StopWatch();
                sw.start();
            }

            double maxRadius;
            double meanRadius;
            if (isochroneType == TravelRangeType.DISTANCE) {
                maxRadius = isoValue;
                meanRadius = isoValue;
            } else {
                maxRadius = metersPerSecond * isoValue;
                meanRadius = meanMetersPerSecond * isoValue;
                isochronesDifference = metersPerSecond * isochronesDifference;
            }

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

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

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

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

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

            prevCost = isoValue;
        }

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

        return isochroneMap;
    }

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

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

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

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

            if (!result.containsKey(edge.originalEdge))
                edge.edge = -2;
        }
    }

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

        points.clear();

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

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

        double bufferSize = 0.0018;
        double detailedZone = isolineCost * detailedGeomFactor;

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

        if (useHighDetail) {
            bufferSize = 0.00018;
        }

        StopWatch sw = new StopWatch();

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

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

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

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

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

            // edges that are fully inside the isochrone
            if (isolineCost >= maxCost) {
                // This checks for dead end edges, but we need to include those in small areas to provide realistic
                // results
                if (goalEdge.edge != -2 || useHighDetail) {
                    double edgeDist = iter.getDistance();
                    boolean detailedShape = (edgeDist > 200);
                    if (maxCost >= detailedZone || detailedShape) {
                        if (LOGGER.isDebugEnabled())
                            sw.start();
                        addBufferedEdgeGeometry(points, minSplitLength, iter, detailedShape, goalEdge, bufferSize);
                        if (LOGGER.isDebugEnabled())
                            sw.stop();
                    } else {
                        addPoint(points, nodeAccess.getLon(nodeId), nodeAccess.getLat(nodeId));
                    }
                }
            } else {
                if (minCost < isolineCost && maxCost >= isolineCost) {
                    if (LOGGER.isDebugEnabled())
                        sw.start();
                    addBorderEdgeGeometry(points, isolineCost, minSplitLength, iter, maxCost, minCost, bufferSize);
                    if (LOGGER.isDebugEnabled())
                        sw.stop();
                }
            }
        }
        if (LOGGER.isDebugEnabled())
            LOGGER.debug("Expanding edges " + sw.getSeconds());

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

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

        return new GeometryCollection(geometries, geometryFactory);
    }
}