hay realmente tres partes a su pregunta, no dos:
- estructuras qué datos deben ser usado para representar la malla?
- ¿Qué algoritmo debo usar para extraer bordes de las estructuras de datos de malla?
- ¿Cómo se debe representar el conjunto resultante de bordes?
Tienes que hacer más preguntas para encontrar las respuestas adecuadas.
¿Qué estructuras de datos se deben usar para representar la malla?
¿Qué tipos de elementos necesita manejar?
Si solo necesita manejar polígonos (bucles cerrados) y simplicials (cada nodo está conectado a cada otro nodo en el elemento, como un tetraedro), entonces una lista de nodos ordenada es suficiente porque los bordes pueden ser implícitos desde el lista de nodos Si, por otro lado, necesita manejar tipos de elementos como hexahedra, prismas o poliedros generales, entonces necesita más información sobre la topología del elemento. Una simple matriz de mapeos de bordes a menudo es suficiente. Es solo una matriz [] [2] de índices en la lista de nodos del elemento que le indica cómo conectar los puntos para un tipo de elemento dado.
La estructura de medio borde descrita por Chris es una buena opción solo para 2D. En 3D, puede haber un número arbitrario de elementos unidos a cada borde, no solo a dos. Hay una extensión 3D para la representación de medio borde que creo que se llama estructura de molinete.
Si tiene que admitir tipos de elementos arbitrarios, prefiero una estructura de datos más completa para representar la topología de elementos. Una opción común es usar bordes y bordes. Hay una estructura de borde para cada par de nodos conectados, y un borde de borde para cada uso de ese borde en un elemento. Es similar al enfoque de molinete, pero un poco más explícito.
¿Qué algoritmo debo usar para extraer los bordes de los elementos?
¿Cuán importante es la velocidad o la memoria? ¿Debería el resultado incluir cada borde una vez por elemento, o solo una vez sin importar cuántos elementos lo estén usando? ¿Importa el orden de los bordes en el resultado? ¿Importa el orden de los nodos de cada borde?
Es bastante difícil encontrar un algoritmo para tipos de elementos arbitrarios que solo visiten cada borde una vez. Para asegurarse de que cada borde aparezca solo una vez, puede filtrar el resultado, o puede ser un poco hackish y mantener un bit "visitado" en cada borde para asegurarse de no pegarlo en el resultado dos veces.
¿Cómo debo representar los resultados?
¿Qué importancia tiene la forma en que usaré el resultado?
Si va a utilizar el resultado en un cálculo de cálculo intensivo, una gran variedad de coordenadas puede ser la mejor opción. No desea volver a buscar las coordenadas del nodo una y otra vez durante su cálculo. Sin embargo, si está filtrando los resultados para eliminar bordes duplicados, la comparación de coordenadas (6 dobles para un par de nodos) no es el camino a seguir. Si está filtrando, genere una lista de punteros a las estructuras de borde primero, luego filtre los duplicados, y luego genere su lista de coordenadas. También puede usar este enfoque con pares de nodos, pero luego debe filtrar contra ambos posibles pedidos de nodos por borde, duplicando la cantidad de tiempo que lleva filtrar.
Una lista de punteros de borde es también el camino a seguir si la memoria es más importante que el rendimiento. Sin embargo, en lugar de convertir su lista de bordes en una lista de coordenadas, busca coordenadas durante su cálculo. Obtener coordenadas de nodo es más lento de esa manera, pero se evita hacer una lista masiva de coordenadas: se almacena un solo puntero por borde en lugar de 6 dobles por borde.
Muchas aplicaciones de malla almacenan todas las coordenadas en una gran matriz global, con cada nodo teniendo un índice en la matriz. Si este es el caso, en lugar de convertir su lista de bordes a una matriz de coordenadas, conviértala a una lista de índices en la matriz de coordenadas global. El rendimiento no debería estar muy lejos de una matriz de coordenadas local, pero sin la memoria y la sobrecarga de la población.
