В дополнение к предложению Geom (R-Tree - это путь), дальнейшие улучшения производительности можно получить, выполнив следующие действия:
1. Упростите полилинию - количество точек в полилинии можно уменьшить, сохранив общую форму полилинии. Это может быть сделано с использованием углового порога и обработки каждой точки или с использованием алгоритма Рамера-Дугласа-Пекера . В зависимости от того, что вы делаете, вам может понадобиться отслеживать, какие точки исходной полилинии использовались в качестве начальной / конечной точек для каждого сегмента упрощенной полилинии (индексы точек исходной полилинии нужно будет где-то хранить ).
В этом примере вы можете увидеть, как можно уменьшить количество точек ломаной линии. Красные точки указывают точки, которые не использовались на исходной полилинии, а зеленые точки указывают точки, которые были сохранены для построения упрощенной полилинии.
2. Сохраните упрощенные полилинии в R-дереве и определите пересечения между каждым сегментом каждой полилинии (сравнение границ сегментов для сокращения вычислений полезно для производительности). Когда это делается, старые индексы из исходных сегментов полилинии сохраняются как информация, относящаяся к каждому обнаруженному пересечению, вместе с которым пересекаются полилинии (можно использовать некоторый вид идентификатора). По сути, это дает вам начальную и конечную границы каждого сегмента в исходных полилиниях, где существуют пересечения друг с другом полилинии.
3. Этот шаг выполняется только в том случае, если местоположение пересечения должно совпадать с точным местоположением пересечений исходных полилиний. Вам нужно будет вернуться назад и использовать исходные неупрощенные полилинии вместе с данными из информации о пересечении, полученной на шаге 2. Каждое пересечение должно иметь начальный и конечный индексы, связанные с ним, и эти индексы можно использовать для определения того, какие определенные сегменты исходной полилинии должны быть обработаны. Это позволит вам обрабатывать только необходимые сегменты (заданные начальным и конечным индексами, хранящимися с информацией о пересечении). Альтернативой этому было бы использование самой точки и расширение ограничивающей рамки наружу, а затем обработка сегментов оригинальных полилиний, которые пересекаются с этой ограничительной рамкой (хотя это, вероятно, займет больше времени).
4. Может потребоваться выполнить дополнительный шаг для проверки конечных точек каждой ломаной линии относительно сегментов каждой другой ломаной линии, поскольку процесс упрощения может выбить некоторые пересечения конечных точек. (это обычно довольно быстро).
Этот алгоритм может быть дополнительно улучшен с помощью алгоритма Бентли-Оттмана (это алгоритм стреловидности, на который ссылался Геом). Также обратите внимание, что в зависимости от используемого алгоритма упрощения и параметров, используемых для таких алгоритмов (например, угловой допуск), может быть компромисс между производительностью и точностью (некоторые результаты пересечения могут быть потеряны в зависимости от того, насколько просты полилинии).
Очевидно, что существуют библиотеки, которые могут быть жизнеспособными, но если вы ограничены условиями лицензии в связи с компанией, в которой вы работаете, или продуктом, в котором вы работаете, сторонние библиотеки могут не подойти. Кроме того, другие библиотеки могут работать не так хорошо, как требуется.