问题标签 [space-partitioning]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
8 回答
42969 浏览

3d - 何时使用二进制空间分区、四叉树、八叉树?

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

什么是 A、B 和 C?

0 投票
3 回答
2119 浏览

c++ - 优化截锥体剔除

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

0 投票
2 回答
1155 浏览

search - 如何确定一个点在哪些长方体中而不遍历它们?

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

例如,我可能有以下 3 个长方体:

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

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

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

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

0 投票
2 回答
3793 浏览

algorithm - 寻找最近邻的空间划分算法如何工作?

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

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

0 投票
3 回答
532 浏览

algorithm - 有什么比边界框更好的吗?

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

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

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

我很想看到算法、参考和一些实现;)非常感谢!

0 投票
6 回答
381 浏览

algorithm - 数以千计的光线与 3D 空间中的三角形相交

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

此致,

0 投票
2 回答
292 浏览

algorithm - 如何在 n 维中执行空间分区?

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

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

这里这里

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

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

我的问题是:

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

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

0 投票
8 回答
5059 浏览

algorithm - 空间划分算法

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

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

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

0 投票
1 回答
589 浏览

algorithm - 划分一维空间的算法

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

区间图

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

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

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

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

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

0 投票
1 回答
259 浏览

sql - 如何在关系数据库中存储二进制空间分区树?

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

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