为什么点区域四叉树搜索（用于碰撞检测）是线性时间？
完全创建四叉树后，为什么比较操作（用于n对象的冲突检测）需要线性的n log（n）时间？节点按区域/象限递归地拆分，搜索将向下扫描树，删除不在搜索坐标内的路径，最终在冲突节点的范围内找到或没有找到目标节点。每个操作都在比较一个划分的分区n，这看起来像log（n）时间，而不是n log（n）。
共有1个答案
要找到n个物体的所有碰撞（以及在最坏的情况下显示任何一个碰撞），应该执行大约n个动作 - 检查每个物体的附近。
正如您所写的，每次这样的检查都需要O（logn）时间，因此总时间达到O（nlogn）
-
大家好，我正在用Java制作一个体素游戏，在研究我需要学习的所有不同内容时，我注意到很多游戏都使用AABB进行碰撞检测。然后我记得在Minecraft中也看到了AABB。但当我在谷歌上搜索什么是AABB时，它只会给出其他人的代码，或者历史书上的某个组织。Stackoverflow，什么是AABB？
-
我有两个矩形的游戏对象，一个玩家和一个敌人。我希望玩家在Y轴上跳跃，敌人在X轴上滑行。当玩家的X、Y位置与敌人的位置匹配时，应该杀死玩家。到目前为止，我无法让AnimationTimer（）检查每个帧的恒定X位置和Y位置。它仅在应用程序首次启动时进行检查，并保留这些值。 如何让它检查两个矩形的 X 位置和 Y 位置的每个帧？
-
碰撞检测 现在你知道了如何制造种类繁多的图形对象，但是你能用他们做什么？一个有趣的事情是利用它制作一个简单的 碰撞检测系统 。你可以用一个叫做：hitTestRectangle 的自定义的函数来检测两个矩形精灵是否接触。 hitTestRectangle(spriteOne, spriteTwo) 如果它们重叠， hitTestRectangle 会返回 true。你可以用 hitTestRect
-
本节暂未进行完全的重写，错误可能会很多。如果可能的话，请对照原文进行阅读。如果有报告本节的错误，将会延迟至重写之后进行处理。 当试图判断两个物体之间是否有碰撞发生时，我们通常不使用物体本身的数据，因为这些物体常常会很复杂，这将导致碰撞检测变得很复杂。正因这一点，使用重叠在物体上的更简单的外形（通常有较简单明确的数学定义）来进行碰撞检测成为常用的方法。我们基于这些简单的外形来检测碰撞，这样代码会变得
-
我正在尝试为我的3D环境创建一个四叉树（所有元素都在平坦的地形上，因此它们可以用2D数据表示），但我对它的精细部分的实现有点迷路。 我将首先描述我当前的四叉树，然后讨论它的缺陷，然后提出问题。 我目前拥有的是一个四边形树，它接受一个非常具体的矩形，我在其中定义了x，z，宽度和前向。以下是我的操作概述。 将对象插入四元树： 检查当前节点是否有子节点。如果是，请检查对象是否能够完全适应四个节点中的任何
-
因此，我创建了一个方法来检测球形球和矩形球之间的碰撞。我把它分成了4部分；它检测圆的顶部、圆的左侧、圆的底部、圆的右侧和矩形之间的碰撞。其中的两个工作是检测圆上的左点和矩形之间的碰撞，以及检测圆上的右点和矩形之间的碰撞。但是，不起作用的是，如果最上面的点或最下面的点接触矩形，就不会检测到碰撞，正如我记录if语句以查看是否输入它时所看到的那样。下面是我的代码（方法。getr（）获取圆圈半径）： 我已