algoritmo para encontrar los bordes utilizando vértices (2D y 3D) en una malla

StackOverflow https://stackoverflow.com/questions/2294032

Pregunta

Tengo un una malla, con ciertos tipos de elementos (por ejemplo, triangular, TETRA). Para cada elemento I conocer todas sus vértices es decir, un elemento 2D triangular tendrán 3 v1 v2 v3 vértices, y cuyos x, y, z son conocidos coords.

Pregunta 1

Estoy buscando un algoritmo que devolverá todos los bordes ... en este caso:

borde (v1, v2), el borde (v1, v3), borde (v2, v3). Basado en el número de vértices de cada elemento tiene, el algoritmo debe determinar de manera eficiente los bordes.

Pregunta 2

Estoy usando C ++, por lo que, lo que va a ser la forma más eficiente para almacenar la información sobre los bordes devueltos por el algoritmo anterior? Ejemplo, todo lo que me interesa es una tupla (v1, v2) que desea utilizar para algún cálculo y luego olvidarse de él.

Gracias

¿Fue útil?

Solución

Puede utilizar la estructura de datos de media punta.


Básicamente su malla también tiene una lista de los bordes, y hay una estructura de borde por par de vértices en cada dirección. Eso significa que si tiene vértices A y B, entonces hay dos estructuras de borde almacenados en algún lugar, una para A-> B y uno para B-> A. Cada arista tiene 3 punteros, uno llamado anterior, uno llamado al lado y uno llamado gemelo. Siguiendo los punteros siguiente y anterior que camina alrededor de los bordes del triángulo o polígono en la malla. Llamando gemelo le lleva al borde adyacente en el polígono o triángulo adyacente. (Mira las flechas que int imagen) Esta es la estructura de datos del borde más útil y detallado que conozco. Lo he utilizado para suavizar las mallas mediante la creación de nuevas aristas y actualizar los punteros. Por cierto, cada borde también debe apuntar a un vértice por lo que sabe dónde está en el espacio.

Otros consejos

En realidad, hay tres partes a su pregunta, no dos:

  • ¿Qué estructuras de datos se debe utilizar para representar la malla?
  • ¿Qué algoritmo debería utilizar para extraer los bordes de las estructuras de datos de malla?
  • ¿Cómo debería estar representado el conjunto resultante de aristas?

Hay que hacer preguntas adicionales para encontrar respuestas adecuadas.

¿Qué estructuras de datos debe ser usado para representar la malla?

¿Qué tipos de elementos se necesitan para manejar?

Si sólo necesita para manejar polígonos (circuitos cerrados) y simplicials (cada nodo está conectado a todos los demás nodos en el elemento, tal como un tetraedro), a continuación, una lista de nodos ordenado es suficiente porque bordes pueden estar implícitas de la lista de nodos. Si, por el contrario, es necesario para manejar los tipos de elementos tales como hexaedros, prismas, o poliedros general, entonces usted necesita más información acerca de la topología elemento. Un simple conjunto de asignaciones de borde es a menudo suficiente. Es sólo una matriz [] [2] de los índices en la lista del elemento de nodos que le indica cómo conectar los puntos para un tipo de elemento dado.

La estructura de un medio de borde descrito por Chris es una buena opción para solamente 2D. En 3D no puede haber un número arbitrario de elementos fijados a cada borde, no sólo dos. Hay una extensión 3D para la representación de media punta que creo que se llama una estructura de molinete.

Si usted tiene que apoyar los tipos de elementos arbitrarios, prefiero una estructura de datos más completa para representar la topología elemento. Una opción común es utilizar bordes y compañeros de bordes. Hay una estructura de borde para cada par de nodos conectados, y un co-borde para cada uso de dicho borde en un elemento. Es similar al enfoque molinete, pero un poco más explícita.

¿Qué algoritmo debería utilizar para extraer los bordes de los elementos?

¿Qué tan importante es la velocidad o la memoria? Debe incluir el resultado de cada borde una vez por elemento, o sólo una vez, no importa cuántos elementos están utilizando? No importa el orden de los bordes en el resultado? ¿El orden de los nodos de cada materia borde?

Es muy difícil llegar a un algoritmo para los tipos de elementos arbitrarios que sólo visitar una vez cada borde. Para garantizar que cada borde sólo aparece una vez, puede filtrar el resultado, o bien puede ser un poco hacker y mantener un "visitado" bit en cada borde para asegurar que no se pegue en el resultado dos veces.

¿Cómo debería representar los resultados?

Lo que importa acerca de la manera voy a utilizar el resultado?

Si va a utilizar el resultado de un cálculo informático intensivo, una gran variedad de coordenadas puede ser la mejor opción. Usted no desea volver a buscar el nodo coordina una y otra vez durante su cálculo. Sin embargo, si usted está filtrando los resultados para eliminar bordes duplicados, comparando las coordenadas (6 dobles para un par de nodos) no es el camino a seguir. Si se está filtrando, generar una lista de punteros a estructuras Edge primero, y luego filtrar duplicados, y después generar su lista de coordenadas. Se podría utilizar este método con los pares de nodos también, pero luego se va a filtrar tanto contra posibles órdenes de nodos por filo, duplicando la cantidad de tiempo que se necesita para filtrar.

Una lista de punteros borde es también el camino a seguir si la memoria es más importante que el rendimiento. En lugar de convertir su lista de aristas a una lista de coordenadas, sin embargo, se mira coordenadas durante su cálculo. Obtener las coordenadas del nodo es más lento de esa manera, pero evitar hacer una lista masiva de coordenadas -. Almacenar un único puntero por el borde en lugar de 6 dobles por filo

Muchos tienda de aplicaciones de malla de todas las coordenadas en una gran matriz global, con cada nodo que tiene un índice en la matriz. Si este es el caso, en lugar de convertir su lista de borde a una matriz de coordenadas, convertirlo en una lista de índices en la matriz de coordenadas global. El rendimiento no debería ser mucho fuera de un local de coordenadasarray, pero sin la memoria y de la población por encima.

No tengo algoritmos para ti, pero te puedo decir dónde buscar.

"Set Point triangulación" es lo que busca.

Aquí están algunas librerías de código abierto, que lo hará por usted (asimilar el código de algoritmos):

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top