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 n 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 O(n^2). 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 (u,v,w) forma um vértice convexo.
– Testar se o triângulo (u,v,w) 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.

Passo 2

Definição de vértice convexo. Dados três vértices consecutivos u,v,w em CCW, calculamos o sinal do produto vetorial (cross) em 2D:
\text{cross}(u,v,w) = (v_x - u_x)\,(w_y - v_y)\;-\;(v_y - u_y)\,(w_x - v_x).
Se \text{cross}(u,v,w)>0, \angle uvw é convexo (volta para dentro do polígono).

Passo 3

Definição de orelha. O vértice v é uma orelha se e somente se:
  1. (u,v,w) é convexo.
  2. Nenhum outro vértice do polígono (além de u,v,w) está estritamente dentro do triângulo (u,v,w).
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):
  1. Constrói lista duplamente encadeada V de todos os índices 0,1,\dots,n-1 na ordem CCW.
  2. Inicializa lista de triângulos vazia T.
  3. Enquanto \lvert V\rvert>3:
    a. Percorre cada vértice v em V, com vizinhos u=\text{prev}(v) e w=\text{next}(v).
    b. Se (u,v,w) for orelha, então:
    i. Adiciona triângulo (u,v,w) em T.
    ii. Remove v de V.
    iii. Interrompe o for e recomeça do início.
  4. Ao final sobra exatamente um triângulo em V; adiciona-o a T.
  5. Retorna T.

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 O(n^2).

Exercícios de Livros Relacionados