用于在有限集中找到最接近点的高效算法 [英] Efficient algorithm for finding closest point in a finite set to another point

问题描述

我有一个约30k位置的列表L（写成经度/纬度对），以及约1m事件的列表E（位置写成经度/纬度对），每个位置出现在L点。我想用E中的每个事件标记它在L中的相应位置。但是L和E中的坐标系的取整方式不同 - E为小数点后五位，L为十三 - mdash;因此表面上相同的坐标实际上可能相差10 ^ -5度，或〜1米。 （L中的点至少相隔10米）

因此，我需要L中的每个点的最近点;明显的O（| L || E |）蛮力算法太慢了。 L与E相比足够小，即对L进行预处理并在E上预处理时间摊销的算法很好。这是一个深入研究的问题吗？我可以找到的链接是相关但不同的问题，例如找到一组中的一对点之间的最小距离。

可能相关： Voronoi图，尽管我看不出L如何预处理Voronoi图会节省我的计算时间。

解决方案

您的描述： 在E中与L中相同的点舍入到五位小数。因此，E中的每个点与L中的匹配偏离高达〜1米。 L中的点相距至少10米。

解决方案：将L坐标设置为与E相同的精度并匹配相同的对。

解释：四舍五入将每个点有效地映射到方形网格上的最近邻居。只要网格分辨率（四舍五入至小数点后约1米）低于L（〜10/2米）两点之间的最小距离一半时，您就可以走了。

为了获得最大的性能和利用| L | << | E |，您可能需要在L中的圆角坐标上构建散列映射，并在几乎不变的时间内匹配E中的每个点。总运行时间将受到O（| E |）的限制。

I have a list L of ~30k locations (written as longitude/latitude pairs), and a list E of ~1m events (with locations written as longitude/latitude pairs), each of which occurs at a point in L. I want to tag each event in E with its corresponding location in L. But the cooordinates in L and E are rounded differently—E to five decimal places, L to thirteen—so ostensibly identical coordinates can actually differ by ~10^-5 degrees, or ~1 meter. (Points in L are separated by at least ~10 m.)

I thus need the nearest point in L to every point of E; the obvious O(|L||E|) brute-force algorithm is too slow. L is small enough compared to E that algorithms that preprocess L and amortize the preprocessing time over E are fine. Is this a well-studied problem? The links that I can find are for related but distinct problems, like finding the minimal distance between a pair of points in one set.

Possibly relevant: Voronoi diagrams, though I can't see how preprocessing L into a Voronoi diagram would save me computational time.

解决方案

From your description:

• Each point in E is identical to a point in L rounded to five decimal places. Thus, each point in E deviates up to ~1 meter from its match in L.
• Points in L are separated by at least ~10 meter.

Solution: Round coordinates in L to the same precision of E and match equal pairs.

Explanation: Rounding effectively maps each point to its nearest neighbor on a square grid. As long as the grid resolution (~1 meter when rounding to five decimals) is lower than half the minimal distance between two points in L (~10/2 meters), you are good to go.

For maximum performance and exploiting |L| << |E|, you might want to build a hash map over the rounded coordinates in L and match each point in E in near constant time. Total runtime would then be limited by O(|E|).

这篇关于用于在有限集中找到最接近点的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！