Блог

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

_{(источник: cgal.org)}

Может быть, для этого есть хорошая библиотека Java?

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

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

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

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

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

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

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

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

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

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