Есть два массива точек, которые образуют две ломаные линии. Существует ли алгоритм поиска точек пересечения этих двух линий?
На ум пока приходит поиск пересечений каждого из отрезков обоих линий.
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуЕсть два массива точек, которые образуют две ломаные линии. Существует ли алгоритм поиска точек пересечения этих двух линий?
На ум пока приходит поиск пересечений каждого из отрезков обоих линий.
Классический хрестоматийный алгоритм поиска всех пересечений в наборе отрезков - алгоритм sweep line. Тот факт, что в вашем случае мы имеем дело не с произвольным набором отрезков, а с двумя ломаными, как мне кажется, ситуации сильно не меняет.
Другое дело, если вам заранее известна какая-то дополнительная информация о ваших ломаных.
Например, если вам заранее известно, что ваши ломаные являются монотонными вдоль какого-то общего направления, то в такой ситуации поиск всех пересечений можно выполнить простым линейным проходом по ломаным.