5

I'm currently facing some hard times trying to create a simplified line from a street geometry.
The data that I'm currently using comes from OpenStreetMap, using osm2pgsql.(Which means PostGIS, but I'm open to solutions that don't use it, or use external code, like C, JS, or whatever).

The problem: I need to create a simplified line string from given streets, however, most streets have multiple segments, such as: Line segment example

In this example, the street is forked and segmented, the GeoJSON is available here.

Dumping the points of the street is useful which could be converted to a line string, however, their order is messed up, causing bizzare line formations. I could partially solve this issue ordering by lon/lat or lat/lon, but in several cases of points in the same axis or due geometry angle, it does not order them properly, and thus, does not work for all streets.

Points and ordering examples

Few solutions I came up with:

  • Using ST_Buffer on every segment, joining, and ST_ApproximateMedialAxis on the resulting geometry. It didn't work because some streets, even with a generous buffer have all it's segments touching each other and also ST_ApproximateMedialAxis doesn't always result in a line string (Not a function fault, it's the expected behavior).
  • Ordering by LAT/LON ~ LON/LAT and creating a line from the result: Also didn't work as explained above.
  • Using ST_LineMerge: Nope, in regular streets it does work, but on forked or segmented streets, it fails, as explained here.
  • Iterating over points to create a line from every point nearest neighbor: Fails due the inability to find the real first and last points.

The hardest task so far is getting the farthest points from given set, to define the first and last point, getting this informations would solve the problem for me, but I'm clueless so far?

I thought about using ST_VoronoiPolygons, but I have no idea how to extract some result from that?

  • ST_DumpPoints returns a geometry_dump type of set that holds a path along the geom. what kind of simplification do you need exactly? – ThingumaBob Mar 17 at 8:45
  • @ThingumaBob A line string to be precise, keeping the overall street shape the most accurate possible. I've used ST_DumpPoints so I could attempt creating a line string from that points, however, as explained, they're not in order. – Nick LeBlanc Mar 17 at 12:34
  • Perhaps you could add a justification for why you want to do this? For instance, if you're looking to create a routable road network there are ways to use this input without destoying it. – Richard Law Mar 17 at 20:23
  • 1
    Sure thing @RichardLaw. Linear interpolation. – Nick LeBlanc Mar 17 at 21:45
3

I found a solution that fits my needs:

  1. Dump all points from a street geometry.
  2. Collect all points, create a Voronoi Diagram from the collection, then Dump the geometries to split them in individual, orderable polygons.
  3. Finally, order the polygons from their area, limit the result to 2 (2 biggest polygons, the first and last points)

This is what it looks line in the end:

SELECT *
FROM
  (SELECT (ST_DUMP(St_voronoipolygons(St_collect(dumpedpoints.geometry)))).geom AS polygons
   FROM
     (SELECT (St_dumppoints(geometry)).geom AS geometry
      FROM <your TABLE>
      WHERE <your conditions> ) AS dumpedpoints) AS voronoid
ORDER BY ST_Area(voronoid.polygons) DESC
LIMIT 2

With that in hand, I'm able to just query which point is inside the given polygons with ST_Within.

From that, having the first and last point, I wrote a JS that given a point, finds the nearest neighbor, store the data, go to the found neighbor, find his neighbor and repeat this until all points are iterated over.

/** Each point has a index inside, that's created sequentially, apart from the first OR last point, wich is always 0 so the code has the first iteration **/

const linePoints = [];
const copy = [...pointsCollection]; /** We create a iterable copy */

const points = copy.reduce(( Neighbor, Current, Index, Array ) => {

    /** Avoid iterations over nulls */
    if (Neighbor === null ) { return null } 

    /** If it's the last point, he doesn’t have any neighbors */
    if(Neighbor.index + 1 === Array.length) { return null }; 

    /** Remove itself from the points list, we do that so he doesn’t match with himself */
    pointsCollection.splice(pointsCollection.findIndex(item => item.index === Neighbor.index), 1) 

    /** Your choice function of GeoLib */
    let Nearest = nearestPoint(Neighbor, pointsCollection);
    /** Push to the final list */
    linePoints.push(Nearest);

    /** Set the Neighbor varible of the next iteration as the Neighbor found in this */
    return Nearest;

}, pointsCollection[0]); /** Set the initial value, in our case, the first or last point */

The result of that operation is a sequential array that can be used to create a line string.

  • What does the output look like? I'd imagine it's very jagged? Also, if the algorithm is "find start, find neighbour * n", then ST_StartPoint might be easier than calculating an entire voronoi and sorting by area? (I'm not sure how that works, actually.) Even on a split line, the line will almost certainly have a useful start and end. – Richard Law Mar 23 at 1:20
  • @RichardLaw Most data from OSM(At least the parts I'm using) comes from community contributions(That are visually/graphically useful, but poor on precision), the line start can be exactly where we expect and at same time can be in the middle of the geometry, this was the first issue I faced with this problem, thus it's a problem when dealing with a generalist solution that needs to work on every street I'm working with. The line is in fact jagged, but simplification like Douglas-Peucker Algorithm(or your favorite/adequate one) does solve the problem with proper calculation :) – Nick LeBlanc Mar 23 at 1:54
  • Maybe I'm just too thick to understand your solution, or I need some kind of visual explanation; I just don't understand how sorting your voronoi polygons by area achieves anything more advantageous than querying for the start/end vertices directly. But yes, perfectly generalised solutions for road networks are hard to come by, there is an extreme variety of edge cases. – Richard Law Mar 23 at 7:52
  • @RichardLaw ST_StartPoint and ST_EndPoint only accepts LineStrings, almost all streets in OSM are MultiLineStrings, in the original example of this question, this approach would not work right away, even if i converted it to a LineString using several approaches, the ST_StartPoint and ST_EndPoint will lead to incorrect results. As i explained early, however drew the line be it person or algorithm, took arbitrary starting/ending points, in the original example, the starting point is on the middle of it, the same can be said to the ending point. – Nick LeBlanc Mar 23 at 16:28
  • @RichardLaw Performance is in fact an issue(Not at all, 300ms the entire process above for each street, that can run in parallel on several cores and threads.), but i only need to calculate and store this data one single time, streets will hardly change their shapes, and if they do, i'll just recalculate it and store the changes :) – Nick LeBlanc Mar 23 at 16:31

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.