问题描述
我想检查圈子是否彼此碰撞。
I want to check if circles are colliding with each other.
我知道我可以通过获取圆的两个中心之间的距离,并减去
I know I can do this by getting a distance between the two centers of the circles and subtracting the radius of each circle from that distance and seeing if 'distance' is > 1.
我怎么能有效率地说这个问题,说1000个圈子?也许我能以某种方式得到最近的20个圈子或类似的东西,并检查这些?我不知道我会如何开始有效地,虽然任何..
How can I do this efficiently though with say, 1000 circles? Maybe I can somehow get the nearest 20 circles or something like that and check these? I don't know how I would begin to go about that efficiently though either..
任何想法?
以下是一个示例:
推荐答案
在开始计算距离之间的精确差异之前,您至少可以比较中心的x / y位置vs半径。该信息隐含在圆圈中,只需要一些简单的比较和加/减。
Before you start calculating exact differences in distances, you can at least compare the x/y positions of the centers v.s. the radii. That information is implicitly available in the circle and requires just some simple comparisons and addition/subtraction.
这样就可以比较所有圆对,并抛弃任何明显不是碰撞候选者,例如
That'll let you compare the simple distances in x/y between all the circle pairs, and throw away any that are obviously not collision candidates, e.g.
abs(x2 - x1) > (r2 + r1)
abs(y2 - y1) > (r2 + r1)
...如果圆心之间的X或Y距离较大
... if the distance in X or Y between the circle centers is greater than the sum of the radii, then they cannot be colliding.
一旦你敲下了可能的碰撞器,那么你就可以使用正确的笛卡尔距离重的乘法/除法的东西进来。
Once you've whittled down the possible colliders, THEN you do the formal exact cartesian distance, which is where the 'heavy' multiplication/division stuff comes in.
这篇关于圆形碰撞检测HTML5画布的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!