Is it possible to get the points used for the convex hull in osm2po?

Question

I have a non-convex hull algorithm that I want to use for an app. With OSM2PO, it's possible to get a convexHull, but is there a way to get the points before the hull is constructed?

More, it would be awesome for me if I can get only the points that are "path end", I mean points that are part of segments that are connected to no more than one other segment.

(If you're intererrested by the non-convex hull algorithm, aka Alpha-shapes, I can share...)

---

Thanks for your quick answer, but I don't understand well your solution. I've seen this table, and it might be helpfull but I don't see how to query PGSQL (pass it millions indices to check ?) and my aim is to avoid PGSQL.

I'dont know how you dit it but when you traverse the graph, there's probably something that say "Hey stop traversing this branch, you've reached the max cost or this branch has no more points". It should be possible to grab these "last" points, don't you think ?

In order to be sure we understand well, here's a little example.

Imagine this "graph" :

                       7
                      /
                    6
                   /
1---2---3---5---8----9---10
           |
           4

router.getVisited() will give me 1,2,3,4,5,6,7,8,9,10.

My dream : only get 1,4,7,10

Hope you can help me. Many thanks again.

(sorry for answering my own question but too many chars to be posted as a comment...)

Answer 1

Route with an invalid targetId (0), so the Dijkstra can expand to {maxcost}

router.traverse(graph, sourceId, 0, {maxcost}, params);

in order to collect all visited vertices call

int[] vs = router.getVisited()

If you need the ConvexHull pass to

Utils.convexHull(vs, lats, lons)

lats and lons are retrievable from

graph.getLats() and graph.getLons()

Answer 2

This should do the trick:

import java.lang.reflect.Field;
import java.util.Arrays;
import java.util.Properties;

import de.cm.osm2po.routing.DefaultRouter;
import de.cm.osm2po.routing.Graph;

public class MyRouter extends DefaultRouter {

    private double maxCost;
    private int[] borderEdges;
    private int nBorderEdges;

    public int[] getBorderEdges() {
        return Arrays.copyOf(this.borderEdges, this.nBorderEdges);
    }

    @Override
    public void traverse(Graph graph, int sourceId, int targetId,
            float maxCost, Properties params) {

        this.maxCost = maxCost;
        this.borderEdges = new int[0x400];
        this.nBorderEdges = 0;

        super.traverse(graph, sourceId, targetId, maxCost, params);
    }

    @Override
    protected double calcEdgeCost(int edgeIdx) {
        double edgeCost = super.calcEdgeCost(edgeIdx);

        if (getCurrentCumulatedCosts() + edgeCost > this.maxCost) {
            if (this.borderEdges.length == nBorderEdges) { // ArrayOverflow
                this.borderEdges = Arrays.copyOf(
                        this.borderEdges, this.borderEdges.length * 2);
            }
            this.borderEdges[nBorderEdges++] = edgeIdx;
        }
        return edgeCost;
    }

    /**
     * Cumulated costs to the current vertex inside the PriorityQueue.
     * There is no interface to get it, so I use dirty reflection.
     * For simplicity reasons I've put the ReflectionField-construction
     * in here.
     * 
     * @return costs of the current path.
     */
    private double getCurrentCumulatedCosts() {
        try {
            Field field = DefaultRouter.class.getDeclaredField("pqrCostR");
            field.setAccessible(true);
            double currentPathCosts = field.getDouble(this);
            return currentPathCosts;
        } catch (Exception e) {
            throw new RuntimeException("Sth. went wrong here");
        }
    }

}