在图形中查找最近的边 [英] Find nearest edge in graph

问题描述

我想找到图形中最接近的边.考虑以下示例:

I want to find the nearest edge in a graph. Consider the following example:

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

常规信息:该图包含大约 1000万个顶点和大约 1500万个边.每个顶点都有坐标.边缘由两个相邻的顶点定义.

General Information: The graph contains about 10million vertices and about 15million edges. Every vertex has coordinates. Edges are defined by the two adjacent vertices.

最简单的解决方案:我可以简单地计算出查询点到图中每个其他边的距离，但是那太慢了.

Simplest solution: I could simply calculate the distance from the query-point to every other edge in the graph, but that would be horribly slow.

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

Idea and difficulties: My idea was to use some spatial index to accelerate the query. I already implemented a kd-tree to find the nearest vertex. But as Figure 1 shows the edges incident to the nearest vertex are not necessarily the nearest to the query-point. I would get the edge 3-4 instead of the nearer edge 7-8.

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

Question: Is there an algorithm to find the nearest edge in a graph?

推荐答案

一个非常简单的解决方案(但可能不是复杂性最低的解决方案)将是使用

A very simple solution (but maybe not the one with lowest complexity) would be to use a quad tree for all your edges based on their bounding box. Then you simply extract the set of edges closest to your query point and iterate over them to find the closest edge.

四叉树返回的提取的边缘集应该比原始的1500万个边缘小许多因素，因此迭代所需的成本要低得多.

The extracted set of edges returned by the quad tree should be many factors smaller than your original 15 million edges and therefore a lot less expensive to iterate through.

与R树相比，四叉树是一种更简单的数据结构.它相当普遍，在许多环境中都应该容易获得.例如，在Java中， JTS拓扑套件具有结构 QuadTree >可以很容易地包装起来以执行此任务.

A quad tree is a simpler data structure than the R-tree. It is fairly common and should be readily available in many environments. For example, in Java the JTS Topology Suite has a structure QuadTree that can easily be wrapped to perform this task.

这篇关于在图形中查找最近的边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！