Java библиотека для создания прямого скелета?

Question

У меня на входе есть 2D многоугольник с отверстиями, и мне нужно найти его прямой скелет, как на картинке:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/exterior_skeleton.png

Возможно, есть хорошая библиотека Javaдля этого?

А если нет, можете ли вы указать мне хорошее объяснение алгоритма, чтобы я мог реализовать его сам?(Я не нашел хороших ресурсов в Google)

Answer 1

Я написал это недавно. Не уверен, что это достаточно надежно. https://github.com/twak/campskeleton

(отредактировано на 2018 год ...)

Answer 2

См. http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html, который содержит апплет.

Answer 3

Вы можете использовать JTS Topology Suite .Это очень эффективная библиотека, которую я использовал в ряде проектов - никогда не для скелета, но это возможно.

Answer 4

Edit: Ах. Я вижу, что « Прямой скелет » - это технический термин. Статья в Википедии ссылается на несколько алгоритмов. Вы смотрели на них?

---

Насколько я понимаю, у вас есть (выпуклый?) Многоугольник. Из него вы вычитаете 1 или более (потенциально невыпуклых) многоугольников. Вы хотите превратить результат в набор полигонов без дырок. Существуют ли дополнительные правила, которые вы пытаетесь применить?

Мне трудно придумать набор правил из приведенного вами примера. Внешние многоугольники невыпуклые; так что не похоже, что вы пытаетесь найти выпуклый набор для представления результата (что является относительно обычной задачей).

Если бы вы могли использовать разбивку, показанную ниже, алгоритм довольно прост. Вы можете уточнить?

Answer 5

Могу я спросить вас, какова ваша цель найти Прямой скелет? Это личное или коммерческое? Мне было бы интересно узнать, как вы используете его для решения проблем в реальном времени? У меня есть библиотека Java, которая делает это. Мой алгоритм указан здесь http://web.stcloudstate.edu/rsarnath/skeleton/definition.htm