在立方体中查找 3D 点子集的算法复杂度

Question

给定一个 3D 整数数组，确定立方体中存在哪些整数的算法复杂度是多少？我假设这些点可以用许多并发数据结构表示，每个数据结构都按一个或多个维度排序。

我的直觉告诉我，给定一维点的排序数组，可以确定某个下限和上限之间的点的子集，例如 O(log(n)，但我将非常感谢其他人可以提供的任何见解关于这个概念(以及任何其他人可以提供的推广到多维案例的帮助!)。

Answer 1

如果您不熟悉所涉及的数学，我建议您首先在二维空间中使用矩形来解决此问题。这样，您就可以熟悉数学，这实际上只是一些基本的三角学。之后，提升到三个维度并不是很困难。

如果立方体(或矩形)是轴对齐的，问题就简单多了，所以您可能应该先这样做。有关确定所需旋转的示例，请参阅 How to calculate rotation angle from rectangle points? .

一旦您确定了旋转角度，您就可以将矩形平移到原点并通过执行此处接受的答案中的前两个步骤来旋转它:Drawing a Rotated Rectangle .

您现在有一个以原点为中心的轴对齐矩形。

最后，对于你的每一个观点:

1. 应用与矩形相同的平移和旋转。
2. 测试结果点中的 x 和 y 坐标是否在矩形内。这最多需要四次边界检查。
3. 如果点在矩形内，保存。

在二维中完成此操作后，您应该能够将这些概念应用于三维。

算法是O(n)，其中n是点数。