Построение контура многоугольника (в частности, триангуляции)

Question

Как бы я приступил к построению контура 2d-многоугольника, который сформирован только из треугольников, и в нем могут быть отверстия, а внешний контур может быть вогнутым / выпуклым, и отверстия также могут быть вогнутыми / выпуклыми.

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

Имеют ли к этому отношение восьмеричные / квадратичные деревья?

Answer 1

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

Answer 2

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

Например:вы можете создать структуру данных halfedge.Предполагая, что вы вставляете полукруги даже на границе (правильно), выполнить итерацию по контуру границы так же просто, как найти один полукруг на границе, а затем выполнять итерацию по его указателю "next", пока вы не вернетесь к полукругу, с которого начали.

Аналогично halfedges, вы можете использовать другие топологические структуры, такие как winged-edge и т.д., Но концепция та же.