问题标签 [space-partitioning]

我需要将静态大小的大矩形分割成小矩形的算法。对我来说完美的实现如下所示：

所以我需要算法GetRect和FreeRect方法。任何想法和链接将不胜感激。

我有一个问题，我需要一种非常有效的方法来查找给定体积内的对象。可以想象，对象被表示为具有 X-min、Y-min、Z-min 和 X-max、Y-max、Z-max 值的框。太空中可能有数百万个这样的对象，问题是在任意给定的用户提供的体积内找到对象。用户输入框的 X、Y 和 Z 值的最小值、最大值。

目前，我在 Oracle 数据库表中拥有所有这些对象，这些对象为 X、Y 和 Z 值的范围索引。任何查找对象的查询都涉及将给定的 X、Y 和 Z 值与对象值的比较。我发现性能并不令人满意，并且正在考虑使用内存算法来解决这个问题。此外，还需要找到完全进入、部分进入的对象。

谢谢艾

我一直在尝试在我的游戏中实现空间分区算法，但空间哈希和四叉树都不是我想要的。

我的关卡大小不应该有限制（只有 Int32 限制）。我需要一个不需要“级别宽度”和“级别高度”的空间分区算法。

我有许多移动的物理对象。我需要算法足够快以支持 500 多个对象。

有什么选择吗？

我有一个空间区域，二维，从(0,0)到(MAX_X, MAX_Y)。

在这个空间区域内，我画了一些线，它们与该区域的周长相交，并且它们可能彼此相交。通过这种方式，这些线将我的空间区域划分为子区域，如果将这些子区域相加，则给出整个空间区域。

在这片空间区域内，有一些点(x,y)。我必须确定

1. 构成由线条创建的所有空间子区域的所有顶点的坐标
2. 如果给定的空间子区域包含或不包含一个或多个点

我正在尝试用 java 编写代码，但语言并不是很重要。我不知道如何完成这两项任务。如果有人可以给我一个提示，我将非常感激。

我有一个包裹在边缘的二维地图。因此，如果您离开右边缘，您将重新出现在地图的左侧。其他三个边缘也是如此。

对于我用来查找点范围内的元素的 KDTree 来说，这是一个可继承的问题。通常你会检查超球面是否与超平面碰撞，看看你是否应该继续搜索树的另一边，但这种检查不适用于环绕边缘。

有什么方法可以修改 KD 树以使用甜甜圈 2D 空间？

我正在编写一个使用kd 树在二维空间中查找点的应用程序。在开发过程中，如果能够“看到”每个点周围的最近邻区，那就太好了。

在附图中，红点是 kd 树中的点，围绕每个点的蓝线界定了最近邻搜索将返回包含点的区域。

图像是这样创建的：

这个算法有两个问题：

• （更重要的是）我的（相当快的Core i7）计算机上它很慢。
• （不太重要）它很草率，你可以从不同宽度的蓝线看出。

一组点的这种“可视化”叫什么？

有哪些好的算法可以创建这样的可视化？

我阅读了有关空间分区的 R-Tree、kd-tree、边界间隔层次结构等。我发现这些数据结构对于空间查询很有用。虽然，他们做分区，但我不知道如何从数据结构中检索这些分区。所以，我的问题归结为“给定一个数字 N 和一个包含 X 个多边形的地图，我可以得到 N 个包含大约相等数量多边形的分区吗？”

我有一个由二进制空间分区树给出的 3d 卷。通常这些是由多边形模型制成的，并且分割的多边形已经存储在树节点中。

但我的不是，所以我没有多边形。每个节点都只有一个剖切面（例如，由法线和原点距离给出）。因此，树仍然代表一个实体的 3d 体积，由所有切割定义。但是，为了可视化，我需要这个体积的多边形网格。如何有效地重建它？

粗略的方法是将叶子的无限半空间转换为足够大的多面体（例如立方体）并将它们中的每一个向上推到树上，通过它通过的每个节点的平面切割它。这似乎非常昂贵，因为树可能是不平衡的（例如，如果愚蠢地由凸多面体制成）。有没有经典的解决方案？

_{（来源：hiveworkshop.com）}

在上图中，我将 20 个任意点分成 5 个簇。右边是一个定义最大集群大小的圆圈。右上角是每个集群的最大点数。我希望能够获取任意一组点 k 并将它们分成最大大小为 n 且最大半径为 r 的集群。我需要该算法来检索尽可能多的集群（在上面的示例中，尽可能多的 4 个集群）。任何给定点只能属于 1 个集群，并且集群不能重叠。

如果该算法可以向现有集合添加/删除点并更新集群，这也会很有帮助。

我完全不知道如何做到这一点。到目前为止，我最好的想法是计算点集的中心，然后使用这些中心进行二进制空间分区，但我希望使用这种方法的最好结果是均匀分布的集群。

任何帮助，将不胜感激 ：）。

编辑
不要重叠，因为区域形成的形状不与其他区域形成的形状相交，并且区域不位于其他区域的内部（例如圆圈中的圆圈）。在上图中，每个区域都有一个形状。这些形状都没有相交，并且没有区域位于另一个区域内。

我正在执行一些涉及数百万个原子系统的 MD 模拟。

我编写了一些代码来生成一个文件，该文件只是 XYZ 原子坐标的列表。现在我需要在原子之间产生键。如果两个原子彼此相距一定距离，则被认为是键。

示例 XYZ 文件：

所以我有五个原子。如果我的距离阈值为 2 个单位，那么我的债券列表将是：

（其中数字对应于 XYZ 文件中的坐标索引）。

生成此列表的简单方法是：

然而，这很快就达到了算法限制，即使在针对数百万个原子的高度优化的 C 语言中也很慢，至少在我将执行此过程的频率上如此。

我曾经写过一次光子映射器时，对空间分区数据结构的唯一经验是使用 kd-trees，所以我真的不知道这个问题的最佳解决方案是什么。我敢肯定，那里可能有一些最适合这个的东西。

我还应该提到我的模拟框是周期性的，这意味着 (0.5, 0, 0) 处的原子将与 (boxWidth - 0.5, 0, 0) 处的原子结合，距离阈值为 2。