问题标签 [quadtree]

我有一个非常大的点云（> 100000 个点），我想在其中检测平面排列。我决定使用八叉树将这些点分解为非常小的平面簇，然后合并共面的相邻簇。我已经用 C++ 编写了代码，可以将点云快速拆分成小的平面集群，但是如何有效地合并它们却让我望而却步……

我的Octree实现使用指针结构：有OctreeNodes 的数组OctreeNode* children[8]包含指向其子节点的指针，或者NULL如果它是叶节点，则为所有指针。

我的第一个想法是在每个OctreeNode对象中保留一个指向Plane对象的指针。在第一次分割点之后，八叉树中的每个叶子都会得到一个Plane代表叶子中包含的所有点的最小二乘拟合。然后我遍历树中的每个叶节点。对于每个叶节点，我检查它的每个相邻叶节点：如果邻居的平面应该与当前叶的平面合并，我调用Plane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane);创建一个表示两个节点中的点的新平面。

这就是我遇到麻烦的地方......我首先认为我可以简单地用新平面替换两个平面，即plane = newPlane; neighbor->plane = newPlane;完成（除了内存泄漏；我在真实代码中处理它们）。不幸的是，这在实践中不起作用。合并几个平面后，可能会有几个不同OctreeNode的 s 指向一个 s Plane，并且只需替换其中的指针，this->plane而neighbor->plane不是替换指向其旧平面的每个指针。

甚至当我第一次想出这个解决方案时，它似乎也很老套，现在它的缺陷更加明显。任何人都可以想出一种方法来修复我提出的合并方法，或者想出更好的方法吗？

谢谢

嗨，我在为 Android 使用非常大的 gpx 轨道时遇到了问题。我想将一小部分轨道添加到四叉树，只有这小部分绘制到显示器上。我真正的问题是如何为这个问题实现一个好的四叉树结构。谢谢，对语言错误感到抱歉，我的英语不太好。

全部，

有一些关于使用 Python 实现四叉树的示例，但我的问题是，有没有人知道用纯 Python 编写的类，就像我可以轻松包含在我的项目中的单个 .py 文件一样？这里列出了三个最受欢迎的包这些四叉树库中的任何一个有用吗？但由于运行它们所需的所有依赖项，我没有运气使用它们。我真的想要一些轻量级且使用起来相对简单的东西。我想通过传入整个地球的边界来调用脚本，然后从那里开始工作。myMethod((-180,-90,180,90))

谢谢，亚当

我在 Mathematica中实现了一个四叉树。我是使用像 Mathematica 这样的函数式编程语言编码的新手，我想知道是否可以通过更好地使用模式来改进它或使其更紧凑。

（我知道我也许可以通过修剪未使用的节点来优化树，并且可能有更好的数据结构，例如用于空间分解的 kd 树。）

此外，我仍然对每次添加新点时都复制整个树/表达式的想法感到不舒服。但我的理解是，对表达式进行整体操作而不修改部分是函数式编程方式。我将不胜感激有关这方面的任何澄清。

MV

编码

用法

输出

我有一组 100 到 200 个点 (x,y)。我必须检查哪些落在其他的特定距离内。整个程序的特定距离是固定的，比如 50。比如点 1 落在点 5、7、25、90、96、105 等的范围内。同样，点 2 落在 23,45 等范围内... 存储对象以通过 x,y 坐标定位

这里建议使用 QuadTree，但它可用于获取边界矩形内的所有点。但是如何获得边界圈内的所有点？有一种方法可以在最大距离内返回最接近纬度/经度的点，但是如何获取距离内的所有点？ http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int)

一种方法可能是在我得到它时从树中删除每个点，然后再次查询最近的点，直到我得到空值。这是唯一的方法吗？

我一直在研究四叉树及其在视频游戏代码中的碰撞检测中的用法。

但是，到目前为止，所有实现都依赖于 C++、C#、javascript 和 Lua 的面向对象特性来完成每个节点，而我完全不知道如何将其转换为原始 C。

目标是针对演员（不断移动）和地形（静态）测试多个对象（镜头）。然后是带地形的演员。由于我找不到可以用“纯”C 术语阅读的示例（即不使用方法或自引用对象），因此我什至无法掌握如何对其进行编码的基本思想，但我确实理解背后的思想算法。我不知道如何设置它，如何引用它，我应该使用什么数据类型，或者任何东西。我对 C++ 一无所知，这使得将其翻译成 C 是不可能的。

同样，我将使用地形贴图，我想做一些高或宽的地图，而不是完美的正方形。四叉树仍然适用于这样的地图吗？

此外，还会有许多移动元素，地形是唯一的静态部分（移动块或门等元素是单独的实体）。如果经常需要更新，是否值得使用四叉树？我什至需要将其设为全局数据吗？（也可以在某些函数内部伪造，然后在启用碰撞时传递）。在这种情况下我需要为它分配内存吗？

四叉树在游戏和其他地方被用作实体空间组织的优化http://en.wikipedia.org/wiki/Quadtree。

是否有用于 HTML5 Canvas 的四叉树示例？

我的应用程序从地图文件中加载约 100k 项（矩形）的集合，然后构建 MX-CIF 四叉树作为快速查找的索引。四叉树是在启动时构建的，它的内容在运行时不会改变。

（在 MX-CIF 四叉树中，项目由完全包含它的最小节点存储......内部和叶节点都可能包含项目）

在第一遍中，我找到了集合的外部范围，因此我知道根节点有多大。

在第二遍中，我将每个项目添加到完全包含它的最小节点。一旦一个节点传递了一定数量的项目，它就会被拆分，并且子节点会在新的父节点和 4 个子节点之间重新分配。

鉴于我已经预先准备好所有项目，我怎样才能更有效地构建树？

我需要知道这个算法是否是已知的：

这比较了SURF算法的结果。

1. 这是最近邻算法？看起来 func 正在搜索每个点的最近点。
2. 我可以使用 Quadtree 或 kd-tree 做同样的事情吗？
3. 有更好的算法来比较图像点并知道它们是否相同或相似？
4. 最好我想将它们存储到 mysql 中并构建一个 kd-tree 来比较所有图像中的 1 个图像，这可能吗？
5. RANSAC 对这项任务有什么用？
6. 有什么方法可以捕捉误报？

Let's say I have circular objects. Each object has a diameter of 64 pixels.

The cells of my quad tree are let's say 96x96 pixels.

Everything will be fine and working well when I check collision from the cell a circle is residing in + all it's neighbor cells.

BUT what if I have one circle that has a diameter of 512 pixels? It would cover many cells and thus this would be a problem when checking only the neighbor cells. But I can't re-size my quad-tree-grid every time a much larger object is inserted into the tree...