Polígono retilíneo - Rectilinear polygon

Este artigo é sobre polígonos em ângulo reto. Para a definição dada nos Elementos de Euclides, veja Polígono .
Alguns exemplos de polígonos retilíneos

Um polígono retilíneo é um polígono cujas interseções de arestas estão em ângulos retos . Assim, o ângulo interno em cada vértice é de 90 ° ou 270 °. Os polígonos retilíneos são um caso especial de polígonos isotéticos .

Em muitos casos, outra definição é preferível: um polígono retilíneo é um polígono com lados paralelos aos eixos das coordenadas cartesianas . A distinção torna-se crucial quando falada sobre conjuntos de polígonos: a última definição implicaria que os lados de todos os polígonos no conjunto estão alinhados com os mesmos eixos coordenados. No âmbito da segunda definição, é natural falar de arestas horizontais e arestas verticais de um polígono retilíneo.

Os polígonos retilíneos também são conhecidos como polígonos ortogonais . Outros termos em uso são orientados-iso , eixo alinhado , e polígonos orientada-eixo . Esses adjetivos são menos confusos quando os polígonos desse tipo são retângulos , e o termo retângulo alinhado ao eixo é preferido, embora retângulo ortogonal e retângulo retilíneo também estejam em uso.

A importância da classe dos polígonos retilíneos vem do seguinte.

  • Eles são convenientes para a representação de formas em layouts de máscara de circuito integrado devido à sua simplicidade de design e fabricação. Muitos objetos manufaturados resultam em polígonos ortogonais.
  • Problemas em geometria computacional declarados em termos de polígonos geralmente permitem algoritmos mais eficientes quando restritos a polígonos ortogonais. Um exemplo é fornecido pelo teorema da galeria de arte para polígonos ortogonais, que leva a uma cobertura de guarda mais eficiente do que é possível para polígonos arbitrários.

Elementos

Um polígono retilíneo possui arestas de dois tipos: horizontal e vertical .

  • Lema : O número de arestas horizontais é igual ao número de arestas verticais (porque cada aresta horizontal é seguida por uma aresta vertical e vice-versa).
    • Corolário: polígonos ortogonais têm um número par de arestas.
X marca cantos convexos; O marca cantos côncavos. As linhas azuis são botões; linhas vermelhas são anti-knobs; as linhas amarelas não são nenhum dos dois.

Um polígono retilíneo possui cantos de dois tipos: os cantos em que o ângulo menor (90 °) é interno ao polígono são chamados de convexos e os cantos em que o ângulo maior (270 °) é interno são chamados de côncavos .

Um botão é uma aresta cujos dois pontos finais são cantos convexos. Um antiknob é uma aresta cujos dois pontos finais são cantos côncavos.

Polígono retilíneo simples

Um polígono retilíneo que também é simples também é denominado sem orifícios porque não possui orifícios - apenas um único limite contínuo. Possui várias propriedades interessantes:

  1. O número de cantos convexos é quatro a mais do que o número de cantos côncavos. Para ver por quê, imagine que você atravessa os limites do polígono no sentido horário (com a mão direita dentro do polígono e a esquerda fora). Em um canto convexo, você vira 90 ° à direita; em qualquer canto côncavo, você vira 90 ° à esquerda. Finalmente, você deve fazer uma volta completa de 360 ​​° e voltar ao ponto original; portanto, o número de voltas à direita deve ser 4 a mais do que o número de voltas à esquerda.
    • Corolário: todo polígono retilíneo tem pelo menos 4 cantos convexos.
  2. O número de botões (lados conectando dois cantos convexos) é quatro a mais que o número de anteparos (lados conectando dois cantos côncavos). Para ver por que, seja X o número de cantos convexos e Y o número de cantos côncavos. Pelo fato anterior, X = Y + 4 . Seja XX o número de cantos convexos seguidos por um canto convexo, XY o número de cantos convexos seguidos por um canto côncavo, YX e YY definidos analogamente. Então, obviamente, X = XX + XY = XX + YX e Y = XY + YY = YX + YY . Portanto, XX = X-XY = X- (Y-YY) = YY + (XY) = YY + 4 .
    • Corolário: todo polígono retilíneo tem pelo menos 4 botões.

Quadrados e retângulos em um polígono retilíneo

Um polígono retilíneo pode ser coberto por um número finito de quadrados ou retângulos com arestas paralelas às arestas do polígono (consulte Cobertura do polígono ). É possível distinguir vários tipos de quadrados / retângulos contidos em um determinado polígono retilíneo P :

Um quadrado máxima num polígono P é um quadrado em P que não está contido em qualquer outro quadrado em P . Da mesma forma, um rectângulo máxima é um rectângulo que não estejam contidos em qualquer outro rectângulo P .

Um quadrado s é máxima em P se cada par de bordas adjacentes de s cruza a fronteira de P . A prova de ambos os lados é por contradição:

  • Se um certo par adjacente em s não intercepta o limite de P , então este par é empurrado ainda mais em direção ao limite, então s não é máximo.
  • Se s não é máximo em P , então existe um quadrado maior em P contendo s ; o interior deste quadrado maior contém um par de orlas adjacentes do s , por conseguinte, este par não cruza a fronteira de P .

A primeira direcção é também verdadeiro para os rectângulos, ou seja: se um rectângulo s é máxima, então cada par de bordas adjacentes de s cruza a fronteira de P . A segunda direção não é necessariamente verdadeira: um retângulo pode cruzar o limite de P em até 3 lados adjacentes e ainda não ser máximo, pois pode ser esticado no 4º lado.

Corolário: cada quadrado / retângulo máxima em P tem pelo menos dois pontos, em dois lados opostos, que se cruzam a fronteira do P .

Um quadrado de canto é um máximas quadrados s em um polígono P de modo a que, pelo menos, um canto de s sobreposições um canto convexo de P . Para cada canto convexo, há exatamente um quadrado máximo (canto) cobrindo-o, mas um único quadrado máximo pode cobrir mais de um canto. Para cada canto, pode haver muitos retângulos máximos diferentes cobrindo-o.

continuador e separador
tipos de continuador

Um quadrado separador em um polígono P é um quadrado s em P tal que P - s não está conectado.

  • Lema : em um polígono retilíneo simples, um quadrado máximo que não contém um botão é um separador. Um quadrado contendo um botão pode ou não ser um separador. O número de quadrados separadores diferentes pode ser infinito e até incontável. Por exemplo, em um retângulo, cada quadrado máximo que não toca um dos lados mais curtos é um separador.

Um quadrado continuador é um quadrado s em um polígono P tal que a interseção entre o limite de s e o limite de P é contínua. Um continuador máximo é sempre um quadrado de canto. Além disso, um continuador máximo sempre contém um botão. Portanto, o número de continuadores é sempre finito e limitado pelo número de botões.

Existem vários tipos diferentes de continuadores, com base no número de botões que contêm e em sua estrutura interna (consulte a figura). A varanda de um continuador é definida como seus pontos que não são cobertos por nenhum outro quadrado máximo (ver figura).

Nenhum quadrado pode ser um continuador e um separador. Em polígonos gerais, pode haver quadrados que não são nem continuadores nem separadores, mas em polígonos simples isso não pode acontecer:

  1. Em um polígono retilíneo simples, cada quadrado máximo é um separador ou um continuador. Isso também é verdadeiro para retângulos: todo retângulo máximo é um separador ou um continuador.
  2. Em um polígono retilíneo simples que não é um quadrado, existem pelo menos dois continuadores.

Há uma analogia interessante entre quadrados máximos em um polígono simples e nós em uma árvore: um continuador é análogo a um nó folha e um separador é análogo a um nó interno.

Casos especiais

O polígono retilíneo mais simples é um retângulo alinhado ao eixo - um retângulo com 2 lados paralelos ao eixo xe 2 lados paralelos ao eixo y. Consulte também: Retângulo de limite mínimo .

Um golygon é um polígono retilíneo cujos comprimentos laterais em sequência são inteiros consecutivos.

Um polígono retilíneo que não é um retângulo nunca é convexo , mas pode ser ortogonalmente convexo. Consulte Polígono retilíneo convexo ortogonalmente .

Um polígono retilíneo monótono é um polígono retilíneo monótono que também é retilíneo.

Um T-quadrado é um fractal gerado a partir de uma sequência de polígonos retilíneos com propriedades interessantes.

Generalizações

Problemas de algoritmo envolvendo polígonos retilíneos

A maioria deles pode ser declarada para polígonos gerais também, mas a expectativa de algoritmos mais eficientes garante uma consideração separada

Decomposição retangular

De particular interesse para polígonos retilíneos são os problemas de decomposição de um determinado polígono retilíneo em unidades simples - geralmente retângulos ou quadrados. Existem vários tipos de problemas de decomposição:

  • Ao abordar problemas, o objetivo é encontrar um menor conjunto de unidades (quadrados ou retângulos) cuja união seja igual ao polígono. As unidades podem se sobrepor. Veja a cobertura do polígono .
  • Em problemas de embalagem , o objetivo é encontrar um maior conjunto de unidades não sobrepostas cuja união esteja contida no polígono. A união pode ser menor que o polígono.
  • Em problemas de particionamento , o objetivo é encontrar um menor conjunto de unidades não sobrepostas cuja união seja exatamente igual ao polígono. Veja partição do polígono .

Referências

  • Franco P. Preparata e Michael Ian Shamos (1985). Geometria Computacional - Uma Introdução . Springer . ISBN 0-387-96131-3. 1ª edição:; 2ª impressão, corrigida e ampliada, 1988., capítulo 8: "A geometria dos retângulos"
  1. ^ a b c d Barra-Yehuda, R .; Ben-Hanoch, E. (1996). "Um algoritmo de tempo linear para cobrir polígonos simples com retângulos semelhantes". International Journal of Computational Geometry & Applications . 06 : 79–102. doi : 10.1142 / S021819599600006X .
  2. ^ "Contando pares de bits" . Stack Exchange . 17 de novembro de 2013.
  3. ^ Albertson, MO; o'Keefe, CJ (1981). "Cobrindo regiões com quadrados". SIAM Journal on Algebraic and Discrete Methods . 2 (3): 240. doi : 10.1137 / 0602026 .