3

I am developing a car-sharing application and I want to check if the approach I have is correct. I am using Postgres with PostGIS.

I have a list of routes that users publish, where they indicate that they typically commute from a point A to a point B (i.e. I am going from Milan to Venezia). All those routes are saved in the database as polylines that represent user journeys.

Then I need to search all those routes giving an input route (the red line in the picture), looking for routes that intersect my input or are close by (let's say 10 km deviation).

My solution is to convert everything to linestrings and use the Hausdorff distance to get close paths. Since I am fairly new to this approach, before proceeding further I have some doubt:

  • Is this approach computationally feasible?
  • Does it take into account the direction of the two polylines?
  • Is it a good approximation of "similar" routes?
  • Are there optimizations I can do to improve the overall search?
Improve this question
7
  • Using line similarity measures like the Hausdorff- or Fréchetdistance (the latter would be the one that takes direction into account!) will likely not work for one nasty detail: similarity includes length differences. what's your base network data?
    – geozelot
    Oct 24 '19 at 10:26
  • What do you mean for base network data? To avoid length difference, I thought of cutting all the DB routes inside a rectangle that contains the searched route.
    – Pablosproject
    Oct 24 '19 at 12:45
  • ŵell, to get those routes stored as vector geometries you need a road network? or do you get those commuter routes as extracts from somewhere? the usage of those functions the way you describe is strongly bound to the simplicity of your data...I imagine the 'proper' way of doing this is to take a commute routes source and target location, and run a routing with every other commute routes src and trg as via points, and find those where the detour of the direct route is less than a threshold.
    – geozelot
    Oct 24 '19 at 14:54
  • Too many question and not enough detail, but, more or less: yes, no, almost certainly not, and yes. Hausdorff is actually a pretty horrible measure of similarity. You would probably want to come up with your own, specific to your problem, as Hausdorff is way too generic and has huge numbers of edge cases.
    – John Powell
    Oct 24 '19 at 15:56
  • Thanks for the comments. I get all the routes directly from an external service (kind of google maps) and I am saving directly that to the database. So the routing problem is not my problem in this case. As I imagine the algorithm (but let me know if I'm saying something impossible): 1 - Create a rectangle that contains the red route (+ some space) 2 - Search in the database of routes (polylines or linestring) the one that intersect the rect. 3 - On that subset I run the distance measurement and find similar path.
    – Pablosproject
    Oct 25 '19 at 7:55
2

Considering that you look at the whole project in a practical way, let's also not over complicate things with this...

I want to get a ride from A to B, and my ride wants to stick as close to their usual path as possible; neither of us cares about Hausdorff's lousy measurement as long as I keep my chocolate away from the seat covers and they keep their cloud rap music down..

So what this breaks down to is to find a 'blue route' where the start and end points of the 'red route' is within a given threshold:

SELECT a.*
FROM   <blue_routes_table> AS a
JOIN   <red_routes_table> AS b
  ON   ST_DWitihn(a.geom, ST_StartPoint(b.geom), <threshold>)
 AND   ST_DWithin(a.geom, ST_EndPoint(b.geom), <threshold>)
;

Imagine the letter A as our routes, where the /\ is the 'blue route' and - is the 'red route'; those routes are far from being similar, yet sharing a car would work out just fine for both.

Improve this answer
2
  • This is very simple, doesn't take anything else but proximity into account, is maybe still better than comparing the similarity of your LineStrings, but you will nevertheless very likely run into plenty of cases where this fails, so I suggest to do some intensive testing on your database.
    – geozelot
    Oct 25 '19 at 12:51
  • Ha ha ha, to the rap music. It is also possible that you might want to look at pgRouting, which definitely takes direction into account, and could be used to actually tell if two similar routes will actually take you to the same place ultimately. You can also include estimates of travel time in pgRouting. Finally, as far as optimizations are concerned, while I don't know the full inner workings, applications like Google Maps precompute a lot of the network, so if you are going from New York to San Fransicso you would only be searching from the start and end point in each city, not between them
    – John Powell
    Oct 25 '19 at 17:26
1

If you want to search for a linestring close to at most X km from another linestring, my best guess would be to use ST_Buffer: WHERE ST_Intersects(ST_Buffer(red_geom, 10000), blue_geom) and then you can for exemple use ST_Distance between the linestring to order your results.

It should be pretty fast, if you use index, but it depends of you case study (what is fast enough for you, how many linestrings, what is the median size of thelinestring, ...). I think you need to try it to see if it fits your needs.

Improve this answer
4
  • Thanks for your answer. ST_Buffer is only taking account the area in which I want to intersect my routes, right?
    – Pablosproject
    Oct 25 '19 at 8:09
  • ST_Buffer add a buffer around your red line, conserving the shape (it's like making it "fatter", see the postgis doc for visual exemples), so if you select with st_intersects, it only keep the blue line that are at most X km from any point of the red line (mathematical points, not the points of the linestring of course)
    – robin loche
    Oct 25 '19 at 10:29
  • for proximity searches, always use ST_DWithin!
    – geozelot
    Oct 25 '19 at 11:59
  • Yeah, as @ThingumaBob says, use ST_DWithin. ST_Buffer means the spatial index won't be used, so this will be horribly slow. Also, a line being close to another line, doesn't mean it is in any way similar. An L shape has two intersecting lines, but I don't think you would replace Goolge Maps if you based your routing on such logic. This really should be a comment, as it in no way answers the original questionS.
    – John Powell
    Oct 25 '19 at 12:16

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.