问题标签 [space-partitioning]

在处理了将 Bezier 补丁转换为三角形之后，我需要进行二进制空间分区，以便使用 Painter 算法绘制投影的三角形。

我已经实现了来自 Wikipedia 的算法，对数学有很大帮助。

但它正在制作一棵查理布朗树！也就是说，大多数节点都有一个完全空的分支。整个策略都是错误的。由于茶壶基本上是球形的，因此整个形状仅位于任何特定组件三角形的一个“边”上。

所以我想我需要像苹果核一样排列的分区平面：所有平面都通过 y 轴的线。但我有点偏离书本，你知道吗？分割茶壶的最佳方法是什么？

这是我的 bsp-tree 生成器。它使用链接问题中发布的其他功能。

编辑：额外的杂耍以避免 dictstackoverflow。此处提供完整程序（需要mat.ps和teapot）。数值输出显示了正在构建的树节点的深度。

输出：

我在 3 维空间中有很多点（+100,000）。我需要使用最近邻和范围查询。首先我使用了 kdtree (k=3) 但每个点都有一个速度属性。它们的位置不是静态的，它们会改变它们的位置。问题从这里开始。使用旧位置进行最近邻和范围查询很容易。但我必须根据他们的速度计算他们的新位置。在计算出他们的新位置后，我必须找到最近的邻居并在范围内搜索。

每次这些点改变它们的位置时，我都必须更新 kdtree，但这很昂贵。它让我慢下来。对于这种情况，您有什么建议或有更好的数据结构吗？

这里似乎有一个类似的问题，但我对答案的清晰性和实用性都不满意。在最近的一次采访中，有人问我将存储我的大量浮点数的数据结构，以便我为自己或最近的邻居查找新来的。我说我会使用二叉搜索树，并尝试使其平衡以实现 O(log n)。

然后问题扩展到两个维度：我将使用什么数据结构来存储大量 (x,y) 对，例如地理坐标以便快速查找？我想不出一个令人满意的答案，当扩展到 K 维时完全放弃了。直接使用使用坐标值来“分割”空间的 k 维树似乎不起作用，因为靠近原点但在不同象限内的两个接近点可能最终落在很远的叶子上。

采访结束后，我想起了很好地划分 K 维空间的 Voronoi 图。使用什么数据结构实现这一点的最佳方法是什么？如何进行查找？我觉得这个问题在计算机科学中是如此普遍，以至于现在它甚至有一个专门的数据结构。

我目前正在一个高效的计算引擎中工作，用于 CPU 和 GPU 中的粒子模拟。我最近一直在研究八叉树，我设法为空间中的粒子编写了一个八叉树的工作版本，并且还有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格（STL 对象），以便我也可以处理粒子和对象三角形之间的碰撞。我很困惑如何以有效的方式将三角形插入到我已经创建的八叉树中？请提出实现这一目标的方法。如果这有帮助，我正在使用 C++。已经谢谢了。

我目前正在尝试实现四叉树来划分地图。过去一周我进行了研究，但并不成功。我正在尝试将地图划分为各种矩形，这些矩形将是地图的不同区域，具体取决于人的位置。我被卡住了，因为由于某种原因，我的树无法超过 3 的深度。下面的代码是我的四叉树类。我附加了另外两个类，QuadNode 和 QuadRectangle。QuadNode 是树中的节点，而 QuadRectangle 是将成为玩家周围区域的矩形。

四叉树：

四节点：

四边形：

我为这里的代码量道歉。我已经被困了几天，我不知道从这里去哪里。

我在具有周期性边界条件的 D 维空间中有 N 个点的点云，其中 N 的范围可以从 500 到 10^8，D 的范围可以从 1 到 20。点的分布变化很大，从完全均匀到非常聚集一起。对于点云中的每个点，我需要找到与该点最近的 k 个邻居。我还需要找出每个点的距离内存在多少个点，特别是 maxnorm 距离。我不需要知道半径内有哪些点，只知道有多少，但这将是一个很好的补充。

我尝试过 kd-trees，但它们不处理环绕边界，对于较大的树，复制是不可行的。此外，它在更高维度上会变慢。

我刚刚遇到 Vantage Point Trees，并尝试了一些代码，但它比 kd-tree 慢。虽然我找到的代码使用递归搜索方法，没有批处理。积极的一面是，它可以本地处理包装条件，因此不需要重复。

我将看看是否可以通过转换为迭代方法并查看是否可以批量搜索来从 VP​​ 树中挤出更多性能，但我有一个想法。所有这些数据结构都可用于查找任意查询点的最近邻居，而我的查询点仅限于点云中的点。我认为这个限制可能允许一些更高性能的结构（可能是导航网格？）。我尝试搜索可以处理此问题的结构，但我的 google-fu 让我失望了。所以只是想知道是否有人知道可以处理以下内容的数据结构：

• 处理小点数和大点数，即500-10^8点
• 处理多达 20 个维度
• 使用周期性边界（即平坦环面）
• 使用 maxnorm 距离（软要求。欧几里得可以给我一个我可以手动剔除的潜在列表，但最好使用 maxnorm）
• 可以找到k-NN到查询点以及找到与查询点的距离存在多少个点
• 查询点只是结构中的点，不是任意点
• 可以批量查询。即我需要为点云中的每个点找到第 k 个 NN。我还需要找出每个点 i 在 d[i] 中存在多少个点。也就是说，每个点都有不同的搜索半径。
• 不需要支持插入或删除。

谢谢

我面临一个关于将多边形“分区”/子集到区域（更大的多边形）中的问题，以便每个区域应该有不相交的有意义的元素。

例如，我们有以下区域/多边形。在给定时间，我们只知道一个区域的形式（现在假设为 R1）。很明显，L3 将属于 R1。L1，L2和P1怎么样？我考虑在它们周围创建边界框并检查东南坐标（minX 和 minY）是否属于 R1。这样，L1 将属于 R2，即使它甚至不与 R2 交叉。

你有什么具体的想法我应该研究这些算法或者如何解决这个空间分离问题​​？

我应该在地图上显示一组标记以指示附近的兴趣点。这些标记将通过单击打开公共聊天室，因此我认为用户在进入该房间之前应该看到有关每个标记的简短地址信息，而无需单击标记。但是，如果我在这个意义上更改标记图标，一些标记可能会发生冲突，如下所示：

我想要做的是显示尽可能多的没有碰撞的标记，并用一个非常小的标记（如点）替换这些碰撞的图标（并且没有地址信息）：

我通过执行 x 轴扫描算法来检测碰撞来获得这个结果，但不幸的是，如果一个标记在用户滚动地图后停止碰撞，或者它从屏幕上存在，或者另一个标记进入屏幕并开始与其他标记发生碰撞，或者用户滚动到一个全新的区域，.. 这个算法应该在每一个回合一次又一次地执行。为了消除大多数碰撞标记，我使用了 maps-utils 标记聚类，但我需要一种更艰苦的方法来克服这个问题。我考虑实现四叉树，但我不确定它是否是最好的方法。有什么建议吗？

例子：

我熟悉 BSP、KD-tree 和 BVH 来解决一般的射线原始相交问题。是否有更有效的算法和数据结构来查找仅一个球体和许多线段之间的交点？请注意，球体是查询对象。

我正在pygame中设计一个篮球模拟器。

我需要它发挥作用，以便如果一支球队的一名球员前面的空间是空的，他会向篮筐移动，如果不是，他会尝试以预定的机会成功越过防线越过所述障碍物。

我第一次遇到一个问题是因为我使用进攻球员 x 坐标并简单地将防守移动到 (x + 30)，如下所示：

然而，这引发了问题，因为尽管它有效，但在游戏循环的每个循环中都有一个短暂的时刻，其中防守移动（x 变化）并且进攻会认为这是“敞开的”：

现在我已经更改了我的代码，让玩家只有在没有障碍物的情况下才移动，这确实有效，但是一旦他遇到防守他就不会继续移动（即使我将他的越过他们的机会设置为 100%）......

有没有更有效（有效）的方法来解决这个问题？

请注意：

• 玩家必须在不受阻碍时移动
• 当被阻挡时，必须计算他的路径继续前进的概率
• 防守必须移动到进攻球员的前面而不是后面或上方（必须停止他们的x）

这是运行显示的代码完整代码的图片（myGame1.team2players[i] 是第 2 队的每个球员；第 2 队始终是球场右侧的球队（红色的“CAVS”）：

这是游戏的截图。红色是上面的第 2 队。代码应该对此有意义。