线段矩形碰撞检测

在 R² 中检测有两个端点的线段是否与一个矩形碰撞的问题可以被划分为检测线段是否和矩形的任意边相交，或线段的任意端点在矩形内部（包括刚好在边上）。

前者是四次线段相交检测。对于线段相交检测，最明显的途径自然就是求包含这两条线段的直线的交点，然后判断是否在线段范围内。然而，这个方法无法避免浮点运算。为了提高效率，就需要避免浮点运算，只进行整数定点运算。下面的算法，是判断两条线段各自的端点是否分别在包含另一条线段的直线的两端。只有在这种情况下（当且仅当），两条线段才相交。这就涉及到另一个问题——判断两个点是否分别在一条直线的两端。这里可以分别使用两个点按固定的顺序连接线段的两个端点（即直线上的两个点），形成两个凸包（三角形），然后检测凸包的形成是通过顺时针还是逆时针旋转。如果这两个点各自在直线的一端，那么必然有着相反的旋转方向，一个是顺时针，一个是逆时针。

def cw_test(ax, ay, bx, by, cx, cy)
  lhs = (by - ay) * (cx - ax)
  rhs = (cy - ay) * (bx - ax)
  if lhs == rhs then 0
  elsif lhs < rhs then 1
  else 2
  end
end

这是判断旋转方向的检测函数。如果 (ax, ay), (bx, by), (cx, cy) 这三个点在同一直线上返回 0，逆时针返回 1，顺时针返回 2。之所以需要三个状态，是为了在调用的时候能区分。

def bound?(x, a, b)
  a <= x && x <= b || a >= x && x >= b
end

def bound_inside?(x, y, ax, ay, bx, by)
  bound?(x, ax, bx) && bound?(y, ay, by)
end

def seg_intersect?(px1, py1, px2, py2, qx1, qy1, qx2, qy2)
  t1 = cw_test(px1, py1, qx1, qy1, qx2, qy2)
  t2 = cw_test(px2, py2, qx1, qy1, qx2, qy2)
  t3 = cw_test(qx1, qy1, px1, py1, px2, py2)
  t4 = cw_test(qx2, qy2, px1, py1, px2, py2)
  3 == (t1 | t2) && 3 == (t3 | t4) ||
  0 == t1 && bound_inside?(px1, py1, qx1, qy1, qx2, qy2) ||
  0 == t2 && bound_inside?(px2, py2, qx1, qy1, qx2, qy2) ||
  0 == t3 && bound_inside?(qx1, qy1, px1, py1, px2, py2) ||
  0 == t4 && bound_inside?(qx2, qy2, px1, py1, px2, py2)
end

这里 bound? 函数判断一个值 x 是否在 [a, b] 区间内；bound_inside? 函数判断一个点是否在一个与坐标轴对齐的矩形内（包含边界）；seg_intersect? 判断两条线段 (px1, py1)-(px2, py2), (qx1, qy1)-(qx2, qy2) 是否相交。t1、t2、t3、t4 分别是两条线段的四个端点是否在包含另一条线段的直线两侧的测试结果。t1 和 t2 成对，t3 和 t4 成对，每一对中必须有一个的 cw_test 返回 1，一个的 cw_test 返回 2，也就是一个顺时针，一个逆时针。当检测结果是 0 的时候是特殊情况，所以需要特殊处理。cw_test 返回 0，表示三个点在同一条直线上，这时通过检测第一个点是否在后面两个点（左上角与右下角）形成的与坐标轴对齐的矩形中，就能判断出是否有一条线段的一个端点在另一条线段上。

这样就涵盖了所有线段和矩形边相交的情况。然而线段可以完全被包围在矩形中，根本不和边相交。这种情况下，根据程序的需求不同，处理方式也可能不同。这里假设完全被包围也属于碰撞，那么就可以判断线段的其中一个端点是否在矩形中。只要有一个端点在矩形中，线段就必然和矩形碰撞了。

def point_lies_in?(x, y, ax, ay, bx, by, cx, cy, dx, dy)
  (cw_test(x, y, ax, ay, bx, by) |
   cw_test(x, y, bx, by, cx, cy) |
   cw_test(x, y, cx, cy, dx, dy) |
   cw_test(x, y, dx, dy, ax, ay)) != 3
end

这是一个判断点 (x, y) 是否在一个矩形中的检测函数，x、y 后面的参数必须以时钟顺序传递。这里又再次应用了凸包的属性。如果一个点在矩形中，并且并非刚好在矩形的边上，那么这个点与每个矩形边的两个端点按时针顺序所形成的所有三角形凸包都将会有相同的 cw_test 检测结果，也就是要么全部顺时针，要么全部逆时针。如果点在矩形外部，那么必然有一个或多个凸包和其它凸包的旋转方向相反。点刚好落在矩形边上的时候是一种特殊情况，这时对该点和所在边的两个端点应用 cw_test 会返回 0。由于这种情况也被考虑为碰撞，所以最后是判断所有 cw_test 结果的或运算不为 3 = 0b0011。如此一来一旦同时出现两个分别为 1 = 0b0001 和 2 = 0b0010 的检测结果，与运算最后都会返回 3。

　　最后，线段矩形碰撞检测函数：

def seg_rect_collide?(ax, ay, bx, by, tlx, tly, trx, try, brx, bry, blx, bly)
  point_lies_in?(ax, ay, tlx, tly, trx, try, brx, bry, blx, bly) ||
  point_lies_in?(bx, by, tlx, tly, trx, try, brx, bry, blx, bly) ||
  seg_intersect?(ax, ay, bx, by, tlx, tly, trx, try) ||
  seg_intersect?(ax, ay, bx, by, trx, try, brx, bry) ||
  seg_intersect?(ax, ay, bx, by, brx, bry, blx, bly) ||
  seg_intersect?(ax, ay, bx, by, blx, bly, tlx, tly)
end

和 seg_intersect? 一样，矩形四个顶点的传递顺序必须是时钟顺序。

附上一系列单元测试：

def assert_equal(expected_value, actual_value)
  puts "Got #{actual_value}; " + (actual_value == expected_value ? 'OK' : 'FAILED')
end

def assert_true(test)
  puts test ? 'Got true; OK' : 'Got false; FAILED'
end

def assert_false(test)
  puts test ? 'Got true; FAILED' : 'Got false; OK'
end

assert_equal(1, cw_test(0, 0, 1, 1, 0, 2))
assert_equal(1, cw_test(-134, -421, 2345, 0, -2129575, -100))
assert_equal(1, cw_test(1, -1, -491746, -1, 0, -2))
assert_equal(2, cw_test(3, 4, -32, -14, -33, 1))
assert_equal(2, cw_test(0, 0, 0, -1, -1, 0))
assert_equal(2, cw_test(2, 6, 9, 1, -32, 0))
assert_equal(0, cw_test(-32, 32, -32, 32, -32, 32))
assert_equal(0, cw_test(1, 1, 1, 1, 2, 2))
assert_equal(0, cw_test(7, 7, 8, 8, 8, 8))
assert_equal(0, cw_test(5, 5, 6, 6, 5, 5))

assert_true(seg_intersect?(-6, 7, 13, -1, 10, 2, 0, 0))
assert_true(seg_intersect?(0, 0, 1, 1, 0, 1, 1, 0))
assert_true(seg_intersect?(-1, -1, 9, 9, 0, -2, -2, 0))
assert_true(seg_intersect?(32, 4521, 32, -2156413, 3, 1, 32, 1))
assert_false(seg_intersect?(-100, 10000, 100, -10000, -200, 20100, 200, -19900))
assert_false(seg_intersect?(32, 13, -14, -4, -34, 77, 0, 6))
assert_false(seg_intersect?(0, 0, 14, -8, 11, -14, 22, 0))
assert_false(seg_intersect?(1, 6, 14, 6, 15, 11, 15, 1))
assert_false(seg_intersect?(0, 0, 1, 1, 2, 2, 3, 3))
assert_false(seg_intersect?(-1, -1, -1, 32, -1, 33, -1, 34))
assert_false(seg_intersect?(-1, -1, 9, 9, 0, -3, -3, 0))
assert_true(seg_intersect?(1, 1, 1, 1, 1, 1, 1, 1))
assert_true(seg_intersect?(1, 1, 1, 1, 3, -235421324, 1, 1))
assert_true(seg_intersect?(1, 1, 1, 1, 1, 1, 3, 3243))
assert_true(seg_intersect?(1, 1, 233, 43, 1, 1, 3, 3243))
assert_true(seg_intersect?(1, 1, 1, 9, 1, 7, 1, 34))
assert_true(seg_intersect?(-100, 10000, 100, -10000, -500, 50000, 500, -50000))

assert_true(seg_rect_collide?(0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1))
assert_true(seg_rect_collide?(7, 5, 10, 11, 8, 5, 8, 1, 1, 1, 1, 5))
assert_true(seg_rect_collide?(8, 0, 8, 6, 8, 1, 0, 1, 0, 3, 8, 3))
assert_true(seg_rect_collide?(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))
assert_false(seg_rect_collide?(1, 1, 3, 1, 4, 1, 6, 1, 6, 3, 1, 3))