La estructura de datos de cuatro bordes (Delaunay / Voronoi)

2 preguntas para los geómetras computacionales o algebraistas:

Estoy empezando a sumergirme en la geometría computacional y me encanta =)

Estoy intentando leer el famoso artículo de Guibas y Stolfi llamado "Primitivas para la manipulación de subdivisiones generales y el cálculo de Diagramas de Voronoi" para implementar un algoritmo de triangulación de Delaunay. Estoy tentado a omitir todas las cosas teóricas y solo leer la descripción de su estructura de datos de cuatro filos para ahorrar tiempo. Sin embargo, creo que valdría la pena entender todas las matemáticas del artículo si la estructura se usa ampliamente, o simplemente porque puede ser hermosa.

Las matemáticas son un poco demasiado densas para mí. No soy completamente ignorante sobre la topología, pero la descripción de su álgebra de borde requiere conocimiento de álgebra abstracta que no tengo.

Mis dos preguntas son: ¿Qué otras aplicaciones de la estructura quad-edge existen además de computar Delaunay / Voronoi? Parece una herramienta extremadamente poderosa.

La segunda pregunta; ¿Qué es un álgebra abstracta? Sería genial si pudiera darme una referencia a una introducción al álgebra abstracta, lo suficiente para que pueda entender la sección sobre el álgebra de borde.

¡Gracias!

reference-request cg.comp-geom algebra bigmonachus
fuente

Solo para llenar los vacíos: el álgebra abstracta es el estudio de conjuntos de elementos que respetan ciertas reglas. Como habrás adivinado, las reglas que satisfacen estos conjuntos son propiedades como el cierre, los elementos de identidad, la existencia de inversos únicos y, a medida que avanzamos, la conmutatividad, la asociatividad, etc. Es el estudio del álgebra en conjuntos que no necesariamente se comportan como los números reales. (Un buen ejemplo son las permutaciones).

Ross Snider

en.wikipedia.org/wiki/Abstract_algebra

Kaveh

Supongo que mi segunda pregunta fue un poco equivocada. Sé algo de teoría de grupos. Sé lo que son un anillo y un campo. Es solo que en el artículo definen un álgebra abstracta: "Un álgebra de borde es un álgebra abstracta (E, E *, Onext, Rot, Flip) que satisface las propiedades E1-E5 y F1-F5"

bigmonachus

[...] y no tengo idea de lo que eso significa. No es un álgebra sobre un campo , ¿verdad?

bigmonachus

Respuestas:

Creo que el formalismo de "álgebra de borde" de Guibas y Stolfi es un poco innecesario.

$f$ $f^*$ $e$ $e^*$ $v$ $v^*$

Gráficos primarios y duales

$\vec{e}$ $\text{tail}(\vec{e})$ $\text{head}(\vec{e})$ $\text{left}(\vec{e})$ $\text{right}(\vec{e})$ $\text{tail}(\vec{e})$ dirección . (Guibas y Stolfi usan "Org" y "Dest" en lugar de "cola" y "cabeza", pero prefiero las etiquetas más cortas, porque las abreviaturas innecesarias son malas). $\text{left}(\vec{e})$

$\vec{e}$

$\text{tailNext}(\vec{e})$ $\text{tail}(\vec{e})$ $\vec{e}$
$\text{flip}(\vec{e})$ $\vec{e}$ $\text{left}(\vec{e})$ $\text{right}(\vec{e})$
$\text{rotate}(\vec{e})$ $\vec{e}$

tailNext, rotar y voltear

Estas tres funciones satisfacen todo tipo de identidades maravillosas, como las siguientes:

$\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
$\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
$\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
$\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

$e~Flip$ e.Flip

Además, dadas estas tres funciones, uno puede definir varias otras funciones útiles como

$\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$
$\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$ $\vec{e}$ $\text{left}(\vec{e})$

Finalmente, conocer estas funciones le dice absolutamente todo acerca de la topología de la subdivisión, y cualquier subdivisión poligonal de cualquier superficie (orientable o no) puede codificarse utilizando estas tres funciones.

La estructura de datos de cuatro bordes es una representación particularmente conveniente de un gráfico de superficie que proporciona acceso a todas estas funciones, junto con varias otras operaciones de tiempo constante como insertar, eliminar, contraer, expandir y voltear bordes; división o fusión de vértices o caras; y agregando o eliminando asas o cruces.

¡Que te diviertas!

Jeffε
fuente

Usé OmniGraffle.

Jeffε