noi*_*cat 3 algorithm geometry intersection collision-detection
我有一些圈子,我知道他们的X,Y和r.我想检查他们中的任何一个是否与其他任何人一致......检查的方法很简单:
r 1 + r 2 <sqrt((x 1 -x 2)2 +(y 1 -y 2)2)
但是我必须全部检查所有吗？它给了我O(n 2)的复杂性,我想避免这个:/
试着看看KD-tree acc-struct.首先你必须考虑将圆形视为方形而不是计算交集的复杂性,而不是将这些方块放在修改后的KD树中,它需要一些思考,但希望没有太极端......方式kd-tree的工作原理是它取消了根据每个树级别的一些标准,可能匹配的一半.在维基上查找.祝你好运:)