碰撞检测复杂度
我有大量的物体（首先是球）在空间中逐步移动，一次一个，并且不会重叠。目前，对于每一个移动，我都会检查是否与其他所有对象发生碰撞。 几个 其他 问题 这里处理这个，然而，我想到了一个看似简单的解决方案，但在这种情况下似乎没有出现，我想知道为什么。
为什么不简单地保留所有对象的 2 个集合（对于 2D 或 3 个维度），分别按 x 和 y（和 z）坐标排序，并在每次移动时查找给定距离（球直径）内的所有其他对象这里）在每个维度中，并且仅对两个（或所有 3 个）结果集中的对象进行实际碰撞检查吗？
我意识到这仅适用于大小相同的对象，但也可以使用两倍的集合，按每个维度的每个对象的 (1) 最高 (2) 最低坐标排序。与从 O(n)“成对检查”到“网格方法" 或“四叉树/八叉树”？我认为这些排序集合的更新是成本高昂的操作，但是使用例如 TreeSet（我的实现将在 Java 中），它仍然应该明显小于 O(n)，对吗？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web
技术交流群。
我有大量的物体（首先是球）在空间中逐步移动，一次一个，并且不会重叠。目前，对于每一个移动，我都会检查是否与其他所有对象发生碰撞。 几个 其他 问题 这里处理这个，然而，我想到了一个看似简单的解决方案，但在这种情况下似乎没有出现，我想知道为什么。
为什么不简单地保留所有对象的 2 个集合（对于 2D 或 3 个维度），分别按 x 和 y（和 z）坐标排序，并在每次移动时查找给定距离（球直径）内的所有其他对象这里）在每个维度中，并且仅对两个（或所有 3 个）结果集中的对象进行实际碰撞检查吗？
我意识到这仅适用于大小相同的对象，但也可以使用两倍的集合，按每个维度的每个对象的 (1) 最高 (2) 最低坐标排序。与从 O(n)“成对检查”到“网格方法" 或“四叉树/八叉树”？我认为这些排序集合的更新是成本高昂的操作，但是使用例如 TreeSet（我的实现将在 Java 中），它仍然应该明显小于 O(n)，对吗？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
检查两个结果集中都有哪些对象涉及查看平面的两个条带中的所有对象。这是一个更大的区域，因此涉及的对象比四叉树让您立即缩小到的封闭正方形要大得多。更多对象意味着速度更慢。
The check for which objects are in both result sets involves looking at all objects in two strips of the plane. That is a much larger area, and therefore involves more objects, than the enclosing square that a quadtree lets you immediately narrow down to. More objects means that it is slower.
您想要使用空间索引或空间填充曲线而不是四叉树。 sfc 将 2d 复杂度降低到 1d 复杂度，并且与四叉树不同，因为它每个 x,y 对只能存储 1 个对象？也许这对你的问题有用？您想要搜索 Nick 的希尔伯特曲线四叉树空间索引博客。
You want to use a spatial index or space-filling-curve instead of a quadtree. A sfc reduce the 2d complexity to a 1d complexity and is different from a quadtree because it can only store 1 object per x,y pair? Maybe this works for your problem? You want to search for Nick's hilbert curve quadtree spatial index blog.