我有一些圈子，我知道他们的 X、Y 和 r。我想检查它们中的任何一个是否与其他任何冲突...检查的方法很简单:
r1+r2 < sqrt((x1-x2) 2 +(y1-y2)2)
但是我必须全部检查吗？它给了我 O(n2) 复杂度，我想避免这种情况:/
最佳答案
尝试查看 KD-tree acc-struct。首先，你必须将圆圈视为正方形，计算交集的复杂性比你将这些正方形放在修改后的 KD 树中要低，这需要一些思考，但希望不要太极端...... kd-tree 的工作方式是它抵消了根据每个树级别的某些标准，可能匹配的一半。在维基上查一下。祝你好运:)
关于algorithm - 检查碰撞圈，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9545622/