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" :


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...)

  • do you have a working Alpha-Shapes-Algo for osm2po?
    – Carsten
    Feb 7 '13 at 18:02
  • First, many thanks for helping me. I tried your custom router, but I probably missunderstood something. In order to make things easy, let's try with this very small OSM file : dl.dropbox.com/u/55433448/map.osm.bz2 (797ko uncompressed) When I ask for a 0.005 cost starting from node 1 the router says 12 nodes've been visited. Ok. Your getBorderEdges() method returns me an array with 9 indexes. But I don't understand what are these values. The first one is 52 but the total lats[] or lngs[] have a size of 31. So, what am I missing ? Note : you adviced me to email you but what's your email
    – Phiphou
    Feb 19 '13 at 12:12

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()
  • Thanks for your quick answer. But how to get only the "path end" ? Because if it's easy to make a convexHull from tons of points, a concaveHull algo is much more complicated and I can't plan to use it with more that 2 or 3k points. When dealing with PGSQL, the query returns me the segments and not just the vertices. So it's easy to merge the segment's sources and targets and then count the occurences and finaly keep just those who only appears once. (sorry for my bad english). Do you see a way for doing that ? Do you understand what I call "path end" ? Thanks again.
    – Phiphou
    Feb 7 '13 at 17:48
  • enable postp.1.class = de.cm.osm2po.plugins.PgVertexWriter in the config and you'll get another table of vertices where you'll find a "vertex-counter"
    – Carsten
    Feb 7 '13 at 17:59

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);

    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);

    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");
            double currentPathCosts = field.getDouble(this);
            return currentPathCosts;
        } catch (Exception e) {
            throw new RuntimeException("Sth. went wrong here");

  • Since Version 4.7.7 please call GeoUtils.convexHull(...) instead of Utils.convexHull(...)
    – Carsten
    Apr 5 '13 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.