Есть ли простой способ обнаружить пересечения отрезков?

Question

Это намного сложнее, чем может показаться на первый взгляд. У меня есть гигантский массив, который состоит из большего количества массивов, которые содержат точки [в форме массива "x, y"], например, так:

Array (
    [0] => Array (
        [0] => "0,9",
        [1] => "0,0",
        [2] => "9,0",
        [3] => "9,9",
        [4] => "0,9"
        )
    [1] => Array (
        [0] => "1,5",
        [1] => "1,6",
        [2] => "3,6",
        [3] => "3,8",
        [4] => "4,8"
    )
    ... and so on ...
)

Итак, мне нужно обработать все точки и посмотреть, пересекается ли любая точка массива, скажем, от $points[0][1] до $points[0][2], с любым другим отрезком линии, который может существовать в массиве. Все линейные сегменты расположены последовательно в том порядке, в котором они находятся в каждом из соответствующих массивов. Таким образом, в первом массиве «0,9» переходит в «0,0», и никакой другой точки в этом массиве. Последняя точка в массиве не возвращается к первой точке в массиве. Кроме того, его не следует рассматривать как пересечение, если отрезок линии заканчивается на пересечении другого отрезка, ему фактически нужно пересечь отрезок, который он пересекает.

Я думал о том, чтобы построить сегменты по мере их обработки. Так, как пробежаться по массивам, строящим каждую точку на «виртуальной» сетке, скажем, а затем каждый массив после этого будет вычисляться, если он пересекает другой сегмент, который уже нанесен, если это имеет какой-то смысл, но все равно кажется, что это может занять в то время как для расчета, если в массиве много отрезков. Похоже, что я буду делать для каждого сегмента в массиве, рассчитать, если он пересекает какие-либо сегменты, предшествующие ему (потому что теоретически он может пересекать сегмент в том же массиве, в котором он находится). Должен быть более простой способ сделать это, верно?

P.S. Я не мог придумать, к каким тегам это относится, кроме PHP. Если вы думаете о чем-либо, пожалуйста, не стесняйтесь пометить его.

Answer 1

Это довольно просто. Вы начинаете с вычисления уравнения (наклон и пересечение Y) каждой линии. Наклон составляет (Y ₁ -Y ₂ ) / (X ₁ -X ₂ ). Перехват Y - Y ₁ - наклон * X ₁ . Затем мы можем выразить эту линию в виде Y = mX + b, где m = наклон, а b = пересечение Y.

Как только вы вычислили их для пары линий, вы вычислили место, которое эти 10101 * линии пересекли бы. Здесь координаты X и Y одной линии равны X и Y другой линии. Другими словами, где уравнение для одной строки равно уравнению для другой строки: m ₁ X + b ₁ = m ₂ X + b ₂ . Затем вы можете решить это уравнение, изолировав X. Например, если заданы две строки Y = 3x + 5 и Y = .5x + 2:

3x+5 = .5x+2 // subtract 5 from both sides
3x = .5x - 3 // subtract .5x fro both sides
2.5x = -3    // divide by 2.5
x = -3/2.5   // reduce term
x = -1.2

Теперь мы установили точку пересечения двух линий , но мы не знаем, простираются ли оба отрезка достаточно далеко, чтобы включить эту точку. Для этого нам нужно проверить, что наше значение X находится между X ₁ и X ₂ для обоих отрезков.

Если вы собираетесь проверять пересечения для лота линий, вы, вероятно, захотите поискать «алгоритм развертки плоскости» (я не буду пытаться включить ссылку, но поиск в Google за это должно дать изрядное количество показов).

Answer 2

Вот простой метод, который был бы приемлем, если число точек в каждом списке невелико:

1. Возьмите первые два линейных сегмента в вашем массиве и проверьте, пересекаются ли они .
2. Если нет, проверить следующий сегмент линии по сравнению с предыдущими сегментами
3. Продолжите до последней точки и повторите для другого массива (я предполагаю, что эта проверка выполняется для каждого подмассива).

Это O (n ² ) , где n - количество точек во всех ваших подмассивах --- если n маленький - круто, если нет, дайте нам знать.

Обновление: если O (n ² ) недостаточно хорошо ...

Алгоритм развертки для пересечения сегментов - предположительно O (n log (n))

Ввод: Набор отрезков на плоскости.

Выход: Множество точек пересечения между сегментами в S.