给定圆圈列表，其坐标（x和y）正在朝着不同方向移动（东南，西南，东北和西北），如果圆形撞到墙，则圆将改变方向，那么我们如何检测它们是否相撞或彼此重叠？我不确定我们是否可以使用诸如Binary Search Tree之类的一些数据结构，因为由于所有坐标每秒钟都有不同，因此树将不得不相应地重建。还是我们可以每次都使用垂直扫描线算法？关于如何以有效的方式进行此操作的任何想法？
您的形状只是圆，所以：
- 如果矩形的边界距离边界的距离不如其半径。
- 如果其中心之间的距离不如其半径。 ，两个圆将互相接触
假设您的矩形边界是水平轴上的X1和X2，垂直轴上的Y1和Y2（带有X1 < X2和Y1 < Y2）。在第一种情况下，如果您的圆的中心为(x, y)，并且其半径为r，则必须检查是否：
-
x-r < X1？ -
x+r > X2？ -
y-r < Y1？ -
y+r > Y2？
如果这些都是正确的，则您的圆圈会触及矩形的边界。
在第二种情况下，假设您的圆圈分别由(x1, y1, r1)和(x2, y2, r2)定义。您必须检查(x1 - x2)^2 + (y1 - y2)^2 < (r1 + r2)^2是否。如果这是真的，您的圆圈互相触摸。
给定提供的假设：
- 您的移动形状只是圆形。
- 墙壁只是形成盒子的垂直或水平墙。
- 圆圈不会相互冲突（尽管这并不难实施）
您可以实现以下简单算法：
- 对于每个圆圈，请跟踪4个坐标作为偏离当前起源（中心）的抵消：
- 顶部，底部，左，右（或北，南，西，东）
- 请注意，这些是与墙壁的唯一接触点，与这4个确切的位置。
- 圆圈移动后的每次，检查其4个坐标中的每一个从原点检查它是否与墙壁边界重叠（一种简单/懒惰的方式可以使墙壁像fps一样厚的矩形构成墙壁/球速需要）
- 如何实施重叠检测：
- 假设您刚刚以
RectangleWall的方式实现了墙。 - 在
RectangleWall中，添加一个称为public boolean isPointInside(Point pt)的公共成员函数（或签名可以为(int x, int y)），并添加逻辑以检查是否在矩形边界内传递的点是否在跌倒中：这应该对您很简单;;）
- 假设您刚刚以
- 当您检测到重叠时，实现相应碰撞的相应逻辑：
- 如果球的左或右点与某物重叠，请反转其X速度。
- 如果球的顶部或底部与某物重叠，请扭转其Y速度。