[SERVER-14948] Find Points near LineString Created: 18/Aug/14  Updated: 22/Mar/23

Status: Open
Project: Core Server
Component/s: Geo
Affects Version/s: 2.4.10, 2.6.4
Fix Version/s: features we're not sure of

Type: New Feature Priority: Minor - P4
Reporter: Neville Dipale Assignee: Backlog - Query Integration
Resolution: Unresolved Votes: 3
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-4339 Querying along a polyline Backlog
Assigned Teams:
Query Integration
Participants:

 Description   

I couldn't find an existing ticket, so let me try my luck.

I would like the ability to search for GeoJSON points that are within x meters of a GeoJSON Polyline. This is currently a costly query to implement outside of a database server, as I either have to; build a Polygon from a Polyline before using a $geoWithin, or hit Mongo multiple times using a $near, then filter all results for a distinct list of Points.

An approach that could be achieved in the server would be (likely a naive implementation):
1. make a LineString into a 'complex' LineString by reducing the distance between each point to a small distance. JS example: https://github.com/rwt-to/GeoJSON-Tools#complexify
2. convert the LineString into a Polygon by creating a circle out of each point in the LineString, then merging them (haven't found an effective way of doing that yet, my Polygons become huge)
3. use $geoWithin internally to find Points in the Polygon.

The second approach would be to perform step 1. above, then just use a $near for each point in the LineString, then filtering all the Points before returning a result.

In case I haven't explained it clearly, here's a SO question explaining the issue: http://stackoverflow.com/questions/19015861/find-points-near-linestring-in-mongodb-sorted-by-distance

There is likely a more efficient way, but I haven't had the time to try find it. I think the query would still perform decently if ran internally on Mongo, as either method above would use indices while avoiding round-trips.

Lastly, just for control, it seems like this is easily achievable in PostgreSQL : http://stackoverflow.com/questions/10286899/find-the-nearest-points-along-the-linestring-in-specified-distance-limit-and-ord



 Comments   
Comment by Joey Tuskan [ 21/Jan/19 ]

@Siyuan Zhou My use case is having a collection of line strings representing vehicle routes. A vehicle's driver may only be able to complete the next 4 hours of driving along their current route, Route A. Route A is time critical. I need to find another vehicle route, Route B (non-critical), that is close to Route A in order to fulfill Route A.

Using linear referencing, I slice the route into time segments of say 30 minutes. Then perform a $near query on each valid time segment point. But this does not match my use case. Because a circular or spherical distance without an excessively large query will have gaps without having a lot of overlapping $near queries. As well as, linear referencing being resource expensive. My query is not returning the entire data set.

Comment by Siyuan Zhou [ 21/Jul/15 ]

nevi_me, I don't think MongoDB supports this feature currently. The following query gives an error of "invalid point in geo near query $geometry argument".

coll.find({loc: {$near : {$geometry: {type: "LineString", coordinates: [[0,0],[1,1],[2,2]]}}}});

The functions mentioned in the description and its references on StackOverflow are actually different. To my understanding, there are at least 3 different queries.
1. Find points $within a buffer of line, where a buffer means the area that's within a certain distance from the line.
2. Find points $within a buffer of line, then sort the results according to the distance from the line.
3. Find points $within a buffer of line, then sort the results along the driving order along the road.

The first is a $within query, the second looks like a $near query and MongoDB doesn't have a counterpart of the third function. Could you please talk more about your use cases?

Thanks,
Siyuan

Comment by Neville Dipale [ 18/Jul/15 ]

This looks fixed in 3.0. I was able to query a point against a polyline using `$near` successfully. I think the issue can be closed. The last time I tried it I was still using 2.6.

Comment by Neville Dipale [ 20/Aug/14 ]

Understandable.

It's something I've wanted to efficiently implement, so I'll keep working on it in JavaScript and see how efficient I can make it. C++ isn't my forte so maybe if someone else is interested in doing that on Mongo they could then port the implementation and submit a pull request.

In terms of the $near interface, there shouldn't be significant/any change to how the API works externally. I reckon that the user should be able to specify a valid GeoJSON object, then Mongo should apply the existing logic for Points, and whatever the potential implementation would be for other types.

Logically, all of this is possible, the pain is just in implementing it outside of the server as one can't enforce query limits properly, and the roundtrip cost. If I want to select 100 closest points, but I pull 120 from Mongo, and 30 of them are duplicates, I would end up with 90. Similarly, if
I construct a Polygon out of the LineString range, I'd still need to calculate each Point's distance to the nearest boundary so I can filter by distance before applying limits.

Finally, to reduce the frequency of "I want this feature now or else ..." comments on issues that we follow, more work could be done on server-side scripting so that interested parties could roll out our own enhancements to Mongo without pulling a TokuTek. Probably something to consider for 2.10 or 3.0.

Comment by Greg Studer [ 20/Aug/14 ]

Generalized near-to-shape isn't a bad idea, but would require some significant work (and potentially some changes to the $near interface).

Generated at Thu Feb 08 03:36:27 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.