问题标签 [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.
3d - 何时使用二进制空间分区、四叉树、八叉树?
我最近了解了二进制空间分区树及其在 3d 图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的材料。你什么时候会在 bsp 树上使用四叉树,反之亦然?它们可以互换吗?如果我有足够的信息来填写这样的表格,我会很满意:
什么是 A、B 和 C?
c++ - 优化截锥体剔除
我正在用 C++ 编写游戏,并且有一个由许多单独的网格组成的关卡,每个网格都有自己的顶点缓冲区。我正在使用 vmmlib(出色的免费 gl compat.vector/matrix 库)来创建我的截锥剔除器,并针对关卡中每个网格的边界球对其进行测试。可悲的是,我的关卡最多可以包含 800 个网格,并且每帧迭代所有这些网格很慢。优化代码的最佳方法是什么,这样我就不必在每次迭代时查看所有网格?截锥体内的边界体积?
search - 如何确定一个点在哪些长方体中而不遍历它们?
我有许多长方体,它们的位置和大小用 minimum 和 maximum和x
坐标给出(所以它们平行于主轴)。y
z
例如,我可能有以下 3 个长方体:
如果我然后给出一个点(例如(25.3,10.2,90.65)
),有没有办法快速确定我在哪个长方体?
显然我可以迭代所有的长方体,但可能有数百万个,我需要它比简单的迭代更快(O(log n)或更好的东西会很棒)。
这对我来说听起来像是一个“模糊匹配”类型的问题,我注意到Apache Lucene支持范围查询,但这似乎以相反的方式工作(在长方体中找到一个点,而不是在包含一个点的长方体中找到一个点)。
稍微复杂一点的是,维度的数量可能大于 3(可能高达 20);即我可能正在寻找“超长方体”而不是长方体。)
algorithm - 寻找最近邻的空间划分算法如何工作?
为了找到最近的邻居,空间分区是算法之一。它是如何工作的?
假设我有一组 2D 点(x 和 y 坐标),并且给定一个点 (a,b)。这个算法如何找到最近的邻居?
algorithm - 有什么比边界框更好的吗?
我有一个场景,我有 x 百万经度纬度点。
添加新的长/纬度点时,我想有效地知道哪些其他点在用户配置的距离参数内,因此我可以将它们添加到列表中。
有什么比边界框更好的吗?
我很想看到算法、参考和一些实现;)非常感谢!
algorithm - 数以千计的光线与 3D 空间中的三角形相交
有成千上万的射线和三角形。我们需要得到所有的交点。如果我们使用正常的两级循环,我们需要 O( mn) 时间复杂度。有没有办法将时间复杂度从 O( mn) 降低到 O(m* logn) 或 O(logm*n)?
此致,
algorithm - 如何在 n 维中执行空间分区?
我正在尝试将向量量化的实现设计为一个 c++ 模板类,它可以处理不同类型和维度的向量(例如 16 维字节向量或 4d 双精度向量等)。
我一直在阅读算法,我了解其中的大部分内容:
我想实现 Linde-Buzo-Gray (LBG) 算法,但我很难弄清楚划分集群的一般算法。我想我需要定义一个平面(超平面?),将向量分成一个簇,这样平面的每一侧都有相等的数量。
[编辑以添加更多信息] 这是一个迭代过程,但我想我首先找到所有向量的质心,然后使用该质心定义分割平面,获取平面每个边的质心,继续直到我获得了 VQ 算法所需的集群数量(迭代以优化以减少沿途的失真)。上面第一个链接中的动画很好地展示了它。
我的问题是:
一旦我有了质心,找到平面的算法是什么?
如何测试向量以查看它是否在该平面的任一侧?
algorithm - 空间划分算法
我有一组包含在矩形内的点。我想根据点密度将矩形拆分为子矩形(给出多个子矩形或所需的密度,以最简单的为准)。
分区不必精确(几乎任何比常规网格更好的近似值),但算法必须处理大量点 - 大约。2亿。然而,所需的子矩形数量要少得多(大约 1000 个)。
有谁知道任何可以帮助我完成这项特定任务的算法?
algorithm - 划分一维空间的算法
I 两组区间对应于相同的一维(线性)空间。这是一个粗略的视觉效果——实际上,有更多的间隔并且它们更加分散,但这给出了基本概念。
这些间隔中的每一个都包含信息,我正在编写一个程序来将一组间隔(红色)中的信息与另一组(蓝色)中包含的信息进行比较。
这是我的问题。我想将空间划分为n 个块,以便在每个块中完成大致相等数量的比较工作(工作量取决于该空间部分的间隔数)。此外,分区不应将任何红色或蓝色间隔分割成两个块。
所以输入是两组区间,期望的输出是空间的一个分区,使得
- 间隔(大致)均匀分布在分区的每个元素上
- 没有间隔与多个分区元素重叠
谁能建议这样做的方法或算法?
sql - 如何在关系数据库中存储二进制空间分区树?
我正在尝试将数据存储在关系数据库中的二进制空间分区树中。这个数据结构的棘手部分是它有两种不同类型的节点。第一种类型,我们称为数据节点,只是保存一定数量的项目。我们将能够容纳的最大项目数定义为t
。第二种类型,我们称之为容器节点,包含另外两个子节点。当一个项目被添加到树中时,节点会被递归,直到找到一个数据节点。如果数据节点中的项目数小于t
,则将该项目插入数据节点。否则,数据节点将拆分为另外两个数据节点,并由其中一个容器节点替换。当一个元素被删除时,必须发生相反的过程。
我有点迷路了。我应该如何使用关系模型来完成这项工作?