碰撞檢測——矩形重疊碰撞測試，線段相交碰撞測試，線段交點
// rectangle hit test
public static boolean rectHitTest(int x1, int y1, int x2, int y2, int x3,
int y3, int x4, int y4) {
if (Math.max(x1, x2) < Math.min(x3, x4)
|| Math.max(y1, y2) < Math.min(y3, y4)
|| Math.min(x1, x2) > Math.max(x3, x4)
|| Math.min(y1, y2) > Math.max(y3, y4)) {
return false;
}
return true;
}
// segment hit test
public static boolean segmentHitTest(int x1, int y1, int x2, int y2,
int x3, int y3, int x4, int y4) {
// fast hit test
if (!rectHitTest(x1, y1, x2, y2, x3, y3, x4, y4)) {
return false;
}
// segment hit test judgement
/**/
if (vectorProduct(x1 - x3, y1 - y3, x4 - x3, y4 - y3)
* vectorProduct(x2 - x3, y2 - y3, x4 - x3, y4 - y3) <= 0
&& vectorProduct(x3 - x1, y3 - y1, x2 - x1, y2 - y1)
* vectorProduct(x4 - x1, y4 - y1, x2 - x1, y2 - y1) <= 0) {
return true;
}
/**/
return false;
}
/**
*
* @param x1
* @param y1
* @param x2
* @param y2
* @param x3
* @param y3
* @param x4
* @param y4
* @return int array
* if return null, then the two segments are not crossed
* if return array.length = 2, then segments are crossed at x=array[0], y=array[1]
* if return array.length = 4, then segments are overlaped from
* coordinate (array[0],array[1]) to (array[2], array[3])
* if return else then means error
*/
public static int[] segmentHitPoint(int x1, int y1, int x2, int y2, int x3,
int y3, int x4, int y4) {
if (!segmentHitTest(x1, y1, x2, y2, x3, y3, x4, y4))
return null;
int k1, a1, k2, a2, x, y;
int mathShift = 10;
// on the same vertical line
if (x1 == x2 && x3 == x4 && x1 == x2) {
int maxY = Math.max(Math.max(y1, y2), Math.max(y3, y4));
int minY = Math.min(Math.min(y1, y2), Math.min(y3, y4));
int[] arrayY = new int[] { y1, y2, y3, y4 };
int[] result = new int[] { x1, 0, x1, 0 };
int index = 1, i = 0;
while (i < 4 && index < 4) {
if (arrayY[i] != maxY && arrayY[i] != minY) {
result[index] = arrayY[i];
index += 2;
}
i++;
}
return result;
} else if (x1 == x2) {
k2 = (y3 - y4 << mathShift) / (x3 - x4);
a2 = y3 - (k2 * x3 >> mathShift);
x = x1;
y = (x * k2 >> mathShift) + a2;
} else if (x3 == x4) {
k1 = (y1 - y2 << mathShift) / (x1 - x2);
a1 = y1 - (k1 * x1 >> mathShift);
x = x3;
y = (x * k1 >> mathShift) + a1;
}
// normal state
else {
k1 = (y1 - y2 << mathShift) / (x1 - x2);
k2 = (y3 - y4 << mathShift) / (x3 - x4);
if (k1 == k2) {
int maxX = Math.max(Math.max(x1, x2), Math.max(x3, x4));
int minX = Math.min(Math.min(x1, x2), Math.min(x3, x4));
int[] arrayX = new int[] { x1, x2, x3, x4 };
int[] arrayY = new int[] { y1, y2, y3, y4 };
int[] result = new int[4];
int index = 0, i = 0;
while (i < 4 && index < 4) {
if (arrayX[i] != maxX && arrayX[i] != minX) {
result[index++] = arrayX[i];
result[index++] = arrayY[i];
}
i++;
}
return result;
}
a1 = y1 - (k1 * x1 >> mathShift);
a2 = y3 - (k2 * x3 >> mathShift);
x = (a2 - a1 << mathShift) / (k1 - k2);
y = (x * k1 >> mathShift) + a1;
}
return new int[] { x, y };
}
// get the vector product
private static int vectorProduct(int x1, int y1, int x2, int y2) {
return x1 * y2 - x2 * y1;
}
