查找重叠的圈子 [英] Find overlapping circles

问题描述

我有一个矩形区域，那里有半径相等的圆。我想找出哪些圆与其他圆重叠（输出是2个元素的重叠圆的列表）。

I have a rectangular area where there are circles with equal radius. I want to find which circles overlap with other circles (the output is a list of 2-element sets of overlapping circles).

我知道如何检查两个圆圆重叠（圆心之间的距离小于直径）。我可以对每对圆圈执行此检查，但是我想知道是否有更好的算法（比 O（n ^ 2）更快）。

I know how to check if two of the circles overlap (the distance between their centers is less than the diameter). I can perform this check for every pair of circles, but I was wondering if there is a better algorithm (faster than O(n^2)).

编辑

圆圈数通常约为100，并且重叠很少发生。

The number of circles is usually about 100 and overlappings won't happen very often.

这里是一些上下文：
矩形是游戏中的战场。单元的移动是在很小的步骤上完成的，我正在尝试检测单元之间的冲突。

Here is some context: The rectangle is a battlefield in a game. The movement of the units is done on small steps and I'm trying to detect collisions between units.

推荐答案

给出新的解释对于问题陈述，我建议采用另一种方法。

Given the new explanation of the problem statement, I would recommend a different approach.

在战场上覆盖一个正方形网格，网格步长等于一个圆直径。每个圆圈最多可以重叠四个单元。在每个单元格中，保留一个重叠圆的列表（并在每次移动时对其进行更新）。

Overlay a square grid over the battlefield, with a grid step equal to one circle diameter. Every circle can overlap at most four cells. In each cell, keep a list of the overlapping circles (and update it on every move).

检测潜在的碰撞现在每个圆大约需要进行四个单元/圆测试，即接近线性时间。

Detecting potential collisions will now take about four cell/circle tests per circle, i.e. close to linear time.

这篇关于查找重叠的圈子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！