Нахождение вогнутой оболочки набора точек, такой, что каждая точка находится на границе

Question

Поэтому я пытаюсь сделать сложные многоугольники из набора случайно сгенерированных вершин в 2D. Я хотел бы позволить существовать вогнутым многоугольникам, а также гарантировать, что каждая вершина в наборе включена в границу (поэтому алгоритм должен уметь обрабатывать выпуклые и вогнутые оболочки), а также гарантировать, что линии, созданные Граница никогда не пересекается. В каждой версии алгоритма генерации вогнутых оболочек предполагается, что допустимо иметь разные уровни вогнутости и что некоторые точки могут не являться частью границы.

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

Answer 1

Мне пришлось придумать решение этой проблемы с изюминкой. Мне пришлось визуализировать набор рандомизированных точек в основном в вогнутую оболочку. Я использовал алгоритм марширующих кубов, генерирующий вогнутую оболочку! В основном я просто подсчитывал и взвешивал каждую полученную точку и вычислял крайние индексы для их рендеринга в зависимости от моей сетки значений. https://stemkoski.github.io/Three.js/Marching-Cubes.html я ориентировался на эту реализацию.... получайте удовольствие :)