首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >在图中找到最近的边

在图中找到最近的边
EN

Stack Overflow用户
提问于 2013-11-10 17:13:59
回答 5查看 3.7K关注 0票数 20

我想在图中找到最近的边。请考虑以下示例:

图1:黄色:顶点,黑色:边缘,蓝色:查询点

通用信息:图包含大约1000万个顶点和大约1500万个边。每个顶点都有坐标。边由两个相邻的顶点定义。

最简单的解决方案:,我可以简单地计算出从查询点到图中每一个其他边缘的距离,但是这会非常慢。

思想与难点:,我的想法是使用一些空间索引来加速查询。我已经实现了一个kd-树来查找最近的顶点。但如图1所示,与最近顶点相关的边不一定是与查询点最近的边。我会得到边缘3-4而不是更近的边缘7-8。

问题:是否有一种算法可以在图中找到最近的边?

EN

回答 5

Stack Overflow用户

发布于 2013-11-21 08:19:10

一个非常简单的解决方案(但可能不是最简单的解决方案)是根据边界框为您的所有边缘使用https://en.wikipedia.org/wiki/Quad_tree。然后,您只需提取与查询点最近的一组边缘,并对其进行迭代以找到最接近的边缘。

由四叉树返回的提取的边缘集应该比原来的1500万条边缘小很多,因此迭代成本要低得多。

四叉树是一种比R树更简单的数据结构.它相当常见,应该可以在许多环境中随时使用。例如,在Java中,JTS拓扑套件有一个可以轻松包装以执行此任务的结构QuadTree

票数 4
EN

Stack Overflow用户

发布于 2013-11-10 21:46:13

有一些空间查询结构适合于其他类型的数据,而不是点。最普遍的是“R-树”结构(以及它的许多变体),它将允许您存储线段的边界矩形。然后,您可以从查询点向外搜索,检查边界矩形中的段,并在最近的剩余矩形比目前遇到的最接近的直线更远时停止。当有许多长线段重叠时,这可能会有很差的性能,但是对于像这里这样的PSLG来说,这是不应该发生的。

另一种选择是使用段来定义BSP树,并从您的点向外扫描以找到所有的“可见”行。如果你的观点能看到很多边缘的话,这将是个问题。

票数 3
EN

Stack Overflow用户

发布于 2013-11-10 17:56:11

您可以计算voronoi图并对每个voronoi单元单元运行一个查询。您可以细分voronoi图以获得更好的结果。您可以组合度量图和voronoi图:http://www.cc.gatech.edu/~phlosoft/voronoi/

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/19892564

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档