Polígono simple

Un polígono simple  es una figura que consta de segmentos que no se intersecan ("lados") conectados en pares para formar un camino cerrado. Si los lados se cortan, el polígono no es simple. A menudo, la palabra "simple" se omite en la definición anterior.

La definición anterior proporciona las siguientes propiedades de la forma:

• El polígono rodea una región (llamada interior) que siempre tiene un área medible.
• Los segmentos de línea que forman un polígono (llamados lados, más raramente bordes) se intersecan solo en sus extremos, que se llaman vértices (o, menos formalmente, "esquinas").
• Exactamente dos lados se encuentran en cada vértice.
• El número de lados siempre es igual al número de vértices.

Por lo general, se requiere que dos lados que se encuentran en un vértice no formen un ángulo recto (180°). De lo contrario, los lados que se encuentran en la misma línea recta se consideran parte del mismo lado.

Los matemáticos generalmente usan el término "polígono" solo para figuras formadas por segmentos de línea, sin incluir el interior. Sin embargo, algunos usan el término "polígono" para referirse a una figura plana delimitada por un camino cerrado que consta de una secuencia finita de segmentos (es decir, una polilínea cerrada ). Dependiendo de la definición utilizada, un borde puede o no ser parte de un polígono [1] .

Los polígonos simples también se denominan polígonos de Jordan , ya que el teorema de Jordan se puede usar para demostrar que dichos polígonos dividen el plano en dos regiones, interior y exterior. Un polígono en el plano es simple si y sólo si es topológicamente equivalente a un círculo . Su interior es topológicamente equivalente a un círculo .

Polígono débilmente simple

Si un conjunto de segmentos que no se intersecan forma el límite de un dominio en el plano, topológicamente equivalente a un círculo, entonces este límite se denomina polígono débilmente simple [2] . En la figura de la izquierda, ABCDEFGHJKLM es un polígono débilmente simple por definición. El azul representa la región cuyo límite es un polígono débilmente simple. Este tipo de polígonos débilmente simples puede ocurrir en gráficos de computadora y sistemas CAD como una representación de computadora de áreas poligonales con cavidades; para cada cavidad se crea un "corte" para conectar con el límite exterior. Según la figura, ABCM es el límite exterior de la región plana con la cavidad FGHJ. El corte ED conecta la cavidad con el contorno exterior y se recorre dos veces en una representación poligonal débilmente simple.

Una definición alternativa y más general de polígonos simples débiles es el límite de una secuencia de polígonos simples del mismo tipo combinatorio que convergen en la distancia de Fréchet [3] . Esto formaliza la idea de que los elementos de un polígono pueden tocarse, pero no cruzarse. Sin embargo, este tipo de polígono débilmente simple no forma necesariamente el límite de una región, ya que el "interior" puede estar vacío. Por ejemplo, en la figura de la cadena, ABCBA es un polígono débilmente simple; puede considerarse como el límite de "extracción" del polígono ABCFGHA.

Problemas de computación

En geometría computacional, algunos problemas computacionales importantes utilizan una entrada de polígono simple. En cada una de estas tareas, la distinción entre adentro y afuera es clave [4]

• El problema de si un punto pertenece a un polígono requiere determinar si el punto q está en el interior del polígono P.
• Se conocen fórmulas simples para calcular el área de un polígono , es decir, el área interior.
• Una partición de un polígono es un conjunto de unidades elementales (por ejemplo, cuadrados) que no se cortan y cuya unión forma un polígono. La tarea de dividir un polígono es 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 una longitud total mínima de los lados.
  • Un caso especial de división de un polígono es el problema de triangulación de polígonos, que es la partición de un polígono simple en triángulos. Aunque los polígonos convexos son fáciles de triangular, la triangulación de polígonos simples generales es más difícil porque debe evitar agregar bordes que se intersecan fuera del polígono. Sin embargo, Bernhard Chazelle en 1991 demostró que cualquier polígono simple con n vértices se puede triangular en un tiempo óptimo Θ ( n ). El mismo algoritmo se puede utilizar para determinar si una línea quebrada cerrada forma un polígono simple.
• Operaciones booleanas en polígonos : varias operaciones booleanas en el conjunto de puntos definidos por las áreas interiores de los polígonos.
• La envolvente convexa de un polígono simple se puede calcular de manera más eficiente que la envolvente convexa para otros tipos de entrada, como un conjunto de puntos.
• Diagrama de Voronoi de un polígono simple
• Eje mediano / esqueleto topológico / esqueleto rectilíneo de un polígono simple
• Curva paralela de un polígono simple
• Suma de Minkowski para polígonos simples

Véase también

• región estelar

Notas

1. ↑ Grünbaum, 2003 .
2. ↑ Dumitrescu, Toth, 2007 , pág. 177.
3. ↑ Chang, Erickson, Xu, 2015 , pág. 1655-1670
4. ↑ Comp.graphics.algorithms FAQ Archivado el 13 de febrero de 2011 en Wayback Machine con una lista de soluciones a problemas matemáticos con polígonos 2D y 3D.

Literatura

• Branko Grünbaum . Politopos convexos / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2do. - Nueva York, Londres: Springer-Verlag , 2003. - ISBN 0-387-00424-6 .
• Adrian Dumitrescu, Csaba D. Toth. STACS 2007: 24° Simposio Anual sobre Aspectos Teóricos de la Informática, Aquisgrán, Alemania, 22-24 de febrero de 2007, Actas / Wolfgang Thomas, Pascal Weil. — ilustrado. - Springer, 2007. - ISBN 3540709177 .
• Hsien-Chih Chang, Jeff Erickson, Chao Xu. Actas del vigésimo sexto simposio anual ACM-SIAM sobre algoritmos discretos (SODA'15). — 2015.

Enlaces

• Weisstein, Eric W. Polígono  simple en Wolfram MathWorld .