Polygon Sponsor

Polygon Set Algorithms Analysis

Большинство нетривиальных алгоритмов в бусте. Библиотека полигонов представляет собой инстанциации общих алгоритмов линий разметки, которые обеспечивают возможность выполнения пересечения сегмента Манхэттена и 45-градусной линии, наложения n-слойной карты, извлечения графа связи и вырезки / булевы.   Эти алгоритмы имеют сложность времени выполнения O(n log n) для n, равную входным вершинам плюс вершинам пересечения.   Алгоритм пересечения сегмента произвольной угловой линии не реализован в виде линии разметки из-за сложностей, связанных с достижением численной устойчивости.   Общий алгоритм пересечения сегментов линий реализован в виде рекурсивного адаптивного эвристического деления и покорения в измерении y с последующей сортировкой сегментов линий в каждом подразделении по координатам x и сканированием слева направо.   По одномерному разложению проблемного пространства как в x, так и в y алгоритм аппроксимирует оптимальную O(n log n) линейную сложность пересечения сегмента Bentley-Ottmann в общем случае. Конкретные примеры входов, которые побеждают одномерное разложение проблемного пространства, могут привести к патологической квадратичной сложности времени выполнения, к которой алгоритм Бентли-Оттмана неуязвим.

Ниже показан логарифмический график времени выполнения по сравнению с размером ввода для входов, которые увеличиваются квадратично по размеру.   Входные данные были получены путем псевдослучайного распределения небольших параллельных прямоугольников оси в пределах квадратной площади, пропорциональной количеству прямоугольников, указанных для каждого испытания.   Таким образом, вероятность возникновения перекрестков остается постоянной по мере роста входного размера.   Поскольку предполагается, что перекрестные вершины являются постоянным фактором входных вершин, мы можем исследовать сложность среды выполнения с точки зрения входных вершин.   Выполненная операция представляла собой объединение (Boolean OR) входных прямоугольников каждым из алгоритмов Манхэттена, 45-градусного и произвольного угла Booleans, которые маркированы как «boolean 90», «boolean 45» и «boolean».   Также показано на графике выполнение алгоритма произвольного угла Booleans до добавления деления и покорения рекурсивного подразделения, которое было описано в paper presented at boostcon 2009.  Наконец, время, необходимое для сортировки входных точек, показано в качестве общей ссылки на время выполнения O(n log n), чтобы поместить данные в контекст.

Мы можем видеть на графике журнала, что сортировка и три Булевы алгоритмы, предоставленные Boost. Библиотека полигонов имеет почти 45-градусное «линейное» масштабирование с эмпирическими показателями чуть больше 1,0 и может наблюдаться в масштабе, пропорциональном O(n log n) для этих входов.   «Старый булев» алгоритм, представленный на boostcon 2009, демонстрирует масштабирование, близкое к ожидаемому масштабированию O(n^1.5).   Поскольку ускорение, обеспечиваемое подходом «разделяй и властвуй», является алгоритмическим, 10-кратное потенциальное улучшение производительности, упомянутое в статье, реализуется на входах 200 000 прямоугольников и больше. Даже для небольших входов прямоугольников 2K алгоритм в 2 раза быстрее, и теперь можно ожидать, что он будет примерно таким же быстрым, как GPC в небольших масштабах, в то время как алгоритмически быстрее в больших масштабах.

Из графика можно сравнить постоянную факторную производительность различных алгоритмов Booleans со временем выполнения std::sort в качестве базовой линии для алгоритмов O(n log n).   Если рассматривать сорт как одну единицу алгоритмической работы O(n log n), мы можем видеть, что манхэттенские булевы стоят примерно пять единиц работы O(n log n), 45-градусные булевы стоят примерно десять единиц работы O(n log n), а произвольные угловые булевы стоят примерно семьдесят единиц работы O(n log n).   Сортировка входных вершин является первым шагом в алгоритме Booleans и, следовательно, обеспечивает жесткую нижнюю границу для времени выполнения оптимального алгоритма Booleans.

Последнее, что следует отметить о производительности алгоритма произвольного угла Booleans, заключается в том, что использование бесконечного прецизионного рационального типа данных для численно надежных вычислений может быть использовано путем включения boost/polygon/gmp_override.hpp и связывания с lgmpxx и lgmp.   Это обеспечивает 100% уверенность в том, что алгоритм будет успешным и произведет выход, прикрепленный к целочисленной сетке с минимум одной целочисленной сеткой ошибок на границах полигона, на которых вводятся точки пересечения.   Тем не менее, тип данных с бесконечной точностью никогда не используется для предикатов (см. презентацию бустеркона или статью для описания надежных предикатов) и используется только для конструкций значений координат пересечения в очень редком случае, когда длинные двойные вычисления пересечения двух линейных сегментов не могут произвести точку пересечения в одной целочисленной единице обоих линейных сегментов.   Это означает, что фактически не существует штрафа за использование бесконечной точности для обеспечения 100% надежности.   Большинство входов будут обрабатываться с помощью алгоритма, не прибегая к GMP.