import static java.lang.Math.*;
public class LineSegmentIntersection {
private static float clamp(float v, float min, float max) {
return max(min(v, max), min);
}
public static float[] intersect(
// Start- und Endpunkt des Liniensegmentes A
float a0x, float a0y, float a1x, float a1y,
// Start- und Endpunkt des Liniensegmentes B
float b0x, float b0y, float b1x, float b1y) {
float bax = b0x - a0x, bay = b0y - a0y;
float rx = a1x - a0x, ry = a1y - a0y;
float sx = b1x - b0x, sy = b1y - b0y;
float rXs = rx * sy - sx * ry;
float baXr = bax * ry - rx * bay;
float eps = 1E-6f;
if (abs(rXs) > eps) {
// beide Liniensegmente sind nicht kollinear -> sie koennten sich schneiden
float baXs = bax * sy - sx * bay;
float rXsi = 1.0f / rXs;
float t = baXs * rXsi, u = baXr * rXsi;
if (t >= 0.0f && t <= 1.0f && u >= 0.0f && u <= 1.0f) {
// sie schneiden sich an Punkt [x, y]
return new float[] { a0x + t * rx, a0y + t * ry };
}
} else if (abs(baXr) < eps) {
// beide Liniensegmente sind kollinear -> sie koennten sich in einem Intervall ueberlappen
float rOr = rx * rx + ry * ry;
float t0 = bax * rx + bay * ry;
float t1 = t0 + sx * rx + sy * ry;
if (t0 >= 0.0f && t1 <= rOr || t0 <= rOr && t1 >= 0.0f) {
// sie ueberlappen sich
float rdri = 1.0f / rOr;
float t0m = clamp(t0 * rdri, 0.0f, 1.0f);
float t1m = clamp(t1 * rdri, 0.0f, 1.0f);
return new float[] {
// ein Endpunkt des Ueberlappungsintervalls
a0x + t0m * rx, a0y + t0m * ry,
// ein anderer Endpunkt des Ueberlappungsintervalls
a0x + t1m * rx, a0y + t1m * ry};
}
}
return null; // <- weder Schnitt noch Ueberlappung
}
}