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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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