logo标签列表

在图中找到最近的边

algorithmgeometrycomputational-geometrygraph-algorithm
20

我想要找到图中最近的边。考虑以下示例： yellow: vertices, black: edges, blue: query-point

图1： 黄色：顶点，黑色：边，蓝色：查询点

基本信息： 该图包含约 1000万个顶点 和约 1500万条边。每个顶点都有坐标，而边是由相邻的两个顶点定义的。

简单解决方案： 我可以简单地计算查询点与图中每条其他边的距离，但这会非常慢。

思路和困难： 我的想法是使用一些空间索引来加速查询。我已经实现了kd树以查找最近的顶点。但正如图1所示，与最近顶点相邻的边不一定是离查询点最近的。我将得到边3-4而不是更近的边7-8。

问题： 在图中查找最近的边是否有算法？

我假设你的所有边都是直线？ - amit
是的，它们是直的。 - user2033412
1
顶点具有坐标，例如笛卡尔坐标系的纬度/经度在一个正方形网格上？还是其他特定领域的坐标系统？极坐标？ - inquisitive
纬度/经度坐标。该图是一个国家大小的道路网络。边缘可能短于1000米。 - user2033412
你好，你解决了这个问题吗？我现在被困在这里了。 - Sairam
显示剩余2条评论
5个回答
4

一种非常简单的解决方案（但也许不是复杂度最低的解决方案）是针对所有基于它们的边界框的边使用四叉树。然后，您只需提取最接近查询点的一组边缘，并迭代这些边缘，以找到最接近的边缘。

四叉树提取的边缘集应比原始的1500万条边缘小得多，因此迭代过程要便宜得多。

四叉树是一个比R树更简单的数据结构。它相当普遍，应该在许多环境中都可以使用。例如，在Java中，JTS Topology Suite有一个结构QuadTree，可以轻松地包装以执行此任务。

1
嘿，我计划使用四叉树实现最近邻算法来查找最近的边缘。然而，我没有完全理解你的解决方案。 “基于它们的边界框，为所有边缘使用四叉树” 我已经将所有节点存储在四叉树中。您是建议我将边缘存储在单独的四叉树中吗？ 谢谢！ - SLearner
3
有些空间查询结构适用于点之外的其他类型数据。最通用的是“R树”结构（以及它的许多变体），它允许您存储线段的边界矩形。然后，您可以从查询点向外搜索，在边界矩形中检查线段，并在最近的剩余矩形比迄今为止遇到的最近线段更远时停止。当有许多重叠的长线段时，这可能会导致性能不佳，但对于像您这样的PSLG，这不应该发生。
另一个选择是使用线段定义BSP树，并从您的点向外扫描以找到所有“可见”的线。如果您的点可以看到许多边缘，则这反过来将成为问题。
R-Tree真的是处理这种问题的有效方法吗？我认为由于它的一般性方法，与专门针对直线的方法相比，性能会较差。 - user2033412
很难在没有尝试过的情况下做出判断。我的猜测是，在您的使用情况中，由于重叠部分很少且片段较短，这应该是可以的。这是我首先尝试的方法，然后再考虑更奇特的解决方案。 - Sneftel
我曾认为四叉树仅适用于点数据（如kD树）。但显然，确实存在一种适用于边缘的变体：http://en.wikipedia.org/wiki/Quadtree#Edge_quadtree。这是你所指的吗？ - user2033412
那么想法就是为四叉树中的每个单元格存储重叠该单元格的边缘？如果有两条重叠的边缘，那么（最后一级）单元格将包含这两条边缘？ - user2033412
你能再详细解释一下吗？我不太明白这个问题。我已经阅读了这个问题：https://dev59.com/F1fUa4cB1Zd3GeqPG1AO，但是我还是有困难理解。谢谢。 - Micromega
我仍在大量阅读这个主题。一旦我有了可行的东西，我会立即告诉你。如果有人有一些好的链接，请发帖！ - user2033412
1

您可以在长边上插入额外的顶点，以基于最近的顶点获得一些近似值..

1

没有证据：
您可以使用约束性德劳内三角剖分开始，这是一种考虑现有边缘的三角剖分。例如，CGAL或Triangle可以实现此功能。对于每个查询点，确定它属于哪个三角形。然后，您只需要检查接触该三角形角落的边缘即可。
我认为这在大多数情况下应该有效，但肯定会出现一些特殊情况，例如当存在许多没有任何边缘的顶点时，因此至少必须删除这些空顶点。

1
2
PSLG线段的沃罗诺伊图是计算起来非常困难的，会导致各种数值精度问题。它也不是一种适合于高效点定位查询的结构，因此仍需要额外的空间剔除结构。我同意这是“正确的解决方案”，但它不太可能是最实用的解决方案。 - Sneftel
一个组合...什么的？那个链接里有一些漂亮的图片，但我不明白它们的基本结构如何与OP的问题相关。他们正在使用基于Voronoi的函数来着色像素。这对于定位最近的边缘毫无用处。 - Sneftel
@Sneftel：你可以使用分层聚类，然后计算每个层级的Voronoi图。这将会得到一个Voronoi树？ - Micromega
如果黄色折线是静态的（或至少移动缓慢），那么这就是答案。如果每个点查询都针对不同的折线集，则Voronoi图仅代表不必要的开销。 - gordy
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接