Создать вогнутый многоугольник, проходящий через все заданные точки

Question

Учитывая набор точек, я хочу создать вогнутый непересекающийся многоугольник, используя эти точки. Выпуклая оболочка сведет на нет вогнутую часть, а расположение их по координатам x/y или углам от центра приведет к появлению остроконечных артефактов. Есть ли простой способ сделать это?

Пример вида многоугольника, который я хочу создать:

Answer 1

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

В верхнем примере показано, где работает MST (с присоединением первой и последней вершин в полученной полилинии)

Нижний пример - это то, что происходит, если края периметра оказываются слишком близко.