Как преобразовать набор 2D точек (многоточечный) в многоугольник?

Question

У меня есть набор плотных, неравномерно распределенных 2D точек («разбросанных повсюду»). Они могут храниться в одном объекте MULTIPOINT WKT, включая «дыры» или - при необходимости - в виде треугольников Делоне.

Как бы вы преобразовали это в многоугольник, то есть одну внешнюю границу и ноль, одну или несколько внутренних границ?

P.S. Это не самый большой вмещающий многоугольник, который я ищу (это может быть решено с помощью ConvexHull или ConcaveHull). Я ищу настоящий многоугольник с той же формой, что и набор рассеянных точек (включая внутреннюю границу).

Answer 1

Используйте QHull: http://www.qhull.org/

Это стандарт де-факто для такого рода вещей.

Answer 2

Ваш вопрос звучит для меня как «найти многоугольник с заданным набором точек в качестве вершин». Верна ли эта интерпретация?

Если это так, вы можете сделать следующее: Создать выпуклую оболочку из своеготочки.Уберите эти точки из рассмотрения и возьмите выпуклый корпус из оставшихся точек.Продолжайте в том же духе, пока не останется больше точек.Промежуточным результатом будет последовательность выпуклых многоугольников, вложенных друг в друга.Вы можете превратить их в один многоугольник, соединив каждую последующую пару многоугольников.Вы соединяете два многоугольника, удаляя ребро из каждого и соединяя полученные конечные точки «наоборот».Необходимо позаботиться о том, чтобы эти соединения не перекрывали что-либо еще, но это не должно быть слишком сложно.

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