问题标签 [quadtree]

作为介绍，我正在为个人学习目的创建一个基本的四叉树引擎。我希望这个引擎能够处理许多不同类型的形状（目前我正在使用圆形和正方形），它们都将在窗口中移动并在发生碰撞时执行某种动作。

这是我目前拥有的形状对象：

现在我的问题是，如何List<T> QObjectList = new List<T>();在 C# 中创建一个通用列表（ )? 一个实现的例子也会有帮助。

我只知道这个问题有一个愚蠢的答案，但无论如何我都会很感激任何帮助。我正在尝试回到 C#；显然已经有一段时间了……

作为介绍，我正在为个人学习目的创建一个基本的四叉树引擎。我希望这个引擎能够处理许多不同类型的形状（目前我正在使用圆形和正方形），它们都将在窗口中移动并在发生碰撞时执行某种动作。

在之前就泛型列表主题提出问题后，我决定使用多态接口。最好的接口将是一个接口Vector2，因为出现在我的四叉树中的每个对象都会有一个 x,y 位置并且Vector2很好地覆盖它。这是我目前的代码：

所以我最终会希望有一个界面可以使用通用列表，我可以使用代码或类似的东西List<ISpatialNode> QObjectList = new List<ISpatialNode>();向它添加形状（请记住，我会想要稍后沿线添加不同的形状）。QObjectList.Add(new QCircle(50, 400, 300, "Red"));QObjectList.Add(new QSquare(100, 400, 300, "Blue"));

问题是，当我从这里调用它时，这段代码似乎不起作用（Initialize()是 XNA 方法）：

所以我的问题有两个部分：

1.为什么这段代码在我的和类的set { position = value; }部分给我一个stackoverflow错误？QCircleQSquare

2.这是否是一种利用接口进行多态性的有效/有效方式？

概括：

我有一个应用程序消耗更多的内存（大约是预期数量的 250%），但我似乎找不到任何内存泄漏。调用相同的函数（执行大量分配）将不断增加内存使用量到某个点，然后它不会改变并停留在那里。

计划详情：

该应用程序使用四叉树数据结构来存储“点”。可以指定要存储在内存中的最大点数（缓存大小）。'Points' 存储在 'PointBuckets' （链接到四叉树的叶节点的点数组）中，如果达到四叉树中的最大总点数，则将其序列化并保存到临时文件中，以便在何时检索需要。这一切似乎都很好。

现在，当加载文件时，会创建一个新的四叉树，如果旧的四叉树存在则删除它，然后从文件中读取点并一一插入四叉树。在节点拆分等过程中创建和删除存储桶时，会发生大量内存分配。

症状：

如果我加载一个预期使用 300MB 内存的文件，我会得到预期的内存消耗量。都好。如果我一遍又一遍地加载相同的文件，内存使用量会不断增长（我正在查看顶部的 RES 列，Linux）直到大约 700MB。这可能表明内存泄漏。但是，如果我继续加载文件，内存消耗将保持在 700MB。

另一件事：当我使用 valgrind massif 并查看内存使用情况时，它始终保持在预期的限制内。例如，如果我将缓存大小指定为 1.5 GB 并单独运行我的程序，它最终会消耗 4GB 的内存。如果我在地块中运行它，它将一直保持在 2GB 以下，然后在生成的图表中我将能够看到它实际上从未分配超过预期的 1.5GB。我幼稚的假设是，发生这种情况是因为 massif 使用了一个自定义内存池，它以某种方式防止了碎片。

那么你认为这里发生了什么？如果是内存碎片，我应该寻找什么样的解决方案来解决这个问题？

我一直在寻找一些在我的 2D 模拟中实现四叉树的方法，以使碰撞检测更快，但我发现这个概念很难掌握。sim 效果很好，因为现在它只是一旦我超过 160-180 个粒子，它就会变得非常慢，因为碰撞检测会毫无必要地通过所有粒子，而且非常愚蠢。现在它只是一堆或圆圈在屏幕周围相互碰撞，我可以通过单击并拖动鼠标以新的速度和位置产生新的。

编辑1：

好吧，我想我现在可以创建树了，正如您在图像中看到的那样

我的四叉树图片：http: //i.stack.imgur.com/c4WNz.jpg

所以现在的问题是如何让它对我的碰撞检测有用......

每次检查时都必须从零开始创建整个树吗？

我在等待时将要做的事情，希望它在某种程度上是正确的：P

1_检查每个节点中是否有球，如果没有，则将该节点排除在外。2_继续检查交叉点，直到我达到叶层并将那些相交的球添加到叶节点。3_在我继续前进之前在叶节点碰撞球？？

这是我的 QuadTreeNode 类：

我很难掌握如何迭代八叉树或四边形。这可能是因为我没有经历过不同的迭代神话。但是让我们假设我生成了一个四叉树，它包含 float x,y,z; 双字颜色。现在，我们还假设这个节点一次只能产生 4 个孩子（这些孩子都可以产生 4 个孩子，等等），直到： 达到 7 个级别（这样孩子就不能再创建孩子了，但是它兄弟/姐妹可以），创建的所有 4 个孩子都是相同的 dword 颜色（同样，如果发生这种情况，其兄弟/姐妹仍然可以生产），或者创建的节点总数等于 87380。发生上述情况时，将其放入容器。这个过程还在继续。

现在这个包含节点的容器（例如）有 7 层深，所有子节点的子节点的所有子节点都有不同的 x、y、zs 和颜色。我遇到的问题是我如何迭代这个容器，我怎样才能遍历所有的孩子，姐妹们？由于根导致 4 个孩子，而这 4 个孩子有 4 个孩子，依此类推，依此类推：4^1+4^2....+4^7。如何在不编写复杂的 if 语句和遍历整个节点（从根开始）的情况下找到我想要的节点？容器（产生节点的容器）是否需要额外的代码来简化这个过程？

对不起，如果问题是一般性的。

我有一个程序，允许用户在大小为 1000 x 750 的 JFrame 上绘制顶点和边。现在我需要使用四叉树根据单个象限中有多少个顶点来划分输入图。如果有人能指出如何实现这一目标的正确方向，我将不胜感激？

附加信息：我有一个 Edge 类，它存储：源（顶点）、目标（顶点）和权重。我有一个 Vertex 类，它存储：名称、x 坐标、y 坐标和 Ed​​ge[] 相邻列表。我还有一个 Graph 类，它存储两个 ArrayList：边和顶点。

我可以知道如何绘制网格或二维四叉树（C++，OpenCV）吗？我只需要在受影响区域上的四叉树内的每个交点处定义点以进行反馈或输出。所以输出应该能够告诉我任何形状的点的最大范围。

有可能做到吗？

谢谢！

我正在为一个行星写一个四叉树结构，当你远离四边形并接近它时，它会减少和增加细节。但是，我遇到了一些非常严重且令人讨厌的错误。

我有两个预处理器定义的常量，当我将值更改为除 32 以外的任何值（例如 16 或 64）时，确定四叉树的大小（QUAD_WIDTH 和 QUAD_HEIGHT）我得到一个蓝屏死机。我正在使用 code::blocks 作为我的 IDE，另一件事：每当我尝试在 code::blocks 中调试程序时，我也会出现蓝屏死机（常量是否为 32 无关紧要）

为什么会这样？我该如何解决它。 PQuad.cpp

假设我们在二维世界中有很多动态对象，例如角色、射弹、能量提升，这些都是您在游戏中常见的东西。他们都在动。我们想检测它们之间的碰撞。有什么好的方法吗？

我看过四叉树，但它似乎检测动态移动对象之间的碰撞，我必须每帧重新创建四叉树（因为对象每帧都会改变它们的位置）。这看起来像一个昂贵的操作。

除了四叉树之外，还有其他方法可以解决这个问题吗？有没有办法改进四叉树方法？也许在每一帧上重新创建树毕竟不是那么昂贵？

第一次来这里，希望大家帮忙。

所以我做了一个四叉树函数，给定 i=1:4 坐标 (localmaplon[i],localmaplat[i])，它搜索并返回 4 个四叉树节点，这样我就可以看到 localmap 在哪些四叉树中。

我遇到的问题是在第一个解决方案之后，它将四叉树节点设置为它搜索的四叉树而不是根节点：

我的 cout 看起来像这样：

你们能帮我弄清楚我做错了什么吗！这是两个功能。这是solveLocalBuckets函数：

这是 getQuadTree 函数。