Polígono rectilíneo - Rectilinear polygon
Un polígono rectilíneo es un polígono cuyas intersecciones de aristas forman ángulos rectos . Por 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 es preferible otra definición: un polígono rectilíneo 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 aristas horizontales y aristas verticales de un polígono rectilíneo.
Los polígonos rectilíneos también se conocen como polígonos ortogonales . Otros términos en uso son orientadas iso- , alineado eje , y polígonos orientada eje . Estos adjetivos son menos confusos cuando los polígonos de este tipo son rectángulos , y se prefiere el término rectángulo alineado con el eje , aunque también se utilizan rectángulo ortogonal y rectilíneo .
La importancia de la clase de polígonos rectilíneos proviene de lo siguiente.
- Son convenientes para la representación de formas en diseños de máscaras de circuitos integrados debido a su simplicidad de diseño y fabricación. Muchos objetos manufacturados dan como resultado polígonos ortogonales.
- Los problemas de geometría computacional expresados en términos de polígonos a menudo permiten algoritmos más eficientes cuando se restringen a polígonos ortogonales. El teorema de la galería de arte para polígonos ortogonales proporciona un ejemplo , que conduce a una cobertura de protección más eficiente que la posible para polígonos arbitrarios.
Elementos
Un polígono rectilíneo tiene bordes 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 aristas.
Un polígono rectilíneo tiene dos tipos de esquinas: las esquinas en las que el ángulo menor (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 .
Una perilla es un borde cuyos dos extremos son esquinas convexas. Un anti-pomo es un borde cuyos dos extremos son esquinas cóncavas.
Polígono rectilíneo simple
Un polígono rectilíneo 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é, imagina que atraviesas el límite del polígono en el sentido de las agujas del reloj (con tu mano derecha dentro del polígono y tu mano izquierda afuera). En una esquina convexa, gira 90 ° a la derecha; en cualquier esquina cóncava, gira 90 ° a la izquierda. Finalmente debes 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 rectilíneo tiene al menos 4 esquinas convexas.
- El número de pomos (lados que conectan dos esquinas convexas) es cuatro más que el número de antipomo (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 tanto, XX = X-XY = X- (Y-YY) = YY + (XY) = YY + 4 .
- Corolario: cada polígono rectilíneo tiene al menos 4 botones.
Cuadrados y rectángulos en un polígono rectilíneo
Un polígono rectilíneo puede estar cubierto por un número finito de cuadrados o rectángulos con bordes paralelos a los bordes del polígono (ver Cobertura de polígono ). Es posible distinguir varios tipos de cuadrados / rectángulos contenidos en un determinado polígono rectilíneo P :
Un cuadrado máxima en un polígono P es un cuadrado en P que no está contenido en ningún otro cuadrado en P . Del mismo modo, un rectángulo maximal es un rectángulo no contenida en cualquier otro rectángulo en P .
Un cuadrado s es máxima en P si cada par de bordes adyacentes de s se cruza el límite de P . La prueba de ambos lados es por contradicción:
- Si un cierto par adyacente en s no interseca 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 s ; el interior de este cuadrado más grande contiene un par de bordes adyacentes de s , por lo tanto, este par no hace intersección con el límite de P .
La primera dirección también es cierto para los rectángulos, es decir: Si un rectángulo s es máxima, entonces cada par de bordes adyacentes de s se cruza el límite de P . La segunda dirección no es necesariamente cierta: un rectángulo puede cruzar el límite de P incluso en 3 lados adyacentes y aún no ser máximo, ya que se puede estirar en el cuarto lado.
Corolario: cada maximal cuadrado / rectángulo en P tiene al menos dos puntos, en dos bordes opuestos, que se cruzan el límite de P .
Una casilla de la esquina es un máximas cuadrados s en un polígono P de tal manera que al menos una esquina de s solapamientos una convexa esquina 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éndolo.
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 máximo que no contiene una perilla es un separador. Un cuadrado que contiene una perilla 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 sy 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 una perilla. Por tanto, el número de continuadores es siempre finito y está limitado por el número de mandos.
Existen varios tipos diferentes de continuadores, según el número de mandos que contienen y su estructura interna (ver figura). El balcón de un continuador se define como sus puntos que no están cubiertos por ningún otro cuadrado máximo (ver 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:
- En un polígono rectilíneo 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 rectilíneo 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
El polígono rectilíneo más simple es un rectángulo alineado con el eje : un rectángulo con 2 lados paralelos al eje xy 2 lados paralelos al eje y. Consulte también: Rectángulo delimitador mínimo .
Un golygon es un polígono rectilíneo cuyas longitudes de lado en secuencia son enteros consecutivos.
Un polígono rectilíneo que no es un rectángulo nunca es convexo , pero puede ser ortogonalmente convexo. Consulte 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 T-cuadrado es un fractal generado a partir de una secuencia de polígonos rectilíneos con propiedades interesantes.
Generalizaciones
- Poliedros ortogonales : la generalización natural de polígonos ortogonales a 3D.
- Rectilinealidad [1]
Problemas algorítmicos que involucran polígonos rectilíneos
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 ortogonal
- Construcción de casco convexo ortogonal
- Operaciones booleanas en polígonos para polígonos ortogonales (por ejemplo, intersección y unión )
- Planificación de movimiento / planificación de ruta / enrutamiento entre obstáculos rectilíneos
- Problemas de visibilidad ( problemas de iluminación )
- Rectángulo vacío máximo
Descomposición rectangular
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. Hay varios tipos de problemas de descomposición:
- Al cubrir problemas, 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. Consulte Revestimiento poligonal .
- En los problemas de empaque , el objetivo es encontrar un conjunto más grande de unidades no superpuestas 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 particiones , 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. Consulte Partición poligonal .
Referencias
- Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer . ISBN 0-387-96131-3. 1ª edición:; Segunda impresión, corregida y ampliada, 1988., capítulo 8: "La geometría de los rectángulos"
- ↑ a b c d Bar-Yehuda, R .; Ben-Hanoch, E. (1996). "Un algoritmo de tiempo lineal para cubrir polígonos simples con rectángulos similares". Revista Internacional de Geometría y Aplicaciones Computacionales . 06 : 79-102. doi : 10.1142 / S021819599600006X .
- ^ "Contando pares de bits" . Stack Exchange . 17 de noviembre de 2013.
- ^ Albertson, MO; O'Keefe, CJ (1981). "Cubriendo regiones con cuadrados". Revista SIAM de Métodos Algebraicos y Discretos . 2 (3): 240. doi : 10.1137 / 0602026 .