Попытка выяснить, пересекаются ли два отрезка

Question

У меня есть отрезок, состоящий из двух точек p1 и p2, и второй отрезок, состоящий из точек p3 и p4. Я пытаюсь выяснить, пересекаются ли они, и пока мне не повезло. Это мой код до сих пор:

public static double angle(Point p1, Point p2, Point p3) {
    double AB = length(p2, p1);
    double BC = length(p2, p3);
    double AC = length(p3, p1);
    return Math.acos((sqr(BC) + sqr(AB) - sqr(AC)) / (2 * BC * AB)) * (180 / Math.PI);
}

public static boolean doIntersect(Point p1, Point p2, Point p3, Point p4) {
    double a = angle(p4, p3, p2);
    double b = angle(p3, p2, p1);
    double c = 180 - b - a;

    System.out.println("a: " + a + ", b: " + b + ", c:" + c);

    if((length(p3, p2) * Math.sin(a)) / Math.sin(c) > length(p2, p1)) return false;
    if((length(p3, p2) * Math.sin(b)) / Math.sin(c) > length(p3, p4)) return false;
    return true;
}

public static double length(Point point1, Point point2) {
    return Math.sqrt(sqr(point1.x - point2.x) + sqr(point1.y - point2.y));
}

public static double sqr(double doub) {
    return Math.pow(doub, 2);
}

Но это не работает. Иногда угол "с" даже выражается как отрицательные числа.

Кроме того, Point - это пользовательский класс с двумя параметрами: x и y. Должно быть достаточно очевидным.

Answer 1

Для расчета углов вместо сложного метода, в котором вы суммируете квадраты разностей x и y, затем берете квадратный корень из суммы, затем возводите в квадрат это значение и затем используете acosможно использовать atan2, который вычисляет угол в собственном квадранте из разностей x и y. Это быстрее и менее проблематично, чем acos метод.

Тем не менее, нет никакой необходимости вычислять какие-либо углы вообще. Вместо этого сначала проверьте, если перекрытие невозможно. Возвращение No если ((x₁≤x₃≤x₂ || x₁≤x₄≤x₂ || x₃≤x₁≤x₄ || x₃≤x₂≤x₄) && (y≤y₃≤y₂ || y₁≤y₄≤y₂ || y₃≤y₁≤y₄ || y₃≤y₂≤y₄)) ложно (Пусть p₁,p₂ - конечные точки одного сегмента, а p₃,p₄ - конечные точки другого.)

Если случай неосуществим, вы можете проверить, происходит ли пересечение, увидев, отличаются ли знаки площадей треугольников p₁,p₂,p₃ и p₁,p₂,p₄. Площадь p₁,p₂,p₃ равна ±(x₁·y₂-x₂·y₁ + x₃·(y₂-y₁) + y₃·(x₂-x₁))/2, и коэффициент 1/2 можно игнорировать, поскольку он не влияет на знак То есть для возможных случаев вы можете вычислить
t = x₁·y₂-x₂·y₁
u = t + x₃·(y₂-y₁) + y₃·(x₂-x₁)
v = t + x₄·(y₂-y₁) + y₄·(x₂-x₁)
и вернуться Yes если u·v ≤ 0иначе No, Смысл использования такого метода состоит в том, чтобы избежать необходимости проверять все особые случаи, возникающие с вертикальными или горизонтальными линиями, параллельными или совпадающими линиями и т. Д. Если вы ожидаете появления вырожденных линий, сообщите Yes если u·v < 0, или же No если u·v > 0, иначе проверьте, если одна строка имеет конечную точку на другой линии.

Answer 2

Я бы предложил сначала сформулировать математическое решение, проверить его, а затем попытаться перенести его в компьютерную программу.

Answer 3

Есть два решения, каждое из которых имеет свои преимущества:

1. Математическое решение

Из двух точек p1 и p2 можно легко вывести формулу y = m*x + b для линии, которая пересекает эти две точки. С помощью формул для линий, определенных (p1, p2) и (p3, p4), снова легко вычислить их пересечение путем выравнивания. Осталось только проверить, является ли точка пересечения частью обоих отрезков, что довольно очевидно.

2. Алгоритмическое решение

Другой подход заключается в применении алгоритма линии развертки: сортировка всех точек по их соответствующей x-координате. Затем для каждой точки в x-порядке представьте вертикальную линию, которая прыгает от точки к точке.

Если вы достигли первой точки отрезка линии B после того, как посетили все точки отрезка линии A, пересечения не будет.

В противном случае ваша первая точка находится на отрезке линии A, а вторая точка - на отрезке B. Следовательно, ваша третья и четвертая точки принадлежат A и B или B и A соответственно. Сосредоточьте свое внимание на координатах y и решите самую последнюю часть этого решения самостоятельно.;-)

РЕДАКТИРОВАТЬ: или еще проще, спросите Википедии о пересечении отрезка.