Реализация детерминированного алгоритма Шарира или Аурнхаммера для вычисления пересечения / объединения 'N' окружностей

Question

Проблема нахождения пересечения / объединения 'N' дисков / кругов на плоской плоскости была впервые предложена М. И. Шамосом в его диссертации 1978 года:

Шамос М.И. «Вычислительная геометрия» к.т.н. диссертация, Йельский университет, Нью-Хейвен, Коннектикут, 1978.

С тех пор, в 1985 году, Миха Шарир представил O (n log2n) детерминистический алгоритм времени и пространства O (n) для задачи пересечения / объединения дисков (на основе модифицированных диаграмм Вороного): Шарир, М. Пересечение и ближайшие пара задач для набора плоских дисков. SIAM .J Comput. 14 (1985), сс. 448-468.

В 1988 году Франц Аурнхаммер представил более эффективный алгоритм O (n log n) времени и пространства O (n) для пересечения / объединения окружностей с использованием степенных диаграмм (обобщений диаграмм Вороного): Аурнхаммер Ф. Улучшенные алгоритмы для дисков и шары с использованием силовых диаграмм. Журнал алгоритмов 9 (1985), с. 151-161.

Ранее, в 1983 году, Пол Г. Спиракис также представил O (n ^ 2) -детерминистический алгоритм времени и O (n) вероятностный алгоритм: Spirakis, P.G. Очень быстрые алгоритмы для области объединения многих кругов. Rep. 98, Dept. Comput. Sci., Courant Institute, Нью-Йоркский университет, 1983.

---

Я искал любые реализации описанных выше алгоритмов, сосредоточив внимание на пакетах вычислительной геометрии, и пока ничего не нашел. Так как ни один из них не кажется простым для практического применения, было бы очень здорово, если бы кто-то мог указать мне правильное направление!

Возможно, пакет конструктивной твердой геометрии (CSG) будет иметь элемент площади поверхности для перекрывающихся круговых примитивов?

Answer 1

Я потратил некоторое время на изучение алгоритмов вычисления объединения множества шаров - как вы упоминаете, это делается с использованием обобщенных диаграмм Вороного.

Библиотека CGAL имеет пакет, который реализует объединение шаров . Это на одно измерение выше того, что вас интересует, и оно не обрабатывает пересечения. так что, вероятно, нет сигары.

Если вы работаете в 2-х измерениях, проблема эквивалентна поиску выпуклой оболочки в 3-х измерениях. Вы можете использовать материал с выпуклой оболочкой из CGAL или другой упаковки.

Если вы ищете реализации конкретных алгоритмов, которые вы упомянули, я не могу вам помочь. Но если вы просто хотите найти диаграмму мощности, которая позволит вам легко вычислять объединения и пересечения, вам будет проще, чем вы думаете, свернуть свое собственное с использованием алгоритма 3D выпуклой оболочки.

Извините за полуиспеченный ответ, но мы также можем начать где-нибудь и посмотреть, насколько у вас гибкость.

Редактировать: Существует также пакет CGAL для двухмерных диаграмм мощности: http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html.

Кроме того, @RGrey нашел библиотеку CGAL для вычисления двумерных логических значений для обобщенных многоугольников, включая круги в http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html.

Answer 2

В CGAL нет реализации 2D-схемы мощности. Ссылка, предложенная выше (http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html), предназначена для аддитивной взвешенной диаграммы Вороного, которая использует евклид + вес вместо евклида ^ 2 + вес (как это делают диаграммы мощности).