标签: quadtree

我最近了解了二进制空间分区树及其在三维图形和碰撞检测中的应用.我还简要地阅读了与四叉树和八叉树相关的材料.你什么时候在bsp树上使用四叉树,反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格,我会感到满意:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

什么是A,B和C？

我正在尝试使用四叉树进行二维碰撞检测,但我对如何实现它感到有点困惑.首先,我有一个四叉树,其中包含四个子树(一个代表每个象限),以及一个不适合单个子树的对象集合.

当检查对象在树中的碰撞时,我会做这样的事情(感谢QuadTree用于2D碰撞检测):

1. 检查对象是否与当前节点中的任何对象发生冲突.
2. 对于其空间与对象重叠的任何子树,递归.

要查找四叉树中的所有碰撞:

1. 检查当前节点中的每个对象与当前节点中的每个其他对象.
2. 根据每个子树检查当前节点中的每个对象.

要插入四叉树:

1. 如果对象适合多个子树,则将其添加到当前节点,然后返回.
2. 否则,递归到包含它的子树.

要更新四叉树:

1. 递归到每个子树.
2. 如果当前节点中的任何元素不再完全适合当前树,请将其移动到父节点.
3. 如果当前节点中的任何元素适合子树,请将其插入子树中.

这好吗？可以改进吗？

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

(我知道我可以通过修剪未使用的节点来优化树,并且可能有更好的数据结构,如用于空间分解的kd树.)

此外,每次添加新点时,我仍然不满意复制整个树/表达式的想法.但我的理解是,对整个表达式进行操作而不修改部分是函数式编程方式.我对这方面的任何澄清表示感谢.

MV

代码

ClearAll[qtMakeNode, qtInsert, insideBox, qtDraw, splitBox, isLeaf, qtbb, qtpt];

(* create a quadtree node *)
qtMakeNode[{{xmin_,ymin_}, {xmax_, ymax_}}] := 
{{}, {}, {}, {}, qtbb[{xmin, ymin}, {xmax, ymax}], {}}

(* is pt inside box? *)
insideBox[pt_, bb_] := If[(pt[[1]] <= bb[[2, 1]]) && (pt[[1]] >= bb[[1, 1]]) &&
  (pt[[2]] <= bb[[2, 2]]) && (pt[[2]] >= bb[[1, 2]]),
  True, False]

(* split bounding box into 4 children *)
splitBox[{{xmin_,ymin_}, {xmax_, ymax_}}] := {
 {{xmin, (ymin+ymax)/2}, {(xmin+xmax)/2, …

我一直在努力将Quadtree添加到我正在编写的程序中,我不禁注意到,我正在寻找的实现很少有很好的解释/执行教程.

具体来说,我正在寻找的一个方法列表和如何实现它们(或只是它们的过程的描述)的方法和伪代码的列表(检索,插入,删除等)是我正在寻找的,以及也许一些提高性能的技巧.这是用于碰撞检测,因此最好用2d矩形来解释,因为它们是将要存储的对象.

四叉树和kd树之间的主要区别是什么？我知道他们在很多方面分裂了点,但我不明白为什么我们会使用一个而不是另一个.我需要一个允许我计算给定区域中有多少点(2D点)的结构.基本上,我试图检测点集群.

我想比较地理空间数据的R-Tree和Quadtree.虽然有文献,但我很难找到涵盖真正基本比较的文件.所以我决定问这个问题.

在我看来,R-Tree具有平衡的优点,树没有空叶.作为缺点,插入或删除等基本操作可能导致重构整个索引.

四叶树是相反的,它不平衡并且有空叶,但它不需要被重新修剪.

因此,作为一个讽刺,我会说R-Tree确实需要更少的内存,并且由于最小的高度,搜索速度更快.当有许多更新操作时,四叉树更好,但结果树可能是不平衡的.

您认为这些观点是否正确？那里有没有涵盖这个主题的好文件？

Auf Wiedersehen,安德烈

我正在尝试确定一种存储一组对象的快速方法,每个对象都有一个x和y坐标值,这样我就可以快速检索某个矩形或圆形内的所有对象.对于小型对象集(~100),简单地将它们存储在列表中并通过它迭代的简单方法相对较快.然而,对于更大的群体来说,预计会很慢.我已经尝试将它们存储在一对TreeMaps中,一个在x坐标上排序,一个在y坐标上排序,使用以下代码:

xSubset = objectsByX.subSet( minX, maxX );
ySubset = objectsByY.subSet( minY, maxY );
result.addAll( xSubset );
result.retainAll( ySubset );

这也有效,并且对于较大的对象集更快,但仍然比我想要的慢.部分问题还在于这些对象四处移动,需要插回到此存储中,这意味着将它们从树中删除并重新添加到树/列表中.我不禁想到那里必须有更好的解决方案.我在Java中实现这个,如果它有任何区别,虽然我希望任何解决方案都会以有用的模式/算法的形式出现.

似乎我的某个项目需要使用四叉树,这是我以前从未使用过的.从我所看到的,他们应该允许大量的性能增强,而不是蛮力尝试解决问题.这些python模块中的任何一个都不错吗？

• Quadtree 0.1.2 <= No:无法在Python 3.1中执行
• QuadTree <= 是:使用矩形时很简单
• quadtree.py <= 否:不支持所需的操作

编辑1:有没有人知道比pygame wiki中提供的更好的实现？

编辑2:以下是其他人可能会发现Python中的路径寻找技术有用的一些资源.

• 游戏实体导航
• 抓住Cootie

我目前正在研究2D射击类型的游戏,我正在使用四叉树进行碰撞检测.我写了一个工作四元树,正确地将我的演员推入他们属于树的节点/叶子.但是,我遇到了一些问题.

首先,我如何实际使用我的四叉树来选择一个对象应该测试碰撞的其他对象？我不确定如何做到这一点.

这提出了第二个问题.假设我在节点中有一个不是另一个节点的邻居的对象,但是该对象足够大以至于跨越几个节点,我如何检查实际的冲突,因为我猜测树可能认为它不是足够接近与"远方"节点中的物体碰撞？是否应将完全适合节点的对象保留在父节点中？

在我的游戏中,大多数物体都有不同的尺寸和移动.

我已经阅读了大量关于四叉树的博客/文章,但大多数只是解释如何构建一棵不是我正在寻找的树.

欢迎任何帮助/信息.

建立

• 函数需要提供从点到多边形最近边缘的距离
• 已知点在多边形内部
• 多边形可以是凸面或凹面
• 需要测试许多点(数百万)
• 每个点需要运行许多单独的多边形(数十个)
• 预先计算和持久存储的数据结构是一种选择.
• 最终的搜索功能将使用C++

对于函数实现,我知道一个简单的方法是使用标准距离到线段公式来测试到多边形的所有段的距离.这个选项规模相当慢,我相信应该有更好的选择.

我的直觉是,对于这种类型的功能应该有一些非常快速已知的算法,这些算法可以在游戏引擎中实现,但我不知道在哪里看.

我找到了一个用于在四叉树中存储线段的参考,这将提供非常快速的搜索,我认为它可以用于我的目的,以快速缩小哪个段看作最近的段然后只需要计算到一个线段的距离. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

我无法找到任何代码示例来说明这将如何工作.我不介意从头开始实现算法,但是如果存在一个可用的,经过测试的代码库,那么就不会明白这一点.

我一直在寻找几个四叉树实现,我认为它的工作方式是每个多边形创建一个四叉树,并将每个多边形的线段与一个边界框插入到该多边形的四叉树中.

我将要制作的函数的"查询"部分将包括创建一个点作为一个非常小的边界框,然后将其用于搜索四叉树结构,然后只能找到多边形的最接近的部分.

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

和

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

我真正的问题是,这对于快速搜索时间功能来说似乎是一种合理的方法吗？

有什么东西可以更快地运作吗？

编辑:我一直在环顾四周,发现使用四叉树的一些问题.四叉树的工作方式有利于碰撞检测,但不能设置为允许有效的最近邻搜索. https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-Trees看起来是更好的选择. https://en.wikipedia.org/wiki/R-tree

和

处理2d线段的有效方法

基于这些帖子,R树看起来像赢家.也很方便看到C++ Boost已经实现了它们.这看起来足够接近我计划做的事情,我将继续实施并验证结果.