问题标签 [quadtree]

我有很多点（数十万个），我想检查哪些点在多边形内。对于一个相对较小的多边形（即，可能只包含数十或数百个点），我可以只使用多边形的边界框作为初始检查，然后对框内的这些点进行常规的多点检查. 但是想象一个大的（即，可能包含我的数千个点）、不规则形状的多边形。许多点将通过边界框检查，此外，多点检查将更昂贵，因为更大的多边形由更多点组成。所以我希望能够过滤掉大部分点，而不必进行完整的多点检查。

所以，我有一个计划，主要是我想知道我所描述的是否是一个众所周知的算法，如果是，它叫什么以及我可以在哪里找到它的现有代码。我不相信我所描述的是四叉树或 r-tree，我不知道如何搜索它。我在下面称它为“矩形树”。

这个想法是，要处理这些较大的多边形：

做一个“矩形树”预处理，矩形树的深度随多边形的大小而变化（即，允许更大的多边形有更多的深度）。矩形树将多边形的边界框分成四等分。它会检查每个四分之一矩形是否完全在多边形内，完全在多边形外，或者两者都不。在两者都不是的情况下，它不会递归地划分子矩形，以这种方式继续，直到所有矩形都完全在内部或外部，或者已经达到最大深度。所以这个想法是（a）制作这棵树的预处理时间，即使它本身会做几个多边形点检查，也是非常值得的，因为这个时间与要检查的点的数量相比相形见绌，

那个算法叫什么？代码在哪里？它实际上看起来并不难写，但我想在开始编码之前我会问一下。

我正在尝试为四叉树实现前向迭代器。不幸的是，我似乎无法在四叉树中找到任何关于遍历的资源。

谁能指出我正确的方向？

请推荐一本关于空间数据结构的书。我有兴趣Quadtrees and Octrees。

不久前我做了一个关于四叉树寻路的项目，我想提高它的性能。似乎使用 tesseral 算术来确定节点邻接（根据此页面，由不列颠哥伦比亚大学地理系提供）将比我目前使用的蛮力方法快得多（我正在检查共享边，这对于静态四叉树效果很好，但如果地图发生变化，开销会太大）。

我或多或少理解邻接算法部分所说的内容，但我不确定如何开始。我主要对 C# 感兴趣，但如果已经有一些源代码可以处理我可以查看的 tesseral 算术，那将是非常棒的，无论语言如何。否则，谁能给我一些关于处理加/减进位的指示？

我正在寻找一个 Java 库来以四叉树的形式操作完整的 n 元树。实际上，我只需要 n = 9，但我认为额外的普遍性对其他人来说是值得的。它适用于我正在开发的 GIS，其中 2D 区域被划分为 3^kx 3^k 网格上的元素（而不是使用四叉树时的 2^kx 2^k 网格）。特别是，我希望库有有效的方法来添加节点、遍历树和进行范围搜索。你知道这样的图书馆吗？

我在 Google 搜索中找不到一个，但我想在自己制作之前与大家仔细检查一下它的存在。

谢谢。

我一直在研究这个：

https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js

我相信我了解四叉树的一般概念，尽管我对它们的工作方式和上面的实现有两个问题：

1. 您是否必须每隔几毫秒重建整个树？在 Javascript 中，这不会非常慢吗？

2. 如果我有这样的东西：http://davzy.com/screenshots/skitched-20120318-180324.png，那么很容易找到同一个四边形中的其他点，但我有一个矩形可以击中 3 个不同的四边形，是有没有办法让它显示为所有 3 个四边形的孩子？

3. 在上面示例的 144 中，它说这个 Node.prototype._classConstructor = Node;，我只是好奇发生了什么。我认为原型是一种定义函数或变量以供将来在类中使用的方法，所以我不确定这一行的作用。

我有一个应用程序，用于显示和修改来自激光雷达文件的大量点云数据（每个文件最多几个 GB，有时同时加载）。在应用程序中，用户可以查看加载点的 2D 图像（从顶部）并选择要在另一个窗口中查看的配置文件（从侧面）。这再次涉及数百万个点，它们使用 OpenGL 显示。

为了处理数据，还有一个四叉树库，它可以工作，但速度极慢。它已经使用了一段时间，但最近激光雷达点格式发生了变化，并且 LidarPoint 对象需要添加许多属性（类成员），这导致它的大小增加，进而影响性能到几乎无法使用的水平（想想 5 分钟加载单个 2GB 文件）。

四叉树目前由指向 PointBucket 对象的指针组成，这些对象只是具有指定容量和定义边界（用于空间查询）的 LidarPoint 对象数组。如果超过桶容量，它将分成四个桶。还有一种缓存系统，当点数据占用过多内存时，它会导致点桶被转储到磁盘。如果需要，然后将它们加载回内存。最后，每个 PointBucket 都包含子桶/分辨率级别，它们保存原始数据的每个第 n 个点，并在根据缩放级别显示数据时使用。这是因为一次显示几百万个点，虽然没有必要那么详细，但速度非常慢。

我希望你能从中得到一张照片。如果没有，请询​​问，我可以提供更多详细信息或上传更多代码。例如，这里是当前（和慢速）插入方法：

现在我的问题是，您是否可以想办法改进这个设计？在处理大量无法放入内存的数据时，有哪些通用策略？如何使四叉树更有效率？有没有办法加快点的渲染？

我正在尝试使用四叉树实现二维快速碰撞检测。

AFAIK，四叉树将一个区域分为 4 个子区域，西北、东北、东南和西南。这种划分与正方形完美配合。但是如果这个区域是一个非正方形的矩形呢？在那种情况下，我们不能将长边和短边平均分割，而短边决定了我们可以分割多远。

我说得对吗？是这样的吗？

我需要以“通常”的方式将图像（正方形）转换为四叉树-将其切成四块，检查每块中是否只有一种颜色；如果是：关闭节点，否则：重复；

有人知道它的开源程序吗？

最好用Java，但我可以使用任何语言。

谢谢。

我正在用 Java (Eclipse) 编写一个实现四叉树结构的类。对于那些不熟悉这种结构的人来说，它只是一个正方形，它被递归地分成四个其他正方形，如下图所示。

我想显示如下所示的数据结构。有没有人有一个简单的实现的好主意？

谢谢