2

给定一个圆的列表，其坐标（x 和 y）每秒都在不同方向（东南、西南、东北和西北）移动，如果它撞到墙上，圆将改变方向有点像弹跳，那么我们如何检测它们中的任何一个是否相互碰撞或重叠？我不确定我们是否可以使用像 a 这样的一些数据结构，Binary Search Tree因为因为所有坐标每秒都在变化，所以树必须相应地重新构建。或者我们可以每次都使用垂直扫描线算法吗？关于如何以有效的方式做到这一点的任何想法？

4

2 回答 2

3

你的形状只是圆圈，所以：

  • 如果一个圆到边界的距离小于它的半径，它就会接触到你的矩形的边界。
  • 如果两个圆的中心之间的距离小于它们的半径之和，则两个圆将相互接触。

假设您的矩形的边界在水平轴上和X1垂直轴上（使用和）。在第一种情况下，如果你的圆心是并且它的半径是你必须检查是否：X2Y1Y2X1 < X2Y1 < 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. 如果这是真的，那么你们的圈子会相互接触。

于 2012-10-27T09:20:21.580 回答
0

鉴于提供的假设：

  • 你的移动形状只是圆圈。
  • 墙壁只是形成盒子的垂直或水平墙壁。
  • 圆圈不会相互碰撞（尽管这并不难实现）

您可以实现以下简单算法：

  • 对于每个圆，跟踪 4 个坐标作为与其当前原点（中心）的偏移量：
    • 上、下、左、右（或北、南、西、东）
    • 请注意，这些是与墙壁的圆圈与这 4 个确切位置的唯一接触点。
  • 每次一个圆圈移动后，检查它从原点开始的 4 个坐标中的每一个，看它是否与墙壁边界重叠（一种简单/懒惰的方法可以只是将墙壁制作成与您的 FPS / 球速一样厚的矩形要求）
  • 如何实现重叠检测：
    • 假设您刚刚将墙壁实现为RectangleWall.
    • 在RectangleWall中，添加一个名为public boolean isPointInside(Point pt)（或签名可以是(int x, int y)）的公共成员函数，并添加用于检查传入的点是否落在矩形边界内的逻辑：这对您来说应该很简单；）
  • 当检测到重叠时，实现相应的碰撞逻辑：
    • 如果球的左侧或右侧与某物重叠，则反转其 x 速度。
    • 如果球的顶部或底部与某物重叠，则反转其 y 速度。
于 2012-10-27T05:16:54.990 回答