Implemente um algoritmo para triangular um polígono simples.
Passo 1
O problema pede para implementar um algoritmo que, dado um polígono simples (sem auto-interseções) com
vértices em ordem CCW, o parta em triângulos cuja união refaz exatamente o polígono original. O método clássico e fácil de implementar é o “ear clipping” (corte de orelhas), que funciona em
. Para isso, vamos precisar:
– Representar o polígono como uma lista duplamente encadeada de vértices na ordem CCW.
– Testar se um triplo de vértices forma um vértice convexo.
– Testar se o triângulo não contém nenhum outro vértice do polígono no seu interior (definição de “orelha”).
– Iterar removendo orelhas até sobrar apenas um triângulo.
– Representar o polígono como uma lista duplamente encadeada de vértices na ordem CCW.
– Testar se um triplo de vértices
– Testar se o triângulo
– Iterar removendo orelhas até sobrar apenas um triângulo.
Passo 2
Definição de vértice convexo. Dados três vértices consecutivos
em CCW, calculamos o sinal do produto vetorial (cross) em 2D:
Se
,
é convexo (volta para dentro do polígono).
Passo 3
Definição de orelha. O vértice
é uma orelha se e somente se:
-
é convexo. - Nenhum outro vértice do polígono (além de
) está estritamente dentro do triângulo .
Para testar “ponto dentro de triângulo” usamos coordenadas baricêntricas ou método de sinais dos três sub-produtos vetoriais.
Passo 4
Algoritmo principal (ear clipping):
- Constrói lista duplamente encadeada
de todos os índices na ordem CCW. - Inicializa lista de triângulos vazia
. - Enquanto
:
a. Percorre cada vérticeem , com vizinhos e .
b. Sefor orelha, então:
i. Adiciona triânguloem .
ii. Removede .
iii. Interrompe o for e recomeça do início. - Ao final sobra exatamente um triângulo em
; adiciona-o a . - Retorna
.
Passo 5
Pseudocódigo final:
function Triangulate(P):
// P[0..n-1] é o vetor de pontos em CCW
V = \(doubly_linked_list\)(0,1,2,…,n-1)
T = empty list of triangles
while V.size > 3:
for v in V:
u = V.prev(v)
w = V.next(v)
if isConvex(P[u],P[v],P[w]) and isEmpty(P,u,v,w,V):
T.append((u,v,w))
V.remove(v)
break
// resto final é um triângulo
u = V[0]; v = V[1]; w = V[2]
T.append((u,v,w))
return T
function isConvex(A,B,C):
return cross(A,B,C) > 0
function isEmpty(P,u,v,w,V):
for q in V:
if q != u and q != v and q != w:
if pointInTriangle(P[q],P[u],P[v],P[w]):
return false
return true
function cross(A,B,C):
return (B.x - A.x)*(C.y - B.y) - (B.y - A.y)*(C.x - B.x)
function pointInTriangle(Q,A,B,C):
// usa sinal de cross para os três pares
// retorna true se Q está estritamente dentro
// (ver implementações padrão de teste baricêntrico)
Resposta
O algoritmo acima triangula um polígono simples por “ear clipping” em
.