找出另一个集合中与任意点距离在一定范围内的所有点

Question

我有两组点A和B。

我想要找到所有在距离r内的A中的点与B中的点，其中B中的点被认为是在范围r内的A，如果A中至少有一个点a到b的（欧几里得）距离等于或小于r。

这两组点都是一致的点集。它们是从两个非重叠对象的体素位置生成的。

在1D中，这个问题相当容易：所有在[min(A)-r max(A)+r]内的B中的点

但我在3D中。

最好的方法是什么？

我目前重复地搜索每个点A中的所有在范围内的B中的点，使用一些knn算法（即Matlab的rangesearch），然后合并所有这些集合。但我有一种感觉应该有更好的方法来解决这个问题。我更喜欢在Matlab中使用高级/向量化解决方案，但伪代码也可以 :)

我还考虑将所有点写入图像，并在半径为r的A对象上使用图像膨胀。但那听起来很麻烦。

- jan-glx

Answer 1

您可以使用k-d树来存储A中的所有点。

遍历B中的点b，并针对每个点-在k-d树中找到最近的点（称为a）。当且仅当距离d(a,b)小于r时，点b应包含在结果中。

复杂度将为O（|B| * log（|A|）+ |A| * log（|A|））。

- amit

---

谢谢。这正是我在寻找的。它将每个案例的运行时间从46秒减少到10秒。 - jan-glx

@YAK，能否分享一下实现这个的代码呢？我真的很需要。 - Tak

@user1460166 这是给你的。 - jan-glx

Answer 2

我通过强化 @amit 的解决方案并首先过滤掉B中明显远离A中所有点的点来进一步加速，因为它们在单个维度中甚至距离太远（类似于问题中提到的1D解决方案）。

这样做将复杂度限制为O（|B| + min（| B |，（2r/res）^ 3）* log（| A |）+ |A| * log（| A |）），其中res 是两个点之间的最小距离，从而将测试用例运行时间缩短到了5秒（从10秒，甚至更少）。

Matlab中的示例代码：

r=5;
A=randn(10,3);
B=randn(200,3)+5;

roughframe=[min(A,[],1)-r;max(A,[],1)+r];

sortedout=any(bsxfun(@lt,B,roughframe(1,:)),2)|any(bsxfun(@gt,B,roughframe(2,:)),2);
B=B(~sortedout,:);
[~,dist]=knnsearch(A,B);
B=B(dist<=r,:);

- jan-glx

Answer 3

bsxfun() 在这里非常有用。假设集合 A 中有10个点，集合B 中有3个点。你想让它们排列，使得单例维度在行/列上。我将随机生成它们以进行演示。

A = rand(10, 1, 3);                    % 10 points in x, y, z, singleton in rows
B = rand(1, 3, 3);                     %  3 points in x, y, z, singleton in cols

然后，所有点之间的距离可以分两步计算。

dd = bsxfun(@(x,y) (x - y).^2, A, B);  % differences of x, y, z in squares
d = sqrt(sum(dd, 3));                  % this completes sqrt(dx^2 + dy^2 + dz^2)

现在，您有一个包含A和B中点之间距离的数组。例如，A中第3个点与B中第2个点之间的距离应该是d(3, 2)。希望这可以帮助您。

- radarhead

---

谢谢你的建议！我也考虑过这个，但是它的规模是O（|A| * |B|），所以我认为它运行得更慢。但我会测试并报告结果。 - jan-glx

它确实需要61秒。无论如何，bsxfun对于机器学习用户来说是非常强大的工具，感谢您提到它。但是，accumarray、sort和obv.knnsearch可以提供更高的（因为算法）加速。 - jan-glx

@YAK 我看到了上面的kdtree答案，非常棒。今天我学到了新东西。感谢你提出这个好问题！ - radarhead