Construindo o contorno de um polígono (em triangulação um determinado)

Question

Como eu iria sobre a construção do contorno do polígono 2d que é formado de apenas triângulos e pode ter buracos eo contorno exterior pode ser côncava / convexa e os buracos também pode ser côncava / convexo.

A partir do que eu estou lendo aqui parece que é exatamente o inverso do problema triangulação. Sabe quaisquer artigos que tratam este tipo de problema?

Tem octrees / quadtrees relevantes para isso?

Answer 1

Eu acho que você tem os dados na forma de conjuntos de três pontos, que constituem um triângulo "cheio", que estes triângulos são contíguos ao longo das bordas, e que todos os vértices que serão cantos da forma completa também são vértices de todos os triângulos que tocam esse ponto. Você, então, apenas tem que encontrar todas as arestas que não são o dobro, ou seja, não pertencem a dois triângulos contíguos.

Answer 2

Eu acho que você pode resolver o seu problema através da criação de uma estrutura de dados topológica para representar o seu conjunto de triângulos, e depois usar essa estrutura para iterar em ordem sobre o triângulo bordas que se encontram na fronteira.

Por exemplo: você pode criar uma estrutura de dados halfedge. Supondo que você inserir halfedges mesmo no limite (corretamente), interagindo sobre o contorno limite é tão simples como localizar um halfedge na fronteira e, em seguida, a iteração sobre ele de "next" ponteiro até você voltar ao halfedge você começou.

À semelhança do halfedges, você pode usar outras estruturas topológicas como alado de ponta, etc., mas o conceito é o mesmo.