如何更有效地找到最近的线段到特定点？ [英] How to find the nearest line segment to a specific point more efficently?

问题描述

这是我经常遇到的问题，我正在寻找一种更有效的方法来解决它。看看这张照片：

This is a problem I came across frequently and I'm searching a more effective way to solve it. Take a look at this pics:

让我们说你想要找到从红点到线段a _n 的最短距离。假设您只知道段和点的起点/终点（x，y）。现在这可以在O（n）中完成，其中n是线段，通过检查从点到线段的每个距离。这是IMO无效，因为在最坏的情况下，必须进行n-1次距离检查，直到找到正确的一个。

Let's say you want to find the shortest distance from the red point to a line segment a_n. Assume you only know the start/end point (x,y) of the segments and the point. Now this can be done in O(n), where n are the line segments, by checking every distance from the point to a line segment. This is IMO not effective, because in the worst case there have to be n-1 distance checks till the right one is found.

这可能是一个真正的性能问题n = 1000 fe （这是一个可能的数字），特别是如果距离计算不仅仅是由毕达哥拉斯定理在欧几里德空间中进行，而是通过诸如半程方程式或Vincenty's的测地方法。

This can be a real performance issue for n = 1000 f.e. (which is a likely number), especially if the distance calculation isn't just done in the euclidean space by the Pythagorean theorem but for example by a geodesic method like the haversine formula or Vincenty's.

这是在不同情况下的一般问题：

This is a general problem in different situations:

• 顶点半径内的点是否


• 哪一组顶点最接近点？


• 线段是否被线段包围？

为了回答这些问题，我知道的唯一方法是O（n）。现在我想知道如果有一个数据结构还是一个不同的策略来更有效地解决这些问题？

To answer these questions, the only approach I know is O(n). Now I would like to know if there is a data structure or a different strategy to solve these problems more efficiently?

为了简化：我正在寻找一种方式，在我开始我的距离计算之前，线段/顶点可以以某种方式过滤以获得一组潜在候选者。某些东西可以降低O（m）的复杂度，其中m < n。

To make it short: I'm searching a way, where the line segments / vertices could be "filtered" somehow to get a set of potential candidates before I start my distance calculations. Something to reduce the complexity to O(m) where m < n.

推荐答案

可能不是一个可以接受的答案，但太长的评论：这里最合适的答案取决于你的细节没有提出这个问题。

Probably not an acceptable answer, but too long for a comment: The most appropriate answer here depends on details that you did not state in the question.

如果您只想执行一次，那么将无法避免线性搜索。但是，如果您有一组固定的行（或一组不会随时间变化太大的行），则可以使用各种技术来加速查询。这些有时被称为空间指数，如四叉树。

If you only want to perform this test once, then there will be no way avoid a linear search. However, if you have a fixed set of lines (or a set of lines that does not change too significantly over time), then you may employ various techniques for accelerating the queries. These are sometimes referred to as Spatial Indices, like a Quadtree.

您必须期望在查询时间和内存消耗之间进行权衡，或查询时间和更新所需的时间当给定的一组行变化时的数据结构。后者还取决于是否是一个结构更改（添加或删除的行），或者是否只有现有行的位置更改。

You'll have to expect a trade-off between several factors, like the query time and the memory consumption, or the query time and the time that is required for updating the data structure when the given set of lines changes. The latter also depends on whether it is a structural change (lines being added or removed), or whether only the positions of the existing lines change.

这篇关于如何更有效地找到最近的线段到特定点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！