Polígono rectilíneo

Un polígono rectilíneo es aquel cuyos lados se unen formando ángulos rectos . Por lo tanto, el ángulo interior en cada vértice es de 90° o 270°. Los polígonos rectilíneos son un caso especial de polígonos isotéticos .

En muchos casos, otra definición resulta preferible: un polígono rectilíneo es aquel cuyos lados son paralelos a los ejes de coordenadas cartesianas . La distinción cobra importancia al hablar de conjuntos de polígonos: la segunda definición implicaría que los lados de todos los polígonos del conjunto están alineados con los mismos ejes de coordenadas. Dentro del marco de la segunda definición, es natural hablar de aristas horizontales y verticales de un polígono rectilíneo.

Los polígonos rectilíneos también se conocen como polígonos ortogonales . Otros términos utilizados son polígonos isoorientados , alineados con los ejes y orientados a los ejes . Estos adjetivos resultan menos confusos cuando los polígonos de este tipo son rectángulos , y se prefiere el término rectángulo alineado con los ejes , aunque también se utilizan rectángulo ortogonal y rectángulo rectilíneo .

La importancia de la clase de polígonos rectilíneos radica en lo siguiente.

• Son convenientes para la representación de formas en diseños de máscaras de circuitos integrados debido a su simplicidad en el diseño y la fabricación. Muchos objetos fabricados resultan en polígonos ortogonales.
• Los problemas de geometría computacional expresados ​​en términos de polígonos suelen permitir algoritmos más eficientes cuando se restringen a polígonos ortogonales. Un ejemplo de ello es el teorema de la galería de arte para polígonos ortogonales, que proporciona una cobertura de guarda más eficiente que la que se puede lograr con polígonos arbitrarios.

Un polígono rectilíneo tiene lados de dos tipos: horizontales y verticales .

• Lema : El número de aristas horizontales es igual al número de aristas verticales (porque a cada arista horizontal le sigue una arista vertical y viceversa).
  • Corolario: Los polígonos ortogonales tienen un número par de aristas.

Un polígono rectilíneo tiene esquinas de dos tipos: las esquinas en las que el ángulo menor (90°) está dentro del polígono se llaman convexas y las esquinas en las que el ángulo mayor (270°) está dentro se llaman cóncavas . ^{[ 1 ]}

Un pomo es una arista cuyos dos extremos son esquinas convexas. Un antipomo es una arista cuyos dos extremos son esquinas cóncavas. ^{[ 1 ]}

Un polígono rectilíneo que además es simple también se denomina sin agujeros porque no tiene agujeros, solo un único límite continuo. Posee varias propiedades interesantes:

1. El número de vértices convexos es cuatro mayor que el de vértices cóncavos. Para entender por qué, imagina que recorres el perímetro del polígono en el sentido de las agujas del reloj (con la mano derecha dentro del polígono y la izquierda fuera). En un vértice convexo, giras 90° a la derecha; en cualquier vértice cóncavo, giras 90° a la izquierda. Finalmente, debes dar una vuelta completa de 360° y regresar al punto de partida; por lo tanto, el número de giros a la derecha debe ser cuatro mayor que el de giros a la izquierda.
   • Corolario: todo polígono rectilíneo tiene al menos 4 vértices convexos.
2. El número de perillas (lados que conectan dos esquinas convexas) es cuatro más que el número de antiperillas (lados que conectan dos esquinas cóncavas). Para ver por qué, sea X el número de esquinas convexas e Y el número de esquinas cóncavas. Por el hecho anterior, X = Y + 4. Sea XX el número de esquinas convexas seguidas de una esquina convexa, XY el número de esquinas convexas seguidas de una esquina cóncava, YX e YY definidos de forma análoga. Entonces, obviamente, X = XX + XY = XX + YX e Y = XY + YY = YX + YY . Por lo tanto, XX = X − XY = X − ( Y − YY ) = YY + ( X − Y ) = YY + 4. ^{[ 2 ]}
   • Corolario: todo polígono rectilíneo tiene al menos 4 nudos.

Un polígono rectilíneo puede ser cubierto por un número finito de cuadrados o rectángulos con lados paralelos a los lados del polígono (véase Recubrimiento de polígonos ). Es posible distinguir varios tipos de cuadrados/rectángulos contenidos en un determinado polígono rectilíneo P : ^{[ 1 ]}

Un cuadrado maximal en un polígono P es un cuadrado en P que no está contenido en ningún otro cuadrado en P. De manera similar, un rectángulo maximal es un rectángulo que no está contenido en ningún otro rectángulo en P.

Un cuadrado s es maximal en P si cada par de aristas adyacentes de s interseca el borde de P. La demostración de ambos lados es por contradicción:

• Si un par adyacente determinado en s no interseca el límite de P , entonces este par se empuja más hacia el límite, por lo que s no es máximo.
• Si s no es máximo en P , entonces hay un cuadrado más grande en P que contiene a s ; el interior de este cuadrado más grande contiene un par de aristas adyacentes de s , por lo tanto , este par no interseca el límite de P.

La primera afirmación también se aplica a los rectángulos: si un rectángulo s es máximo, entonces cada par de lados adyacentes de s interseca el límite de P. La segunda afirmación no es necesariamente cierta: un rectángulo puede intersecar el límite de P en hasta 3 lados adyacentes y aun así no ser máximo, ya que puede estirarse en el cuarto lado.

Corolario: todo cuadrado/rectángulo maximal en P tiene al menos dos puntos, en dos lados opuestos, que intersecan el límite de P.

Un cuadrado de esquina es un cuadrado maximal s en un polígono P tal que al menos una esquina de s se superpone a una esquina convexa de P. Para cada esquina convexa, existe exactamente un cuadrado maximal (de esquina) que la cubre, pero un mismo cuadrado maximal puede cubrir más de una esquina. Para cada esquina, puede haber muchos rectángulos maximales diferentes que la cubran.

Un cuadrado separador en un polígono P es un cuadrado s en P tal que P − s no está conectado.

• Lema : en un polígono rectilíneo simple, un cuadrado maximal que no contiene un nudo es un separador. ^{[ 3 ]} Un cuadrado que contiene un nudo puede ser o no un separador. El número de cuadrados separadores diferentes puede ser infinito e incluso incontable. Por ejemplo, en un rectángulo, todo cuadrado maximal que no toca uno de los lados más cortos es un separador.

Un cuadrado continuador es un cuadrado s en un polígono P tal que la intersección entre el borde de s y el borde de P es continua. Un continuador maximal es siempre un cuadrado de esquina. Además, un continuador maximal siempre contiene un nodo. Por lo tanto, el número de continuadores es siempre finito y está limitado por el número de nodos.

Existen varios tipos de continuadores, según el número de nodos que contienen y su estructura interna (véase la figura). El balcón de un continuador se define como aquellos puntos que no están cubiertos por ningún otro cuadrado máximo (véase la figura).

Ningún cuadrado puede ser a la vez continuador y separador. En los polígonos generales, puede haber cuadrados que no sean ni continuadores ni separadores, pero en los polígonos simples esto no puede ocurrir: ^{[ 1 ]}

1. En un polígono rectilíneo simple, cada cuadrado máximo es un separador o un continuador. Esto también se cumple para los rectángulos: cada rectángulo máximo es un separador o un continuador.
2. En un polígono rectilíneo simple que no es un cuadrado, hay al menos dos continuadores.

Existe una analogía interesante entre los cuadrados máximos de un polígono simple y los nodos de un árbol: un continuador es análogo a un nodo hoja y un separador es análogo a un nodo interno.

El polígono rectilíneo más simple es un rectángulo alineado con los ejes : un rectángulo con dos lados paralelos al eje x y dos lados paralelos al eje y. Véase también: Rectángulo delimitador mínimo .

Un golygon es un polígono rectilíneo cuyos lados tienen longitudes consecutivas de números enteros.

Un polígono rectilíneo que no es un rectángulo nunca es convexo , pero puede ser ortogonalmente convexo. Véase Polígono rectilíneo ortogonalmente convexo .

Un polígono rectilíneo monótono es un polígono monótono que también es rectilíneo.

Un cuadrado en T es un fractal generado a partir de una secuencia de polígonos rectilíneos con propiedades interesantes.

La mayoría de ellas también pueden aplicarse a polígonos generales, pero la expectativa de algoritmos más eficientes justifica una consideración aparte.

• búsqueda de rango ortogonal
• Construcción de la envoltura convexa ortogonal
• Operaciones booleanas sobre polígonos para polígonos ortogonales (por ejemplo, intersección y unión ).
• Planificación de movimiento / planificación de trayectorias / enrutamiento entre obstáculos rectilíneos
• Problemas de visibilidad ( Problemas de iluminación )
• Rectángulo vacío máximo

De particular interés para los polígonos rectilíneos son los problemas de descomposición de un polígono rectilíneo dado en unidades simples, generalmente rectángulos o cuadrados. Existen varios tipos de problemas de descomposición:

• En los problemas de recubrimiento , el objetivo es encontrar el conjunto más pequeño de unidades (cuadrados o rectángulos) cuya unión sea igual al polígono. Las unidades pueden superponerse. Véase Recubrimiento de polígonos .
• En los problemas de empaquetamiento , el objetivo es encontrar el conjunto más grande de unidades que no se superpongan, cuya unión esté contenida dentro del polígono. La unión puede ser más pequeña que el polígono.
• En los problemas de partición , el objetivo es encontrar el conjunto más pequeño de unidades que no se superpongan cuya unión sea exactamente igual al polígono. Véase Partición de polígonos .

• Poliedros ortogonales , una generalización natural de los polígonos ortogonales a 3D.

• Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer . ISBN 0-387-96131-3. 1.ª edición; 2.ª reimpresión, corregida y ampliada, 1988.Capítulo 8: "La geometría de los rectángulos"