Polígono rectilineal
Un polígono rectilineal es un polígono en el que todas las intersecciones entre sus aristas consecutivas forman ángulos rectos. Por lo tanto, el ángulo interior en cada vértice es de 90° o de 270°. Los polígonos rectilineales son un caso especial de polígono isotético.
En muchos casos, es preferible otra definición: un polígono rectilineal es un polígono con lados paralelos a los ejes de coordenadas cartesianas. La distinción se vuelve crucial cuando se habla de conjuntos de polígonos: la última definición implicaría que los lados de todos los polígonos del conjunto están alineados con los mismos ejes de coordenadas. En el marco de la segunda definición, es natural hablar de lados horizontales y de lados verticales de un polígono rectilineal.
Los polígonos rectilineales también se conocen como polígonos ortogonales. Otros términos en uso son iso-orientados, eje-alineados y polígonos orientados respecto a ejes. Estos adjetivos son menos confusos cuando los polígonos de este tipo son rectángulos, y se prefiere el término de rectángulo alineado con los ejes, aunque rectángulo ortogonal y rectángulo rectilineal también son términos utilizados.
La importancia de la clase de los polígonos rectilineales proviene de las siguientes propiedades:
- Son convenientes para la representación de formas en los patrones para la producción de circuitos integrados, debido a su simplicidad de diseño y fabricación. Muchos objetos manufacturados dan como resultado polígonos ortogonales.
- Los problemas en geometría computacional expresados en términos de polígonos a menudo permiten obtener algoritmos más eficientes cuando se restringen a polígonos ortogonales. El problema de la galería de arte proporciona un ejemplo para el uso de polígonos ortogonales, lo que conduce a una cobertura de protección más eficiente que la posible con polígonos arbitrarios.
Elementos editar
Un polígono rectilineal tiene lados de dos tipos: horizontal y vertical.
- Lema: El número de bordes horizontales es igual al número de bordes verticales (porque cada borde horizontal va seguido de un borde vertical y viceversa).
- Corolario: los polígonos ortogonales tienen un número par de bordes.
Un polígono rectilineal tiene esquinas de dos tipos: las esquinas en las que el ángulo más pequeño (90°) es interior al polígono se denominan convexas y las esquinas en las que el ángulo mayor (270°) es interior se denominan cóncavas.[1]
Un "saliente" es un lado borde cuyos dos extremos son esquinas convexas. Un "entrante" es un borde cuyos dos extremos son esquinas cóncavas.[1]
Polígono rectilineal simple editar
Un polígono rectilineal que también es simple también se llama 'sin agujeros' porque no tiene agujeros, solo un único límite continuo. Tiene varias propiedades interesantes:
- El número de esquinas convexas es cuatro más que el número de esquinas cóncavas. Para ver por qué, imagínese que se recorre el límite del polígono en el sentido de las agujas del reloj (con la mano derecha dentro del polígono y la mano izquierda fuera). En una esquina convexa, se giran 90° a la derecha; en cualquier esquina cóncava, se giran 90° a la izquierda. Finalmente, se debe dar un giro completo de 360° y volver al punto original; por lo tanto, el número de giros a la derecha debe ser 4 más que el número de giros a la izquierda.
- * Corolario: cada polígono rectilineal tiene al menos 4 esquinas convexas.
- El número de salientes (lados que conectan dos esquinas convexas) es cuatro más que el número de entrantes (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[2] 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.
- * Corolario: cada polígono rectilineal tiene al menos 4 lados salientes.
Cuadrados y rectángulos en un polígono rectilineal editar
Un polígono rectilineal puede estar cubierto por un número finito de cuadrados o rectángulos con bordes paralelos a los bordes del polígono (véase recubrimiento con polígonos). Es posible distinguir varios tipos de cuadrados/rectángulos contenidos en un determinado polígono rectilineal P:[1]
Un cuadrado máximo 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 máximo es un rectángulo que no está contenido en ningún otro rectángulo en P.
Un cuadrado s es máximo en P si cada par de bordes adyacentes de s interseca el límite de P. Se demuestra por reducción al absurdo:
- Si un cierto par adyacente en s no cruza el límite de P, entonces este par se empujará 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 bordes adyacentes de s, y por lo tanto, este par no cruza el límite de P.
La primera sentencia también es cierta para los rectángulos, es decir: si un rectángulo s es máximo, entonces cada par de lados adyacentes de s se cruza con el límite de P. La segunda sentencia no es necesariamente cierta: un rectángulo puede intersecar el límite de P incluso en 3 lados adyacentes y aún no ser máximo, ya que puede estirarse según su cuarto lado.
Corolario: cada cuadrado/rectángulo máximo en P tiene al menos dos puntos, en dos bordes opuestos, que intersecan el límite de P.
Un cuadrado de esquina es un cuadrado máximo s en un polígono P tal que al menos una esquina de s se superpone a una esquina convexa de P. Por cada esquina convexa, hay exactamente un cuadrado máximo (esquina) cubriéndola, pero un solo cuadrado máximo puede cubrir más de una esquina. Para cada esquina, puede haber muchos rectángulos máximos diferentes cubriéndola.
Un cuadrado separador en un polígono P es un cuadrado s en P de manera que P-s no está conectado.
- Lema: en un polígono rectilineal simple, un cuadrado máximo que no contiene un lado saliente es un separador.[3] Un cuadrado que contiene un lado saliente puede o no ser un separador. El número de cuadrados separadores diferentes puede ser infinito e incluso incontable. Por ejemplo, en un rectángulo, cada cuadrado máximo que no toque 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 límite de s y el límite de P es continua. Un continuador máximo es siempre un cuadrado de esquina. Además, un continuador máximo siempre contiene un lado saliente. Por tanto, el número de continuadores es siempre finito y está limitado por el número de lados salientes.
Hay varios tipos diferentes de continuadores, según el número de lados salientes que contienen y su estructura interna (véase la figura). El "balcón" de un continuador se define como sus puntos que no están cubiertos por ningún otro cuadrado máximo (véase la figura).
Ningún cuadrado puede ser tanto un continuador como un separador. En los polígonos generales, puede haber cuadrados que no sean ni continuadores ni separadores, pero en polígonos simples esto no puede suceder:[1]
- En un polígono rectilineal simple, cada cuadrado máximo es un separador o un continuador. Esto también es cierto para los rectángulos: cada rectángulo máximo es un separador o un continuador.
- En un polígono rectilineal simple que no es un cuadrado, hay al menos dos continuadores.
Existe una analogía interesante entre los cuadrados máximos en un polígono simple y los nodos en un árbol: un continuador es análogo a un nodo hoja y un separador es análogo a un nodo interno.
Casos especiales editar
El polígono rectilineal más simple es un rectángulo alineado con el eje: un rectángulo con 2 lados paralelos al eje x y 2 lados paralelos al eje y. Consúltese también: Mínimo rectángulo envolvente.
Un golígono es un polígono rectilineal cuyas longitudes de lado en secuencia son enteros consecutivos.
Un polígono rectilineal que no es un rectángulo nunca es convexo, pero puede ser ortogonalmente convexo. Véase Polígono rectilineal envolvente convexa ortogonal .
Un polígono rectilineal monótono es un polígono monótono que también es rectilineal.
Un T-cuadrado es un fractal generado a partir de una secuencia de polígonos rectilineales con propiedades interesantes.
Generalizaciones editar
- Orthogonal polyhedra: la generalización natural de polígonos ortogonales a 3D.
- Rectilinealidad [1]
Problemas algorítmicos que involucran polígonos rectilineales editar
La mayoría de ellos también se pueden establecer para polígonos generales, pero la expectativa de algoritmos más eficientes merece una consideración separada
- Búsqueda de rango
- Construcción de envolvente 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 recorridos/encaminamiento entre obstáculos rectilineales
- Visibilidades (problema de la iluminación)
- Máximo rectángulo vacío
Descomposición rectangular editar
De particular interés para los polígonos rectilineales son los problemas de descomposición de un polígono rectilineal dado en unidades simples, generalmente rectángulos o cuadrados. Hay varios tipos de problemas de descomposición:
- En los problemas de cobertura, el objetivo es encontrar un 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 con polígonos.
- En los problemas de empaquetado, el objetivo es encontrar un conjunto más grande de unidades que no se superpongan cuya unión esté contenida en el 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 un conjunto más pequeño de unidades que no se superpongan, cuya unión sea exactamente igual al polígono. Véase partición con polígonos.
Referencias editar
- Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3., capítulo 8: "La geometría de los rectángulos"
- ↑ a b c d Bar-Yehuda, R.; Ben-Hanoch, E. (1996). «A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles». International Journal of Computational Geometry & Applications 06: 79. doi:10.1142/S021819599600006X.
- ↑ «Counting pairs of bits». Stack Exchange. 17 de noviembre de 2013.
- ↑ Albertson, M. O.; o’Keefe, C. J. (1981). «Covering Regions with Squares». SIAM Journal on Algebraic and Discrete Methods 2 (3): 240. doi:10.1137/0602026.
Datos: Q7303186
