问题标签 [space-partitioning]

我最近了解了二进制空间分区树及其在 3d 图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的材料。你什么时候会在 bsp 树上使用四叉树，反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格，我会很满意：

什么是 A、B 和 C？

我正在用 C++ 编写游戏，并且有一个由许多单独的网格组成的关卡，每个网格都有自己的顶点缓冲区。我正在使用 vmmlib（出色的免费 gl compat.vector/matrix 库）来创建我的截锥剔除器，并针对关卡中每个网格的边界球对其进行测试。可悲的是，我的关卡最多可以包含 800 个网格，并且每帧迭代所有这些网格很慢。优化代码的最佳方法是什么，这样我就不必在每次迭代时查看所有网格？截锥体内的边界体积？

我有许多长方体，它们的位置和大小用 minimum 和 maximum和x坐标给出（所以它们平行于主轴）。yz

例如，我可能有以下 3 个长方体：

如果我然后给出一个点（例如(25.3,10.2,90.65)），有没有办法快速确定我在哪个长方体？

• 显然我可以迭代所有的长方体，但可能有数百万个，我需要它比简单的迭代更快（O（log n）或更好的东西会很棒）。

• 这对我来说听起来像是一个“模糊匹配”类型的问题，我注意到Apache Lucene支持范围查询，但这似乎以相反的方式工作（在长方体中找到一个点，而不是在包含一个点的长方体中找到一个点）。

• 稍微复杂一点的是，维度的数量可能大于 3（可能高达 20）；即我可能正在寻找“超长方体”而不是长方体。）

为了找到最近的邻居，空间分区是算法之一。它是如何工作的？

假设我有一组 2D 点（x 和 y 坐标），并且给定一个点 (a,b)。这个算法如何找到最近的邻居？

我有一个场景，我有 x 百万经度纬度点。

添加新的长/纬度点时，我想有效地知道哪些其他点在用户配置的距离参数内，因此我可以将它们添加到列表中。

有什么比边界框更好的吗？

我很想看到算法、参考和一些实现；）非常感谢！

有成千上万的射线和三角形。我们需要得到所有的交点。如果我们使用正常的两级循环，我们需要 O( mn) 时间复杂度。有没有办法将时间复杂度从 O( mn) 降低到 O(m* logn) 或 O(logm*n)？

此致，

我正在尝试将向量量化的实现设计为一个 c++ 模板类，它可以处理不同类型和维度的向量（例如 16 维字节向量或 4d 双精度向量等）。

我一直在阅读算法，我了解其中的大部分内容：

这里和这里

我想实现 Linde-Buzo-Gray (LBG) 算法，但我很难弄清楚划分集群的一般算法。我想我需要定义一个平面（超平面？），将向量分成一个簇，这样平面的每一侧都有相等的数量。

[编辑以添加更多信息] 这是一个迭代过程，但我想我首先找到所有向量的质心，然后使用该质心定义分割平面，获取平面每个边的质心，继续直到我获得了 VQ 算法所需的集群数量（迭代以优化以减少沿途的失真）。上面第一个链接中的动画很好地展示了它。

我的问题是：

一旦我有了质心，找到平面的算法是什么？

如何测试向量以查看它是否在该平面的任一侧？

我有一组包含在矩形内的点。我想根据点密度将矩形拆分为子矩形（给出多个子矩形或所需的密度，以最简单的为准）。

分区不必精确（几乎任何比常规网格更好的近似值），但算法必须处理大量点 - 大约。2亿。然而，所需的子矩形数量要少得多（大约 1000 个）。

有谁知道任何可以帮助我完成这项特定任务的算法？

I 两组区间对应于相同的一维（线性）空间。这是一个粗略的视觉效果——实际上，有更多的间隔并且它们更加分散，但这给出了基本概念。

这些间隔中的每一个都包含信息，我正在编写一个程序来将一组间隔（红色）中的信息与另一组（蓝色）中包含的信息进行比较。

这是我的问题。我想将空间划分为n 个块，以便在每个块中完成大致相等数量的比较工作（工作量取决于该空间部分的间隔数）。此外，分区不应将任何红色或蓝色间隔分割成两个块。

所以输入是两组区间，期望的输出是空间的一个分区，使得

• 间隔（大致）均匀分布在分区的每个元素上
• 没有间隔与多个分区元素重叠

谁能建议这样做的方法或算法？

我正在尝试将数据存储在关系数据库中的二进制空间分区树中。这个数据结构的棘手部分是它有两种不同类型的节点。第一种类型，我们称为数据节点，只是保存一定数量的项目。我们将能够容纳的最大项目数定义为t。第二种类型，我们称之为容器节点，包含另外两个子节点。当一个项目被添加到树中时，节点会被递归，直到找到一个数据节点。如果数据节点中的项目数小于t，则将该项目插入数据节点。否则，数据节点将拆分为另外两个数据节点，并由其中一个容器节点替换。当一个元素被删除时，必须发生相反的过程。

我有点迷路了。我应该如何使用关系模型来完成这项工作？