Упрощенные вогнутые корпуса

Question

Задача:

Дано : n точек, сильно коррелированных с 3d-выпуклым k-сторонним многоугольником, где n >> k

Найти : наиболее подходящая вогнутая оболочка, которая соответствует исходной геометрии точек

---

Попытки решения:

Предупреждение: псевдокод

segments = []
for each point in image:
    #segment points into planes via comparing approximate normals
    #actual implementation is more complicated
    findSegment(image,point)
for each segment in image:
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment
    transform(segment, segment.normal)
    edges = findEdges(segment)
    polygonHull = reconstructPolygon(edges)
    #transform back to original coordinate system
    transform(segment, segment.normal)

---

Пример:

 ___
|   |               |
|    \__    ==>     |   ___
|       |           |__/  /_____
|_______|          /  /   \_
                  /  /_____/
                 /

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

Выходные данные будут вершинами многоугольника в 3d точках.

---

Мой вопрос: есть ли лучший способ подойти к этой проблеме?Проблема с вышеуказанным решением состоит в том, что точки могут быть шумными.Кроме того, растеризация точек в 2d с последующим формированием поиска ребра довольно затратна.

Любые указатели были бы хорошими.Заранее спасибо

Answer 1

Если ваши вогнутые углы не слишком острые, я мог бы попробовать провести триангуляцию Делоне для набора точек.Области Вороного точек на границе будут иметь тенденцию быть либо бесконечными, либо намного длиннее, чем внутренние.Аналогично, ячейки на границе, которые связаны с одной гранью многогранника, будут иметь тенденцию выравниваться в направлении, почти нормальном к грани, с которой они связаны, так как все они будут длинными и тонкими, а их длинные осипочти параллельно и указывает на многоугольник.В своего рода квазипсевдокоде

Compute Delaunay triangulation
Collect long thin Voronoi regions
Partition the Voronoi regions into clusters that are nearby and nearly parallel.
Create faces normal to the axes of the Voronoi regions. 

Edit Теперь я вижу, что вы просто хотите многоугольник.Вышеуказанный подход работает, но, вероятно, лучше всего сделать это в два этапа.Сначала найдите плоскость, в которой лежит многоугольник, и, возможно, достаточно наименьших квадратов для небольшой выборки точек.Спроецируйте точки на плоскость (это в значительной степени то, что вы делали), затем вычислите 2-ю триангуляцию Делоне, чтобы найти граничные точки, и продолжайте, как описано выше.

Answer 2

Прежде всего, вы должны выбрать представление для вашей сетки.В 2D я реализовал алгоритм вогнутой оболочки Python, используя это представление: структура данных с половиной ребра .

Тогда алгоритм в 2D (вы должны адаптироваться к 3D) может быть близок к алгоритму альфа-формы, по Эдельбруннеру.

Answer 3

Звучит так, как будто вы хотите вычислить вогнутую оболочку набора точек в трехмерном пространстве, спроецированного на плоскость.2D случай обсуждается более подробно здесь .