Реализация детерминированного алгоритма Sharir или Aurenhammer для вычисления пересечения/объединения кругов 'N'
Проблема нахождения пересечения/объединения дисков/кругов 'N' на плоской плоскости была сначала предложена M. Я. Shamos в его тезисе 1978 года:
Shamos, M. Я. “Вычислительная Геометрия” кандидатская диссертация, Йельский Унив, Нью-Хейвен, Коннектикут 1978.
С тех пор, в 1985, Micha Sharir представил O (n log2n), время и O (n) располагают детерминированный алгоритм с интервалами для проблемы пересечения/объединения диска (на основе измененных Диаграмм Вороного): Sharir, M. Пересечение и самые близкие парные проблемы для ряда плоских дисков. SIAM.J Comput. 14 (1985), стр 448-468.
В 1988 Franz Aurenhammer представил более эффективный O (n, регистрируют n), время и O (n) алгоритм пространства для кругового пересечения/объединения с помощью схем питания (обобщения Диаграмм Вороного): Aurenhammer, F. Улучшенные алгоритмы для дисков и шаров с помощью схем питания. Журнал Алгоритмов 9 (1985), стр 151-161.
Ранее в 1983 Paul G. Spirakis также представил O (n^2) время детерминированный алгоритм и O (n) вероятностный алгоритм: Spirakis, P.G. Очень Алгоритмы FAST для области Объединения Многих Кругов. Член палаты представителей 98, Отдел. Comput. Наука, Courant Институт, Нью-Йоркский университет, 1983.
Я искал любые реализации алгоритмов выше, фокусируясь на вычислительных пакетах геометрии, и я ничего еще не нашел. Поскольку ни один не кажется тривиальным для осуществления, это было бы действительно аккуратно, если кто-то мог бы указать на меня в правильном направлении!
Возможно, пакет конструктивной стереометрии (CSG) имел бы функцию площади поверхности перекрывающихся круговых примитивов?
1 ответ
Я потратил некоторое время на изучение алгоритмов для вычисления объединения множества шаров - как вы упомянули, это делается с помощью обобщенных диаграмм Вороного.
В библиотеке CGAL есть пакет, реализующий объединение шаров. Это на одно измерение выше, чем то, что вас интересует, и он не обрабатывает пересечения. так что, вероятно, не получится.
Если вы работаете в двух измерениях, проблема эквивалентна нахождению выпуклого корпуса в трех измерениях. Вы можете использовать материал выпуклого корпуса из CGAL или другого пакета.
Если вы ищете реализацию конкретных алгоритмов, которые вы упомянули, я не могу вам помочь. Но если вы просто хотите найти диаграмму мощности, которая позволит вам легко вычислять объединения и пересечения, это может быть проще, чем вы думаете, чтобы сделать свой собственный, используя алгоритм 3D выпуклого корпуса.
Извините за полусерьезный ответ, но мы можем начать с чего-то и посмотреть, насколько гибкими возможностями вы обладаете.
Edit: Существует также пакет 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.