Un polígono rectilíneo es un polígono cuyos lados forman á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 es preferible otra definición: un polígono rectilíneo es un polígono cuyos lados son 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 que se utilizan son isoorientados , alineados con el eje y polígonos orientados al 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 rectángulo rectilíneo .
La importancia de la clase de polígonos rectilíneos proviene 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 denominan convexas y las esquinas en las que el ángulo mayor (270°) es interior se denominan 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 también es simple también se llama sin agujeros porque no tiene agujeros, sino solo un único 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 (véase 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 interseca el límite de P. La prueba de ambos lados 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 interseca el límite de P. La segunda dirección no es necesariamente cierta: un rectángulo puede intersecar el límite de P incluso en 3 lados adyacentes y aún así no ser máximo, ya que puede estirarse en el cuarto lado.
Corolario: todo cuadrado/rectángulo máximo en P tiene al menos dos puntos, en dos aristas opuestas, 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. Para cada esquina convexa, hay exactamente un cuadrado máximo (de esquina) que lo 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 cubran.
Un cuadrado separador en un polígono P es un cuadrado s en P tal que P − s no está 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 maximal es siempre un cuadrado de esquina. Además, un continuador maximal siempre contiene un nudo. Por lo tanto, el número de continuadores es siempre finito y está limitado por el número de nudos.
Existen varios tipos diferentes de continuadores, en función del número de protuberancias que contienen y de 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 continuo y separador. En los polígonos generales puede haber cuadrados que no sean ni continuos ni separadores, pero en los polígonos simples esto no puede ocurrir: [1]
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.
El polígono rectilíneo más simple es un rectángulo alineado con el eje : un rectángulo con dos lados paralelos al eje x y dos lados paralelos al eje y. Véase también: Rectángulo mínimo delimitador .
Un golígono es un polígono rectilíneo cuyos 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 cuadrado T 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 justifica una consideración aparte.
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: