Polígono simples - Simple polygon
Na geometria , um simples polígono / p ɒ l do ɪ do ɡ ɒ n / é um polígono que não se intersectam -se e não tem orifícios. Ou seja, é uma forma plana que consiste em segmentos de linha retos, sem interseção , ou "lados" que são unidos aos pares para formar um único caminho fechado . Se os lados se cruzam, o polígono não é simples. O qualificador "simples" é freqüentemente omitido, com a definição acima sendo entendida como definindo um polígono em geral.
A definição dada acima garante as seguintes propriedades:
- Um polígono envolve uma região (chamada de seu interior) que sempre possui uma área mensurável .
- Os segmentos de linha que formam um polígono (chamados lados ou arestas) se encontram apenas em seus pontos finais, chamados vértices (singular: vértice) ou menos formalmente "cantos".
- Exatamente duas arestas se encontram em cada vértice.
- O número de arestas sempre é igual ao número de vértices.
Geralmente, duas arestas que se encontram em um canto são necessárias para formar um ângulo que não seja reto (180 °); caso contrário, os segmentos de linha colineares serão considerados partes de um único lado.
Os matemáticos normalmente usam "polígono" para se referir apenas à forma formada pelos segmentos de linha, não a região fechada, no entanto, alguns podem usar "polígono" para se referir a uma figura plana que é limitada por um caminho fechado, composto de uma sequência finita de segmentos de linha reta (ou seja, por uma cadeia poligonal fechada ). De acordo com a definição em uso, este limite pode ou não fazer parte do próprio polígono.
Polígonos simples também são chamados de polígonos de Jordan , porque o teorema da curva de Jordan pode ser usado para provar que tal polígono divide o plano em duas regiões, a região dentro dele e a região fora dele. Um polígono no plano é simples se e somente se for topologicamente equivalente a um círculo . Seu interior é topologicamente equivalente a um disco .
Polígono fracamente simples
Se uma coleção de segmentos de linha que não se cruzam forma o limite de uma região do plano que é topologicamente equivalente a um disco, então esse limite é chamado de polígono fracamente simples . Na imagem à esquerda, ABCDEFGHJKLM é um polígono fracamente simples de acordo com esta definição, com a cor azul marcando a região para a qual é o limite. Este tipo de polígono fracamente simples pode surgir em computação gráfica e CAD como uma representação de computador de regiões poligonais com orifícios: para cada orifício, um "corte" é criado para conectá-lo a um limite externo. Referindo-se à imagem acima, ABCM é um limite externo de uma região plana com um furo FGHJ. O corte ED conecta o furo com o exterior e é percorrido duas vezes na representação poligonal fracamente simples resultante.
Em uma definição alternativa e mais geral de polígonos fracamente simples, eles são os limites de sequências de polígonos simples do mesmo tipo combinatório, com a convergência sob a distância de Fréchet . Isso formaliza a noção de que tal polígono permite que os segmentos se toquem, mas não se cruzem. No entanto, esse tipo de polígono fracamente simples não precisa formar o limite de uma região, pois seu "interior" pode estar vazio. Por exemplo, referindo-se à imagem acima, a cadeia poligonal ABCBA é um polígono fracamente simples de acordo com esta definição: ela pode ser vista como o limite de "compressão" do polígono ABCFGHA.
Problemas computacionais
Na geometria computacional , várias tarefas computacionais importantes envolvem entradas na forma de um polígono simples; em cada um desses problemas, a distinção entre o interior e o exterior é crucial na definição do problema.
- Ponto no polígono de testes envolve determinar, por um polígono simples P e um ponto de consulta q , se q mentiras interior de P .
- Fórmulas simples são conhecidas para calcular a área do polígono ; ou seja, a área do interior do polígono.
-
A partição poligonal é um conjunto de unidades primitivas (por exemplo, quadrados), que não se sobrepõem e cuja união é igual ao polígono. Um problema de partição de polígono é um problema de encontrar uma partição que seja mínima em algum sentido, por exemplo: uma partição com o menor número de unidades ou com unidades de menor comprimento lateral total.
- Um caso especial de partição poligonal é a triangulação poligonal : dividir um polígono simples em triângulos. Embora os polígonos convexos sejam fáceis de triangular, a triangulação de um polígono simples geral é mais difícil porque temos que evitar adicionar arestas que se cruzam fora do polígono. No entanto, Bernard Chazelle mostrou em 1991 que qualquer polígono simples com n vértices pode ser triangulado em tempo Θ ( n ), o que é ótimo. O mesmo algoritmo também pode ser usado para determinar se uma cadeia poligonal fechada forma um polígono simples.
- Outro caso especial é o problema da galeria de arte , que pode ser reformulado de forma equivalente como uma partição em um número mínimo de polígonos em forma de estrela .
- Operações booleanas em polígonos : várias operações booleanas nos conjuntos de pontos definidos por regiões poligonais.
- O casco convexo de um polígono simples pode ser calculado de forma mais eficiente do que o casco convexo de outros tipos de entradas, como o casco convexo de um conjunto de pontos.
- Diagrama de Voronoi de um polígono simples
- Medial eixo / topológica esqueleto / esqueleto linear de um polígono simples
- Curva de deslocamento de um polígono simples
- Soma de Minkowski para polígonos simples