坐标略有不同的列表中的交叉引用

Question

我想做一些非常类似于这里提出的问题：

Comparing two lists of coordinates in python and using coordinate values to assign values

也就是说，我有两个坐标列表（比如，x和y），如果（x，y）坐标与列表1中的（x，y）坐标匹配，我想从列表2中提取一个数量。你知道吗

现在，上面链接的问题中的答案可以很好地解决这个问题，只要坐标正好匹配

不过，我想解释一下可能的细微变化。所以，假设在任一坐标中都有一个很小的偏差dx或dy。假设我说，“对于dx<R，我认为这些坐标是相同的。”我该如何把它放到代码中呢？记住上面链接中已经给出的解决方案（当然，也可以是另一个创造性的解决方案）。你知道吗

注：对于快速和肮脏的解决方案（双for循环）这是相对容易的。用公认答案中给出的O（n）解更棘手，这正是我要找的。你知道吗

Answer 1

这绝对是一个计算几何算法。您可以将其重新格式化如下：给定平面中的一组点，为所有点P找到距离<= R的所有点的集合（相对于Chebyshev distance，前提是dx <= R和dy <= R必须发生）。你知道吗

二次时间的解很简单：你只需要检查一个点是否在给定的平方上。然而，我认为基于哈希表的方法（在平均线性时间内运行）不容易适应。你知道吗

然而，O(n log n)中的解决方案是可以想象的（尽管它可能由每个正方形中的点数决定：我假设R非常小，因此在给定的正方形中平均只有常量点数）。你知道吗

为此，您可以调整sweep-line algorithm。首先，您可以通过只考虑与输入中给定点对应的x和y来“离散化”坐标（这用于对坐标而不是点发出请求，同时仅根据输入中的点数保持复杂性）。你知道吗

之后，您可以根据点的x坐标对点进行排序。事实上，最好在x+r和x-r处为每个点添加“事件”（您也可以在x上放置一个事件，以便考虑每个点，而不是在不同的数据结构中进行扫描），对应于正方形的左角和右角。浏览这些事件，在按y坐标（*）排序的二叉搜索树中遇到左角时添加点，在读取右角事件时删除点。你知道吗

因此，在给定的时间，您的树正好包含与当前事件相关的点(x, y)和|x-xcurrent| <= R。当你得到一个点的时候，你只需要找到集合中的所有点(x, y)就当前事件验证|y-ycurrent| <= R。你知道吗

（*）事实上，使用Fenwick trees这样的数据结构是可能的，它比二进制搜索树这样的复杂数据结构更容易“从头开始”编码，并产生更低的常量。你知道吗