En geometría , un polígono sencillo / p ɒ l ɪ ɡ ɒ n / es un polígono que no lo hace de intersección en sí y no tiene agujeros. Es decir, es una forma plana que consta de segmentos de línea rectos que no se cruzan o "lados" que se unen por pares para formar un solo camino cerrado . Si los lados se cruzan, entonces el polígono no es simple. El calificativo "simple" se omite con frecuencia, entendiéndose entonces que la definición anterior define un polígono en general.
La definición dada anteriormente asegura las siguientes propiedades:
- Un polígono encierra una región (llamada su interior) que siempre tiene un área medible .
- Los segmentos de línea que forman un polígono (llamados lados o aristas) se encuentran solo en sus extremos, llamados vértices (singular: vértice) o menos formalmente "esquinas".
- Exactamente dos aristas se encuentran en cada vértice.
- El número de aristas siempre es igual al número de vértices.
Por lo general, se requieren dos bordes que se unen en una esquina para formar un ángulo que no sea recto (180 °); de lo contrario, los segmentos de línea colineales se considerarán partes de un solo lado.
Los matemáticos suelen utilizar "polígono" para referirse solo a la forma formada por los segmentos de línea, no a la región cerrada, sin embargo, algunos pueden utilizar "polígono" para referirse a una figura plana que está delimitada por un camino cerrado, compuesto por una secuencia finita. de segmentos de línea recta (es decir, por una cadena poligonal cerrada ). Según la definición en uso, este límite puede o no formar parte del propio polígono. [1]
Los polígonos simples también se denominan polígonos de Jordan , porque el teorema de la curva de Jordan se puede utilizar para demostrar que dicho polígono divide el plano en dos regiones, la región dentro de él y la región fuera de él. Un polígono en el plano es simple si y solo si es topológicamente equivalente a un círculo . Su interior es topológicamente equivalente a un disco .
Polígono débilmente simple
Si una colección de segmentos de línea que no se cruzan forma el límite de una región del plano que es topológicamente equivalente a un disco, entonces este límite se denomina polígono débilmente simple . [2] En la imagen de la izquierda, ABCDEFGHJKLM es un polígono débilmente simple de acuerdo con esta definición, con el color azul marcando la región para la cual es el límite. Este tipo de polígono débilmente simple puede surgir en gráficos por computadora y CAD como una representación por computadora de regiones poligonales con agujeros: para cada agujero se crea un "corte" para conectarlo a un límite externo. Refiriéndose a la imagen de arriba, ABCM es un límite externo de una región plana con un agujero FGHJ. El ED cortado conecta el agujero con el exterior y se atraviesa dos veces en la representación poligonal débilmente simple resultante.
En una definición alternativa y más general de polígonos débilmente simples, son los límites de secuencias de polígonos simples del mismo tipo combinatorio, con la convergencia bajo la distancia de Fréchet . [3] Esto formaliza la noción de que dicho polígono permite que los segmentos se toquen pero no se crucen. Sin embargo, este tipo de polígono débilmente simple no necesita formar el límite de una región, ya que su "interior" puede estar vacío. Por ejemplo, en referencia a la imagen de arriba, la cadena poligonal ABCBA es un polígono débilmente simple de acuerdo con esta definición: puede verse como el límite de "compresión" del polígono ABCFGHA.
Problemas computacionales
En geometría computacional , varias tareas computacionales importantes involucran entradas en forma de un polígono simple; en cada uno de estos problemas, la distinción entre el interior y el exterior es crucial en la definición del problema. [4]
- Point en polígono de pruebas consiste en determinar, para un polígono simple P y un punto de consulta q , si q interior mentiras para P . [5]
- Se conocen fórmulas simples para calcular el área de un polígono ; es decir, el área del interior del polígono. [6]
- La partición poligonal es un conjunto de unidades primitivas (por ejemplo, cuadrados), que no se superponen y cuya unión es igual al polígono. Un problema de partición poligonal es un problema de encontrar una partición que sea mínima en algún sentido, por ejemplo: una partición con un número mínimo de unidades o con unidades de longitud lateral total más pequeña. [7]
- Un caso especial de partición poligonal es la triangulación poligonal: dividir un polígono simple en triángulos. Aunque los polígonos convexos son fáciles de triangular, triangular un polígono simple general es más difícil porque tenemos que evitar agregar bordes que se crucen fuera del polígono. Sin embargo, Bernard Chazelle demostró en 1991 que cualquier polígono simple con n vértices se puede triangular en Θ ( n ) tiempo, lo cual es óptimo. El mismo algoritmo también se puede utilizar para determinar si una cadena poligonal cerrada forma un polígono simple.
- Otro caso especial es el problema de la galería de arte , que se puede reformular de manera equivalente como una partición en un número mínimo de polígonos en forma de estrella . [7]
- Operaciones booleanas en polígonos : Varias operaciones booleanas en los conjuntos de puntos definidos por regiones poligonales.
- El casco convexo de un polígono simple puede calcularse de manera más eficiente que el casco convexo de otros tipos de entradas, como el casco convexo de un conjunto de puntos.
- Diagrama de Voronoi de un polígono simple
- Medial eje / topológica esqueleto / esqueleto lineal de un polígono simple
- Desplazamiento de la curva de un polígono simple
- Suma de Minkowski para polígonos simples
Referencias
- ↑ Grünbaum, B .; Politopos convexos 2nd Ed, Springer, 2003
- ^ Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Redes ortogonales ligeras con dilatación geométrica constante". En Thomas, Wolfgang; Weil, Pascal (eds.). STACS 2007: 24º Simposio anual sobre aspectos teóricos de la informática, Aquisgrán, Alemania, 22-24 de febrero de 2007, Actas (edición ilustrada). Saltador. pag. 177. ISBN 978-3540709176.
- ^ Hsien-Chih Chang; Jeff Erickson; Chao Xu (2015). Actas del vigésimo sexto simposio anual ACM-SIAM sobre algoritmos discretos (SODA'15) . págs. 1655-1670.
- ^ Las preguntas frecuentes de comp.graphics.algorithms , que enumeran soluciones a problemas matemáticos con polígonos 2D y 3D.
- ^ Haines, Eric (1994). "Estrategias de punto en polígono" . En Heckbert, Paul S. (ed.). Gemas gráficas IV . San Diego, CA, EE.UU .: Academic Press Professional, Inc. págs. 24–46 . ISBN 0-12-336155-9.
- ^ Bart Braden (1986). "Fórmula del área del topógrafo" (PDF) . The College Mathematics Journal . 17 (4): 326–337. doi : 10.2307 / 2686282 . JSTOR 2686282 . Archivado desde el original (PDF) el 7 de noviembre de 2012.
- ^ a b Lee, DT (1998). "Capítulo 19: Geometría Computacional I". En Atallah, Mikhail J. (ed.). Manual de algoritmos y teoría de la computación . Serie de estructuras de datos y algoritmos aplicados de Chapman & Hall / CRC. Prensa CRC. ISBN 9781420049503.Consulte "Otras descomposiciones", pág. 19-25 .
enlaces externos
- Weisstein, Eric W. "Polígono simple" . MathWorld .