Weiler-Atherton (1)

Text Material Preview

<p>Weiler-Atherton</p><p>O algoritmo de Weiler-Atherton é um algoritmo de clipping de polígonos, utilizado em</p><p>computação gráfica para determinar quais partes de um polígono estão dentro ou fora de</p><p>uma região de recorte (clipping window) definida por outro polígono. Diferentemente de</p><p>algoritmos mais simples que lidam apenas com recortes retangulares, o Weiler-Atherton</p><p>permite recortes por janelas de recorte com formas complexas e côncavas.</p><p>Conceitos Chave:</p><p>● Polígono Sujeito: O polígono que está sendo recortado.</p><p>● Polígono de Recorte: O polígono que define a área visível (janela de visualização).</p><p>● Lista de Vértices: Ambos os polígonos são representados por listas ordenadas de</p><p>seus vértices.</p><p>● Interseções: Os pontos onde as arestas do polígono sujeito cruzam as arestas do</p><p>polígono de recorte são calculados.</p><p>● Classificação de Interseções: As interseções são classificadas como "de entrada"</p><p>ou "de saída" em relação ao polígono de recorte, indicando se a aresta do polígono</p><p>sujeito está entrando ou saindo da região visível naquele ponto.</p><p>Funcionamento do Algoritmo:</p><p>1. Encontrar Interseções: O algoritmo começa encontrando todas as interseções</p><p>entre as arestas do polígono sujeito e do polígono de recorte.</p><p>2. Criar Listas de Interseções: Duas listas circulares são criadas, uma para o</p><p>polígono sujeito e outra para o polígono de recorte. Cada lista armazena os vértices</p><p>originais do polígono e as interseções encontradas, ordenadas no sentido horário ou</p><p>anti-horário.</p><p>3. Marcar Interseções: As interseções em ambas as listas são marcadas como "de</p><p>entrada" ou "de saída" dependendo da direção da travessia da aresta do polígono</p><p>sujeito em relação ao polígono de recorte.</p><p>4. Encontrar um Ponto de Partida: O algoritmo encontra um vértice no polígono</p><p>sujeito que esteja dentro do polígono de recorte ou uma interseção marcada como</p><p>"de entrada".</p><p>5. Rastreamento do Polígono Recortado: A partir do ponto de partida, o algoritmo</p><p>rastreia o polígono sujeito na ordem da lista de vértices.</p><p>○ Ao encontrar um vértice original do polígono sujeito, ele é adicionado à saída.</p><p>○ Ao encontrar uma interseção "de entrada", o algoritmo muda para a lista do</p><p>polígono de recorte e continua o rastreamento.</p><p>○ Ao encontrar uma interseção "de saída", o algoritmo muda de volta para a</p><p>lista do polígono sujeito.</p><p>6.</p><p>7. Repetir o Rastreamento: O processo de rastreamento continua até que o ponto de</p><p>partida seja alcançado novamente. O algoritmo repete os passos 4 e 5 para cada</p><p>novo ponto de partida encontrado, gerando um novo polígono recortado.</p><p>Vantagens:</p><p>● Generalização: Pode lidar com polígonos côncavos e com múltiplos contornos.</p><p>● Precisão: Produz resultados precisos, lidando corretamente com casos complexos</p><p>de interseção.</p><p>Desvantagens:</p><p>● Complexidade: É mais complexo de entender e implementar do que algoritmos de</p><p>recorte mais simples.</p><p>● Custo Computacional: Pode ser computacionalmente mais caro, especialmente</p><p>para polígonos com muitas interseções.</p><p>O algoritmo de Weiler-Atherton é uma ferramenta poderosa para clipping de polígonos</p><p>complexos e é frequentemente utilizado em aplicações de computação gráfica que exigem</p><p>alta precisão e flexibilidade, como CAD, GIS e desenvolvimento de jogos.</p>