Это намного сложнее, чем может показаться на первый взгляд. У меня есть гигантский массив, который состоит из большего количества массивов, которые содержат точки [в виде массива «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» и не имеет другой точки в этом массиве. Последняя точка в массиве не обращается к первой точке массива. Кроме того, это не следует рассматривать как пересечение, если сегмент линии заканчивается на пересечении другого сегмента линии, ему действительно необходимо пересечь отрезок линии, который он пересекает.
Я думал о графике сегментов, когда я их обрабатывал. Так что, например, пробегайте массивы, зачеркивая каждую точку в «виртуальной» сетке за скажем, а затем каждый массив после этого будет вычислять, если он пересечет другой сегмент, который уже нанесен на график, если это имеет какой-то смысл, но все еще кажется, что может потребоваться а для вычисления количества сегментов линии в массиве. Кажется, что я буду делать для каждого сегмента массива, вычислить, пересекает ли он какие-либо сегменты, предшествующие ему (потому что теоретически он может пересекать сегмент в том же массиве, в котором он находится). Должен быть более простой способ сделать это, правильно?
PS Я не мог подумать о том, какие теги должны относиться к другим, кроме PHP. Если вы думаете о любом, не стесняйтесь его повторять.
Вот простой метод, который был бы приемлемым, если количество точек в каждом списке невелико:
Это O (n 2 ), где n – количество точек во всех ваших подмассивах – если n мало – удивительно, если нет, сообщите нам.
Алгоритм линии развертки для пересечения сегментов – предположительно O (n log (n))
Вход: набор сегментов линии в плоскости.
Выход: множество точек пересечения между сегментами в S.
Это довольно легко. Вы начинаете с вычисления уравнения (наклон и перехват Y) каждой линии. Наклон равен (Y 1 -Y 2 ) / (X 1 -X 2 ). Перехват Y – Y 1 – наклон * X 1 . Тогда мы можем выразить эту прямую в виде Y = mX + b, где m – наклон, b – перехват Y.
Как только вы вычислили их для пары линий, вы вычислите место, которое пересекали эти линии . Здесь координаты X и Y одной линии равны X и Y другой линии. Другими словами, если уравнение для одной линии равно уравнению для другой линии: m 1 X + b 1 = m 2 X + b 2 . Затем вы можете решить это уравнение, изолировав 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 1 и X 2 для обоих сегментов линии.
Если вы собираетесь проверять пересечения для большого количества строк, вы, вероятно, захотите найти «алгоритм развертки плоскости» (я не буду пытаться включить ссылку, но Googling для этого должен дать достаточное количество ударов ).