stringtranslate.com

esqueleto recto

El proceso de contracción, el esqueleto recto (azul) y el modelo del techo.

En geometría , un esqueleto recto es un método para representar un polígono mediante un esqueleto topológico . Es similar en algunos aspectos al eje medial, pero se diferencia en que el esqueleto está compuesto de segmentos de línea recta, mientras que el eje medial de un polígono puede implicar curvas parabólicas. Sin embargo, ambos son homotópicos equivalentes al polígono subyacente. [1]

Los esqueletos rectos fueron definidos por primera vez para polígonos simples por Aichholzer et al. (1995), [2] y generalizado a gráficos planos de línea recta (PSLG) por Aichholzer & Aurenhammer (1996). [3] En su interpretación como proyección de la superficie del tejado, ya fueron ampliamente discutidos por GA Peschka (1877). [4]

Definición

El esqueleto recto de un polígono se define mediante un proceso continuo de contracción en el que los bordes del polígono se mueven hacia dentro en paralelo a sí mismos a una velocidad constante. A medida que las aristas se mueven de esta manera, los vértices donde se encuentran los pares de aristas también se mueven, a velocidades que dependen del ángulo del vértice. Si uno de estos vértices en movimiento choca con un borde no adyacente, el polígono se divide en dos por la colisión y el proceso continúa en cada parte. El esqueleto recto es el conjunto de curvas que trazan los vértices en movimiento en este proceso. En la ilustración, la figura superior muestra el proceso de encogimiento y la figura del medio muestra el esqueleto recto en azul.

Algoritmos

El esqueleto recto puede calcularse simulando el proceso de contracción mediante el cual se define; Se han propuesto varias variantes de algoritmos para calcularlo, que difieren en las suposiciones que hacen sobre la entrada y en las estructuras de datos que utilizan para detectar cambios combinatorios en el polígono de entrada a medida que se reduce.

Los siguientes algoritmos consideran una entrada que forma un polígono, un polígono con agujeros o un PSLG. Para una entrada poligonal denotamos el número de vértices por n y el número de vértices reflejos (cóncavos, es decir, ángulo mayor que π ) por r . Si la entrada es un PSLG, entonces consideramos la estructura de frente de onda inicial, que forma un conjunto de polígonos, y nuevamente denotamos por n el número de vértices y por r el número de vértices reflejos con respecto a la dirección de propagación. La mayoría de los algoritmos enumerados aquí están diseñados y analizados en el modelo de cálculo RAM real .

Aplicaciones

Cada punto dentro del polígono de entrada se puede elevar al espacio tridimensional utilizando el tiempo en el que el proceso de reducción alcanza ese punto como la coordenada z del punto. La superficie tridimensional resultante tiene una altura constante en los bordes del polígono y se eleva con una pendiente constante desde ellos, excepto en los puntos del propio esqueleto recto, donde se encuentran parches de superficie en diferentes ángulos. De esta manera, el esqueleto recto se puede utilizar como el conjunto de líneas de cumbrera de la cubierta de un edificio, a partir de paredes en forma de polígono inicial. [2] [14] La figura inferior de la ilustración muestra una superficie formada de esta manera a partir del esqueleto recto.

Demaine, Demaine y Lubiw utilizaron el esqueleto recto como parte de una técnica para doblar una hoja de papel de modo que se pueda cortar un polígono determinado con un solo corte recto (el teorema de doblar y cortar ), y problemas de diseño de origami relacionados. . [15]

Barequet et al. Utilice esqueletos rectos en un algoritmo para encontrar una superficie tridimensional que interpola entre dos cadenas poligonales dadas . [dieciséis]

Tănase y Veltkamp proponen descomponer polígonos cóncavos en uniones de regiones convexas utilizando esqueletos rectos, como paso de preprocesamiento para la coincidencia de formas en el procesamiento de imágenes. [17]

Bagheri y Razzazi utilizan esqueletos rectos para guiar la ubicación de los vértices en un algoritmo de dibujo de gráficos en el que el dibujo del gráfico está obligado a quedar dentro de un límite poligonal. [18]

El esqueleto recto también se puede utilizar para construir una curva desplazada de un polígono, con esquinas en inglete , de manera análoga a la construcción de una curva desplazada con esquinas redondeadas formadas a partir del eje medial. Tomoeda y Sugihara aplican esta idea en el diseño de señalización, visible desde ángulos amplios, con una apariencia ilusoria de profundidad. [19] De manera similar, Asente y Carr usan esqueletos rectos para diseñar degradados de color que coinciden con los contornos de las letras u otras formas. [20]

Al igual que con otros tipos de esqueleto, como el eje medial , el esqueleto recto se puede utilizar para colapsar un área bidimensional en una representación unidimensional simplificada del área. Por ejemplo, Haunert y Sester describen una aplicación de este tipo para esqueletos rectos en sistemas de información geográfica , para encontrar las líneas centrales de las carreteras. [21] [22]

Todo árbol sin grado y dos vértices puede representarse como el esqueleto recto de un polígono convexo . [23] El casco convexo de la forma del techo correspondiente a este esqueleto recto forma una realización de Steinitz del gráfico de Halin formado a partir del árbol conectando sus hojas en un ciclo.

Dimensiones superiores

Barequet et al. definió una versión de esqueletos rectos para poliedros tridimensionales , describió algoritmos para calcularlo y analizó su complejidad en varios tipos diferentes de poliedros. [24]

Huber et al. espacios métricos investigados bajo los cuales coinciden los correspondientes diagramas de Voronoi y esqueletos rectos. Para dos dimensiones, la caracterización de dichos espacios métricos está completa. Para dimensiones superiores, este método puede interpretarse como una generalización de esqueletos rectos de ciertas formas de entrada a dimensiones arbitrarias mediante diagramas de Voronoi. [25]

Referencias

  1. ^ Huber, Stefan (2018), "La topología de esqueletos y compensaciones" (PDF) , Actas del 34º Taller europeo sobre geometría computacional (EuroCG'18).
  2. ^ abc Aichholzer, Oswin; Aurenhammer, Franz ; Alberts, David; Gärtner, Bernd (1995), "Un nuevo tipo de esqueleto para polígonos", Journal of Universal Computer Science , 1 (12): 752–761, doi :10.1007/978-3-642-80350-5_65, MR  1392429.
  3. ^ ab Aichholzer, Oswin; Aurenhammer, Franz (1996), "Esqueletos rectos para figuras poligonales generales en el plano", Proc. 2da Ana. En t. Conf. Computación y combinatoria (COCOON '96) , Apuntes de conferencias sobre informática, vol. 1090, Springer-Verlag, págs. 117-126
  4. ^ Peschka, Gustav A. (1877), Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge, Brünn: Buschak & Irrgang, doi :10.14463/GBV:865177619.
  5. ^ Huber, Stefan; Held, Martin (2010), "Cálculo de esqueletos rectos de gráficos planos de línea recta basados ​​en gráficos de motocicletas" (PDF) , Actas de la 22ª Conferencia Canadiense sobre Geometría Computacional.
  6. ^ Huber, Stefan; Held, Martin (2011), "Resultados teóricos y prácticos sobre esqueletos rectos de gráficos planos de líneas rectas" (PDF) , Actas del vigésimo séptimo simposio anual sobre geometría computacional (SCG'11), 13 al 15 de junio de 2011, París, Francia , págs. 171-178.
  7. ^ "CenterLineReplacer", FME Transformers , software seguro , consultado el 5 de agosto de 2013.
  8. ^ Felkel, Petr; Obdržálek, Štěpán (1998), "Implementación de esqueleto recto", SCCG 98: Actas de la 14ª Conferencia de primavera sobre gráficos por ordenador , págs..
  9. ^ Huber, Stefan (2012), Computación de esqueletos rectos y gráficos de motocicletas: teoría y práctica, Shaker Verlag, ISBN 978-3-8440-0938-5.
  10. ^ Yakersberg, Evgeny (2004), Transformación entre formas geométricas mediante interpolación basada en esqueleto recto. , Instituto de Tecnología de Israel.
  11. ^ Eppstein, David ; Erickson, Jeff (1999), "Levantando techos, rompiendo ciclos y jugando al billar: aplicaciones de una estructura de datos para encontrar interacciones por pares", Geometría discreta y computacional , 22 (4): 569–592, doi : 10.1007/PL00009479 , SEÑOR  1721026, S2CID  12460625.
  12. ^ Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016), "Un algoritmo más rápido para calcular esqueletos rectos", Transacciones ACM sobre algoritmos , 12 (3): 44:1–44:21, arXiv : 1405.4691 , doi : 10.1145/2898961.
  13. ^ Biedl, Teresa ; Celebrado, Martín; Huber, Stefan; Kaaser, Dominik; Palfrader, Peter (febrero de 2015). "Un algoritmo simple para calcular esqueletos rectos ponderados positivamente de polígonos monótonos" (PDF) . Cartas de procesamiento de información . 115 (2): 243–247. doi :10.1016/j.ipl.2014.09.021. PMC 4308025 . PMID  25648376. Como Biedl et al. Como señala, un algoritmo anterior para polígonos monótonos de Das et al. es incorrecto como se describe y, en el mejor de los casos, funciona solo para entradas en posición general que no tienen eventos vértice-vértice: Das, Gautam K.; Mukhopadhyay, Asish; Nandy, Subhas C.; Patil, Sangameswar; Rao, SV (2010), "Cálculo de los esqueletos rectos de un polígono monótono en tiempo O (n log n)" (PDF) , Actas de la 22ª Conferencia Canadiense sobre Geometría Computacional.
  14. ^ Bélanger, David (2000), Diseño de techos de edificios.
  15. ^ Demaine, Erik D .; Demaine, Martín L .; Lubiw, Anna (1998), "Folding and cuting paper", Artículos revisados ​​de la Conferencia Japonesa sobre Geometría Computacional y Discreta (JCDCG'98) , Lecture Notes in Computer Science, vol. 1763, Springer-Verlag, págs. 104-117, doi :10.1007/b75044, ISBN 978-3-540-67181-7, S2CID  32962663.
  16. ^ Bareket, Gill; Goodrich, Michael T .; Levi-Steiner, Aya; Steiner, Dvir (2003), "Interpolación de contorno basada en esqueleto recto", Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos , págs..
  17. ^ Tanase, Mirela; Veltkamp, ​​Remco C. (2003), "Descomposición de polígonos basada en el esqueleto de línea recta", Actas del 19º Simposio anual ACM sobre geometría computacional , págs. 58–67, doi :10.1145/777792.777802, ISBN 1-58113-663-3, S2CID  18173658.
  18. ^ Bagheri, Alireza; Razzazi, Mohammadreza (2004), "Dibujar árboles libres dentro de polígonos simples utilizando un esqueleto de polígono", Computación e Informática , 23 (3): 239–254, MR  2165282.
  19. ^ Tomoeda, Akiyasu; Sugihara, Kokichi (2012), "Creación computacional de un nuevo signo sólido ilusorio", Noveno Simposio internacional sobre diagramas de Voronoi en ciencia e ingeniería (ISVD 2012) , págs. 144-147, doi :10.1109/ISVD.2012.26, ISBN 978-1-4673-1910-2, S2CID  27610348.
  20. ^ Asente, Pablo; Carr, Nathan (2013), "Creación de gradientes de contorno utilizando biseles 3D", Actas del Simposio sobre estética computacional (CAE '13, Anaheim, California) , Nueva York, NY, EE. UU.: ACM, págs. 63–66, doi : 10.1145/2487276.2487283, ISBN 978-1-4503-2203-4, S2CID  17302186.
  21. ^ Haunert, Jan-Henrik; Sester, Monika (2008), "Colapso de área y líneas centrales de carreteras basadas en esqueletos rectos", GeoInformatica , 12 (2): 169–191, doi :10.1007/s10707-007-0028-x, S2CID  2169666.
  22. ^ Raleigh, David Baring (2008), Ajuste del estudio de esqueleto recto de las líneas centrales de las carreteras a partir de datos de adquisición aproximada de GPS: un estudio de caso en Bolivia, Universidad Estatal de Ohio, Ciencias Geodésicas y Topografía.
  23. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "¿Qué hace que un árbol sea un esqueleto recto?" (PDF) , Actas de la 24.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'12).
  24. ^ Bareket, Gill; Eppstein, David ; Goodrich, Michael T .; Vaxman, Amir (2008), "Esqueletos rectos de poliedros tridimensionales", Proc. XVI Simposio Europeo sobre Algoritmos , Apuntes de conferencias sobre informática, vol. 5193, Springer-Verlag, págs. 148-160, arXiv : 0805.0022 , doi : 10.1007/978-3-540-87744-8_13, ISBN 978-3-540-87743-1, S2CID  42150.
  25. ^ Huber, Stefan; Aichholzer, Oswin; Hackl, Thomas; Vogtenhuber, Birgit (2014), "Esqueletos rectos mediante diagramas de Voronoi bajo funciones de distancia poliédricas" (PDF) , Proc. 26a Conferencia Canadiense sobre Geometría Computacional (CCCG'14).

enlaces externos