4

我有两组点A和B。

我想找到B中所有在r到A一定范围内的点，如果A中至少有一个点a到b的（欧几里德）距离，那么B中的点b就在r到A的范围内等于或小于 r。

两组点中的每一个都是一组连贯的点。它们是从两个非重叠对象的体素位置生成的。

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

但我是3D的。

做这个的最好方式是什么？

我目前使用一些 knn 算法（即 matlab 的 rangesearch）重复搜索A中的所有点B中的所有点，然后合并所有这些集合。但我觉得应该有更好的方法来做到这一点。我更喜欢matlab中的高级/矢量化解决方案，但伪代码也很好:)

我还想过将所有点写入图像并在半径为 r 的对象 A 上使用图像膨胀。但这听起来像是一个相当大的开销。

4

3 回答 3

4

您可以使用kd 树来存储 A 的所有点。

迭代 B 的点 b，并为每个点 -在 kd 树中找到 A 中最近的点（让它成为 a）。d(a,b)当且仅当距离小于时，点 b 应该包含在结果中r。

复杂性将是O(|B| * log(|A|) + |A|*log(|A|))

于 2013-08-06T17:08:28.923 回答
2

我通过首先过滤掉B中绝对远离A中所有点的点来增强@amit 的解决方案，从而进一步加快速度，因为即使在单一维度上它们也太远了（有点遵循问题中提到的一维解决方案） .

这样做将复杂性限制在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,:);
于 2013-08-06T21:18:13.833 回答
0

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). 希望这可以帮助。

于 2013-08-06T17:22:02.880 回答