Тут в программе алгоритм проверки наличия пересечения в множестве отрезков, только самого факта наличия пересечения, без возврата конкртной точки пересечения, пары отрезков и т.д.
Реализовано два метода
- Наивный - проверка всез со всеми, что занимает
O(n^2) - Алгоритм заметающей прямой, где в качестве структуры данных для хранения отрезков используется B-Tree (2-3 Tree, не B+ Tree), его сложность -
O(n*log(n))
Сами методы находятся в service.cpp
Данная стуктура данных реализована в виде шаблонного класса в заголовочных файлах, находится в папке headers. Там класс звена и самого дерева. (мне кажется, что наибольший инетерес здесь представляет именно этот класс).
Спасибо этому человеку, без его разбора, я бы вряд-ли написал это дело в разумные сроки.
-
склоинруйте репозиторий
git clone https://github.com/nol0n/segment_intersection.git -
создайте папку build (я предпочитаю out-of-source build, когда папка с бинарниками лежит рядом с папкой репозитория)
mkdir ..\build -
перейдите в папку build
cd .\build -
сконфигурирейте проект (при работе я использовал mingw)
cmake ..\segment_intersection -G Ninja -
соберите проект
cmake --build .
В папке директория_сборки\application будет seg_test, при его запуске будет выполнено два небольших теста, где сравниваается быстродействие алгоритмов. Результаты будут записаны в файлы рядом с исполняемым файлом.