O controle da triangulação

Esta é a última etapa do algoritmo. Queremos obter uma triangulação quase regular de $S$ que seja bem próxima a uma ótima. Para isso, adotamos o método de ``avanço de frente'', triangulando $S$ por exaustão como segue:

Primeiramente fixamos a orientação de $S$ dada pelo vetor que aponta para fora de $S$. Fixamos um ponto $q_0$ em $S$, definimos esse ponto como vértice da triangulação. Fixamos uma direção no plano tangente a $S$ em $q_0$ e traçamos uma aresta partindo desse ponto com medida $l$, isso é possível pela solução do Problema 1. Obtemos assim, um ponto $q_1\in S$ que também será um vértice da triangulação. Encontramos um ponto $q_2\in S$ tal que $q_0$,$q_1$,$q_2$ sejam vértices de um triângulo equilátero e a poligonal fechada orientada $\overrightarrow{q_0q_1q_2q_0}$ tenha a orientação induzida pela orientação de $S$ dada pelo vetor que aponta para fora de $S$ com origem em um ponto qualquer no interior do triangulo $\triangle q_0q_1q_2$. Essa poligonal divide $S$ em duas regiões: uma triangulada e outra não. Ressaltamos que a orientação da poligonal é invertida se tormarmos como origem do vetor que aponta para fora de $S$ um ponto fora da área triangula de $S$. Fazemos então iterações sucessivas na área triangulada acrescentando um novo triângulo a esta a cada iteração, de forma que a nova área triangulada de $S$ seja conexa e não degenerada, ou seja, pelo menos uma das arestas do triângulo acrescentado deve ser uma aresta do bordo da área triangulada de $S$ obtida na iteração anterior e esse triângulo esteja contido na área não triangulada de $S$. Se todos os triângulos adicionados tiverem áreas aproximadamente iguais então, visto que $S$ tem área finita, após um número finito de iterações obteremos a triangulação desejada.

Visto que o bordo da área triangulada de cada iteração contém pelo menos uma aresta do próximo triângulo a ser adicionado, podemos estabelecer um controle da triangulação fazendo com que todas as arestas desse bordo tenha o mesmo comprimento, sempre que possível.

Seja $\Gamma = \overrightarrow{p_0p_1...p_np_0}\subset \mathbb{R}^2$ uma poligonal fechada simples, orientada no sentido anti-horário. Essa poligonal limita duas regiões conexas do plano: uma região interior e uma região exterior a $\Gamma$. Seja $g:\mathbb{R}^2\rightarrow S$ uma função de classe $C^1$ injetiva e que omite apenas um ponto. A poligonal $\widetilde{\Gamma}$, obtida ligando-se a imagem dos $p_j$'s por segmentos de reta na mesma ordem em que os $p_j$'s são ligados em $\Gamma$, divide $S$ em duas regiões conexas que identificaremos como interior e exterior a $\widetilde{\Gamma}$ conforme seja imagem da região interior ou exterior a $\Gamma$ em $\mathbb{R}^2$ (o ponto omitido pertencerá à região exterior a $\widetilde{\Gamma}$). Essa definição permite-nos falar em ângulo externo e interno nos vértices de $\Gamma$ e $\widetilde{\Gamma}$, Veja a Figura 2.

Figura:

Denotamos por $q_j$ o ponto imagem $g(p_j)\in S$. Suponha que o ângulo externo em $p_j$ seja $\alpha$ e que o ângulo externo em $q_j$ seja $\beta$.

Problema 2:

Dados $l\in \mathbb{R}^+$ compatível com a geometria de $S$, $\gamma\in (0,\pi/2)$ com $\gamma < \beta$, encontrar $p\in\mathbb{R}^2$ um ponto na região exterior a $\Gamma$ tal que se $q=g(p)\in S$ então $\Vert q-q_j\Vert=l$ e o ângulo medido na região exterior a $\widetilde{\Gamma}$, medido na orientação de $S$ entre os vetores $\overrightarrow{q_jq_{j+1}}$ e $\overrightarrow{q_jq}$ seja $\gamma$.

Problema 3:

Seja $q_j\in\widetilde{\Gamma}$. Dado $l\in \mathbb{R}^+$, encontrar $p\in\mathbb{R}^2$ um ponto na região exterior a $\Gamma$ tal que $\Vert g(p)-q_{j+1}\Vert=l$ ou $\Vert g(p)-q_{j-1}\Vert=l$ (preferenciamente ambos) e os ângulos medido na região exterior a $\widetilde{\Gamma}$ na orientação de $S$ entre os vetores $\overrightarrow{q_jq_{j+1}}$ e $\overrightarrow{q_jq}$ e entre os vetores $\overrightarrow{q_jq}$ e $\overrightarrow{q_jq_{j-1}}$ sejam iguais.

De posse da solução destes dois problemas podemos obter a triangulação desejada. De fato, após o cálculo dos três primeiros vértices, a cada nova iteração, é possível que um dos casos abaixo aconteçam, então resolvemos eles na mesma ordem de prioridade quem aparecem abaixo:

Caso 1: Um dos ângulos externos a $\widetilde{\Gamma}$ é menor que $60^o$. Veja a Figura 3.

Figura:

Suponha que isso ocorra em um vértice genérico $q_j$. Nesse caso inserimos na triangulação o triângulo $\triangle q_{j-1}q_jq_{j+1}$, então o ponto $q_j$ deixará de fazer parte do bordo da área triangulada, assim como as aresta que eram adjacentes a ele, ou seja, $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_{j-1}q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_{j-1}q_{j+1}...}$.

Caso 2: Existe uma aresta de $\widetilde{\Gamma}$ de comprimento $s\not = l$, (por exemplo: arestas geradas no Caso 1). Veja a Figura 4.

Figura:

Seja $\overrightarrow{...q_jq_{j+1}...}$ essa aresta. Nesse caso usamos a solução do Problema 2 e encontramos $p\in\mathbb{R}^2$ exterior a $\Gamma$ tal que $\Vert g(p)-q_j\Vert=l$ e $\gamma=\textrm{acos}(s/2l)$, nesse caso obteremos $\Vert g(p)-q_{j+1}\Vert=l$. Se existe algum vértice de $\widetilde{\Gamma}$ não-adjacente a $q_j$ cuja distância a $g(p)$ é menor que $l$ passamos ao Caso 4, caso contrário, inserimos na triangulação o triângulo $\triangle q_{j}g(p)q_{j+1}$ e $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_{j-1}g(p)q_{j+1}...}$. Se após essa iteração o novo ângulo externo em $q_j$ for menor que $60^o$, desfazemos a iteração e passamos ao Caso 3 abaixo.

Caso 3: Seja $q_j$ um vértice de $\widetilde{\Gamma}$ a partir do qual é possível inserir uma aresta de lado $l$ mas essa aresta divide o ângulo externo de $q_j$ em dois ângulos cuja soma é menor que $120^o$. Veja a Figura 5.

Figura:

Nesse caso usamos a solução do Problema 3. Encontramos $p\in\mathbb{R}^2$ exterior a $\Gamma$ tal que $\overrightarrow{q_jg(p)}$ divida o ângulo externo de $q_j$ em dois ângulos iguais e $\Vert g(p)-q_{j+1}\Vert=l$. Se $\Vert q_j-q_{j+1}\Vert=\Vert q_j-q_{j-1}\Vert$ então teremos, também, $\Vert g(p)-q_{j-1}\Vert=l$. Se a aresta inserida dividir o ângulo externo de $q_j$ em dois ângulos menores que $45^o$, então inserimos na triangulação o triângulo $\triangle q_{j-1}q_jq_{j+1}$ e $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_{j-1}q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_{j-1}q_{j+1}...}$. Se existe algum vértice de $\widetilde{\Gamma}$ não-adjacente a $q_j$ cuja distância a $g(p)$ é menor que $l$ passamos ao Caso 4, caso contrário inserimos na triangulação os triângulos $\triangle q_{j-1}g(p)q_j$ e $\triangle q_jg(p)q_{j+1}$ e $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_{j-1}q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_{j-1}g(p)q_{j+1}...}$.

Caso 4: Existe um vértice em $\widetilde{\Gamma}$, a partir do qual não é possível inserir uma nova aresta de comprimento $l$ (isso acontece, por exemplo, nos últimos passos da triangulação). Veja a Figura 6.

Figura:

Se o ângulo em $q_{j-1}$ ou em $q_j$ ou em $q_{j+1}$ for menor que $90^o$, tomamos aquele que tem o menor ângulo, que, sem perda de generalidade podemos supor que este seja $q_j$, então inserimos na triangulação o triângulo $\triangle q_{j-1}q_jq_{j+1}$ e $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_{j-1}q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_{j-1}q_{j+1}...}$ (note que se o ângulo escolhido fosse $q_{j-1}$ ou $q_{j+1}$ a operação acima também afetaria o ângulo externo em $q_j$). Se não tivermos a propriedade acima usamos a solução do Problema 1 e inserimos a partir de $q_j$ uma aresta cujo comprimento seja a metade da menor distância entre $q_j$ e os outros vértices não-adjacentes a ele usando a mesma regra que foi usada no Caso 2 em relação ao ângulo e finalizamos, também, como no Caso 2. Se o ângulo externo em $q_j$ for como no Caso 3, inserimos uma aresta com o comprimento descrito acima de forma que divida esse ângulo em dois ângulos iguais e finalizamos como no Caso 3.

Caso 5: Se nenhum dos casos acima ocorrem.

Escolhemos um vértice $q_j$ de $\widetilde{\Gamma}$. Calculamos $p\in\mathbb{R}^2$ exterior à $\Gamma$ de forma que o triângulo $\triangle q_jq_{j+1}g(p)$ seja equilátero. Incluimos esse triângulo na triangulação e então $\widetilde{\Gamma}$ deixa de ser $\overrightarrow{...q_jq_{j+1}...}$ e passa a ser $\overrightarrow{...q_jg(p)q_{j+1}...}$.

Solução do Problema 2:

Seja $\alpha$ o ângulo externo a $p_j\in\Gamma$. Pela solução do Problema 1, para todo $t\in (0,\alpha)$ encontramos $p_l(t)\in\mathbb{R}^2$ exterior a $\Gamma$ tal que o ângulo entre $\overrightarrow{p_jp_{j+1}}$ e $\overrightarrow{p_jp_l(t)}$ seja $t$ e tal que $\Vert q_j - g(p_l(t))\Vert=l$. Temos, portanto, bem definidas, as funções $h_l:(0,\alpha)\rightarrow (0,\beta)$ e $\overline{h_l}:(0,\alpha)\rightarrow (0,\beta)$, onde $\beta$ é o ângulo externo a $q_j$ em $\widetilde{\Gamma}$, dadas por $h_l(t)= \textrm{ang}(\overrightarrow{q_jq_{j+1}},\overrightarrow{q_jg(p_l(t))})$ e $\overline{h_l}(t)= \textrm{ang}(\overrightarrow{q_jg(p_l(t))},\overrightarrow{q_jq_{j-1}})$, onde $\textrm{ang}(\cdots,\cdots)$ denota o ângulo entre dois vetores, medido na orientação de S (Nota: $h_l$ e $\overline{h_l}$ tem a mesma classe de diferenciabilidade de $g$).

Para resolvermos este problema o ideal seria procedermos como na solução do Problema 1, aplicando o Método de Newton à função $h_l$, mas $h_l$ aparesce de forma implicita, tornando esta opção um pouco complicada devido à necessidade dos valores da derivada de $h_l$. Em vez disto, optamos por um método alternativo, similar ao Método de Newton, usando o fato de que $h_l$ é estritamente crescente e tem domínio e imagem limitados.

Primeiro escolhemos um valor inicial para $t$, então executamos o algoritmo descrito abaixo:

$t_0=0$;

$t=\dfrac{1}{2} \cdot \dfrac{\alpha}{\beta} \cdot \gamma$;

$r=2$;

$b_0=0$;

while( $\vert r-1\vert>0.01$)

{

$b_1=h_l(t)$;

$r=\dfrac{\gamma}{b_1}$;

$c=b_1-b_0$;

$c=(\vert c\vert>0.000001)?(t-t_0)/c:1000000\cdot c$;

$t_0=t$;

$t=(\vert c\vert>0.1)?(\gamma - b_1)\cdot c + t_0 : r\cdot t_0$;

$t=\textrm{clamp}(t,t_0/2,t_0 +(\alpha-t_0)/10)$;

$b_0=b_1$;

} return $t$;

Aqui, a função ``clamp ''é definida por:

$\textrm{clamp}(a,b,c)=(a<b)?b:((a>c)?c:a)$;

O ponto desejado é, então, o ponto $p_l(t)$ obtido na solução do Problema 1.

Solução do Problema 3:

O algoritmo que usamos para resolver este problema é similar ao que usamos na solução do Problema 2, a diferença é que, neste caso, o comprimento da aresta a ser inserida e o ângulo que esta aresta deve formar com a aresta $\overrightarrow{q_jq_{j+1}}$ são alterados a cada ``loop''do algoritmo. Esse algoritmo é descrito abaixo:

$t_0=0$;

$t=\alpha/2$;

$r=2$;

$b_0=0$;

$d=l$;

while( $\vert r-1\vert>0.01$)

{

$b_1=h_d(t)$;

$b_2=\overline{h_d}(t)$;

$r=(b_2/b_1 +1)/2$;

$\gamma = b_1\cdot r$;

$c=b_1-b_0$;

$c=(\vert c\vert>0.000001)?(t-t_0)/c:1000000\cdot c$;

$t_0=t$;

$t=(\vert c\vert>0.1)?(\gamma - b_1)\cdot c + t_0 : r\cdot t_0$;

$t=\textrm{clamp}(t,t_0/2,t_0 +(\alpha-t_0)/10)$;

$d = ( s < l ) ? s\cdot\cos(\gamma) + \sqrt{\textrm{max}(0,l^2-s^2\cdot\textrm{sen}^2(\gamma))}: 2\cdot l\cdot \cos(\gamma)$;

$b_0=b_1$;

} return $(t,d)$;

Aqui, $d$ é o comprimento da aresta a ser inserida, $\gamma$ é o ângulo que ela deve formar com a aresta $\overrightarrow{q_jq_{j+1}}$ e $s$ denota o comprimento da aresta $\overrightarrow{q_jq_{j+1}}$. A função `` $\textrm{max}(a,b)$''retorna o maior entre os números $a$ e $b$. A restrição a $d$ é para evitar que tenhamos arestas muito grandes.

O ponto desejado é, então, o ponto $p_d(t)$ obtido na solução do Problema 1.