Я знаю два способа найти пересечения в отрезках.
Первый метод заключается в использовании алгоритма Бентли-Оттмана для нахождения всех пересечений.Затем вы можете отфильтровать ненужные пары сегментов (из одного набора).Обратите внимание, что поддержка всех граничных случаев для этого алгоритма может быть довольно сложной, и я бы не рекомендовал это делать.Также у меня были трудности с поиском существующих реализаций для Bentley-Ottmann и . Я знаю только одну, которая имеет дело с крайними случаями .
Другой метод - использовать два R-Tree (это ваше двоичное дерево поиска?) для индексации каждого из ваших рядов сегментов.Затем вы можете выполнить итерацию по всем сегментам одной серии и найти набор соседних сегментов другой серии.С этим, как мы надеемся, сокращенным набором сегментов, вы можете перебором перекрестка.В зависимости от вашего набора данных он может либо близко соответствовать характеристикам Bentley-Ottmann, либо работать точно так же, как и метод грубой силы.Еще одним недостатком является то, что если вам нужно перемещать свои сегменты, вы должны обновить свои индексы.С другой стороны, я считаю, что с этим алгоритмом легче справляться с крайними случаями, и реализации R-Tree должны быть проще для поиска или реализации самостоятельно.
Я все же рекомендую вам попробовать метод грубой силы, прежде чем пытатьсялюбой из этих.Это не должно занять слишком много времени, и большая часть кода должна быть полезна для реализации двух других методов.Вы также можете обнаружить, что это достаточно быстро, чтобы избежать неизбежных головных болей с помощью более сложных методов.
Небольшое обновление для ответа на комментарий Стивена.
Когда я реализовал свой алгоритм поиска пересечений, у меня былооптимизировать процесс, который также работал с данными OSM.Большинство моих тестов производительности были сделаны с использованием лондонского города, который содержит много сегментов и пересечений (не помню фактическое число, извините).Мой алгоритм поиска пересечений также должен был обрабатывать все граничные случаи (вырожденные сегменты, перекрывающиеся сегменты, горизонтальные и вертикальные сегменты и сегменты, пересекающиеся по их конечным точкам) и иметь возможность справляться с постоянно меняющимся набором данных.
Процесс, который я оптимизировал, мог вызывать алгоритм поиска пересечений сотни тысяч раз при постоянной модификации набора данных, над которым он работал.Это также сделало довольно много других вещей помимо поисков пересечения.Используя наивный подход, это заняло около 6 часов.
Первоначально я начал работать над реализацией BO, основанной на этой статье (ищите Надежную и эффективную реализацию алгоритма развертки линии для задачи пересечения отрезка прямой линии здесь ).К сожалению, это было довольно сложно понять (странная логика и проблемы со стабильностью чисел), и мне пришлось отказаться от него.Оглядываясь назад, я должен был попытаться открыть его с открытым исходным кодом, но сейчас уже слишком поздно.
Во всяком случае, тогда я попробовал подход R-Tree, который прекрасно работал и сумел сократить эти колоссальные 6 часов довсего лишь 30 минут, где большая часть была потрачена в другом месте.Это несмотря на необходимость постоянно обновлять сегменты в R-дереве.
Так что да, это того стоит, если ваш набор данных достаточно велик или если вы делаете достаточно поисков.Я все еще настоятельно рекомендую сначала попробовать метод грубой силы и, если он недостаточно быстр, перейти на R-Tree.