在mongodb中查找LineString附近的点(按距离排序) [英] Find points near LineString in mongodb sorted by distance

问题描述

我有一个点阵列，分别代表一条街道(黑线)和一些点，分别代表地图上的某个地点(红色点).我想查找指定街道附近的所有点，并按距离排序.我还需要能够指定最大距离(蓝色和绿色区域).这是一个简单的示例:

我考虑过使用$near运算符，但它仅接受Point作为输入，而不接受LineString.

mongodb如何处理此类查询?

解决方案

如前所述，Mongo目前不支持除Point之外的任何功能.您遇到过拳击手的概念吗? 1 几年前，它在Google地图上非常流行.给定您绘制的线，找到dist(x)内的停靠点.通过在直线上的每个点周围创建一系列边界框并搜索落在存储桶内的点来完成此操作.

我刚意识到Mongo仅适用于积分时，我偶然发现了你的问题，我认为这是合理的.

我已经有一些选择的方法(它们扩展了@mnemosyn在评论中所说的内容).使用我正在处理的数据集，它们全都在客户端上，因此我可以使用routeboxer，但出于性能方面的考虑，我想在服务器端实现它.这是我的建议:

1. 将LineString分解为单独的坐标集，并使用每个坐标集查询$near，合并结果并提取唯一的集.有一些算法可以通过减少点的数量来简化一条复杂的线，但是简单的算法很容易编写.

2. 与上述相同，但作为存储过程/函数.我还没有玩过Mongo的存储函数，也不知道它们与驱动程序的配合程度如何，但这可能比上面的第一个选项要快，因为您不必往返，并且取决于所用的机器.您托管了Mongo实例，计算速度可能会提高几微秒.

3. 在服务器端实施routeboxer方法(已在PHP中完成)，然后使用以上两种方法之一来查找作为$within生成的边界框的停靠点.哎呀，因为routeboxer方法返回矩形，所以可以将所有这些矩形合并为一个覆盖您的路线的多边形，然后对它执行$within即可. (@mnemosyn的建议).

4. 我想到了这一点，却忘记了，但是使用聚合框架可以实现上述某些目标.

这是我即将(希望)要进行的工作，我将根据最终的结果开源我的结果.

编辑:我必须提到1和2的缺陷，即如果您在一条线上有2个点(相距2公里)，并且您想要的点在您的线的1.8公里之内，显然您会错过线中该部分之间的所有点.解决方案是在简化时将点注入到行中(我知道，实现重新添加新点的目标是减少减少点的目标.)

3的缺点是，由于多边形中的某些点的距离可能会大于限制，所以它并不总是准确的，尽管差异不会占限制的很大百分比.

[ 1 ] google映射utils routeboxer

I have an array of points representing a street (black line) and points, representing a places on map (red points). I want to find all the points near the specified street, sorted by distance. I also need to have the ability to specify max distance (blue and green areas). Here is a simple example:

I thought of using the $near operator but it only accepts Point as an input, not LineString.

How mongodb can handle this type of queries?

解决方案

As you mentioned, Mongo currently doesn't support anything other than Point. Have you come across the concept of a route boxer? 1 It was very popular a few years back on Google Maps. Given the line that you've drawn, find stops that are within dist(x). It was done by creating a series of bounding boxes around each point in the line, and searching for points that fall within the bucket.

I stumbled upon your question after I just realised that Mongo only works with points, which is reasonable I assume.

I already have a few options of how to do it (they expand on what @mnemosyn says in the comment). With the dataset that I'm working on, it's all on the client-side, so I could use the routeboxer, but I would like to implement it server-side for performance reasons. Here are my suggestions:

1. break the LineString down into its individual coordinate sets, and query for $near using each of those, combine results and extract an unique set. There are algorithms out there for simplifying a complex line, by reducing the number of points, but a simple one is easy to write.

2. do the same as above, but as a stored procedure/function. I haven't played around with Mongo's stored functions, and I don't know how well they work with drivers, but this could be faster than the first option above as you won't have to do roundtrips, and depending on the machine that your instance(s) of Mongo is(are) hosted, calculations could be faster by microseconds.

3. Implement the routeboxer approach server-side (has been done in PHP), and then use either of the above 2 to find stops that are $within the resulting bounding boxes. Heck since the routeboxer method returns rectangles, it would be possible to merge all these rectangles into one polygon covering your route, and just do a $within on that. (What @mnemosyn suggested).

4. EDIT: I thought of this but forgot about it, but it might be possible to achieve some of the above using the aggregation framework.

It's something that I'm going to be working on soon (hopefully), I'll open-source my result(s) based on which I end up going with.

EDIT: I must mention though that 1 and 2 have the flaw that if you have 2 points in a line that are say 2km apart, and you want points that are within 1.8km of your line, you'll obviously miss all the points between that part of your line. The solution is to inject points onto your line when simplifying it (I know, beats the objective of reducing points when adding new ones back in).

The flaw with 3 then is that it won't always be accurate as some points within your polygon are likely to have a distance greater than your limit, though the difference wouldn't be a significant percentage of your limit.

[1] google maps utils routeboxer

这篇关于在mongodb中查找LineString附近的点(按距离排序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！