2

Есть два массива точек, которые образуют две ломаные линии. Существует ли алгоритм поиска точек пересечения этих двух линий?

На ум пока приходит поиск пересечений каждого из отрезков обоих линий.

6
  • Ух, кривых...можно, например, если эти кривые соответствуют некоторым графикам функций( притом совсем не обязательно одинаковых ).
    – AseN
    11 дек 2013 в 18:45
  • @0xFFh ни как не соответсвуют графикам функции
    – andrew68
    11 дек 2013 в 18:46
  • 1
    Боюсь, тогда, если легко с помощью математики, то иначе - никак.
    – AseN
    11 дек 2013 в 18:50
  • 2
    Массив точек не может описывать кривую, только ломаную. Случаев 2: 1) Допустим, приближение соответствует ситуации "1 точка = 1 пиксель". Тогда "кривые" пересекаются в точках с одинаковыми координатами. 2) Для приближение кривой соседние точки соединяются отрезками. Тогда перебираем пары соседних точек для "кривых", и смотрим, пересекаются ли соединяющие их отрезки.
    – user6550
    11 дек 2013 в 19:06
  • @klopp не так выразился. Ломаная линия. А так да, думаю, только перебор всех отрезков меня спасёт.
    – andrew68
    11 дек 2013 в 19:14

1 ответ 1

3

Классический хрестоматийный алгоритм поиска всех пересечений в наборе отрезков - алгоритм sweep line. Тот факт, что в вашем случае мы имеем дело не с произвольным набором отрезков, а с двумя ломаными, как мне кажется, ситуации сильно не меняет.

Другое дело, если вам заранее известна какая-то дополнительная информация о ваших ломаных.

Например, если вам заранее известно, что ваши ломаные являются монотонными вдоль какого-то общего направления, то в такой ситуации поиск всех пересечений можно выполнить простым линейным проходом по ломаным.

1
  • А можно дополнить ссылкой на алгоритм, или даже его схематическим описанием?
    – VladD
    7 апр 2018 в 10:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.