Un polígono rectilíneo es un polígono cuyos lados forman ángulos rectos . Por tanto, el ángulo interior en cada vértice es 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 de 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 polígonos orientados iso , alineados con ejes y orientados con ejes . 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 rectángulo rectilíneo .
La importancia de la clase de polígonos rectilíneos se deriva de lo siguiente.
Un polígono rectilíneo tiene aristas de dos tipos: horizontales y verticales .
Un polígono rectilíneo tiene esquinas de dos tipos: las esquinas en las que el ángulo menor (90°) es interior al polígono se llaman convexas y las esquinas en las que el ángulo mayor (270°) es interior se llaman cóncavas . [1]
Una perilla 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 también es simple también se llama libre de agujeros porque no tiene agujeros, solo un límite continuo. Tiene varias propiedades interesantes:
Un polígono rectilíneo puede estar cubierto por un número finito de cuadrados o rectángulos con aristas paralelas a las aristas del polígono (ver Cobertura de polígonos ). Es posible distinguir varios tipos de cuadrados/rectángulos contenidos en un determinado polígono rectilíneo 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 aristas adyacentes de s cruza el límite de P. La prueba de ambas partes es por contradicción:
La primera dirección también es cierta para los rectángulos, es decir: si un rectángulo s es máximo, entonces cada par de aristas adyacentes de s 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 así no ser máximo, ya que se puede estirar en el cuarto lado.
Corolario: cada cuadrado/rectángulo máximo en P tiene al menos dos puntos, en dos aristas opuestas, que cruzan 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. Para cada esquina convexa, hay exactamente un cuadrado máximo (esquina) que la cubre, pero un solo cuadrado máximo puede cubrir más de una esquina. Para cada esquina, puede haber muchos rectángulos máximos diferentes que la cubren.
Un cuadrado separador en un polígono P es un cuadrado s en P tal que P − s no es conexo.
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 una perilla. Por tanto, el número de continuadores es siempre finito y está limitado por el número de perillas.
Existen varios tipos diferentes de continuadores, según la cantidad de perillas 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 a la vez continuador y 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]
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 el eje : un rectángulo con 2 lados paralelos al eje x y 2 lados paralelos al eje y. Ver también: Rectángulo delimitador mínimo .
Un golígono es un polígono rectilíneo cuyas longitudes de lados en secuencia son números enteros consecutivos.
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 T-cuadrado es un fractal generado a partir de una secuencia de polígonos rectilíneos con propiedades interesantes.
La mayoría de ellos también pueden enunciarse para polígonos generales, pero la expectativa de algoritmos más eficientes merece una consideración aparte.
De particular interés para los polígonos rectilíneos son los problemas de descomponer un polígono rectilíneo dado en unidades simples, generalmente rectángulos o cuadrados. Existen varios tipos de problemas de descomposición: