una tiene que lineas ingenieria geografia geodesico geodesicas geodesica energia ejemplos definicion coordenadas arquitectura aplicaciones algorithm math graphics computational-geometry graph-algorithm

algorithm - tiene - Trayectorias más cortas y geodésicas



lineas geodesicas definicion (4)

"a) todavía sufre el problema del ángulo obtuso"

Sí, la FMM original sufre el problema del ángulo obtuso, pero los investigadores han resuelto este problema. Este enlace es la implementación de Gabriel Peyre del método de marcha rápida en matlab. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

"b) cuando se usa en un escenario de múltiples puntos de semilla, se debe implementar un solo FMM para cada semilla para poder encontrar la distancia mínima para cada vértice de malla de cada semilla (es decir, en un escenario de 10 puntos de semilla, el FMM Debe ejecutarse 10 veces por cada vértice de malla) "

Si se refiere al problema de la ruta más corta de múltiples fuentes, el método de marcha rápida no necesita ejecutarse varias veces. Por ejemplo, para las semillas s1 y s2, y el destino v, y la distancia más corta entre s1 y v es d (s1, v), la distancia entre s2 y v es d (s2, v). Para encontrar la distancia más corta entre v y s1, s2, min (d (s1, v), d (s2, v)), ejecutar una vez el método de marcha rápida es suficiente. Pero si quiere saber tanto d (s1, v) como d (s2, v), necesita ejecutar FMM varias veces.

"En el otro lado, Mitchell y otros (MI) presentaron un algoritmo exacto -MMP- que lleva a un error de 0 en 87, y AFAIK nunca ha sido realmente implícito (probablemente debido a la potencia de cálculo requerida). En el mismo enfoque exacto, Surazhsky & al. (SU) proporcionó un algoritmo exacto alternativo basado en MMP que debería superar a este último en términos de velocidad, lo que todavía conduce a un resultado correcto. Desafortunadamente, la potencia de cálculo requerida para el cálculo, incluso si es mucho menor que El MMP original todavía es lo suficientemente alto como para que la implementación interactiva en tiempo real no sea factible en este momento. (SU) también propuso una aproximación de su algoritmo exacto, lo que llamaron plano exacto. Debería tomar el mismo tiempo computacional de FMM, mientras que trayendo solo 1/5 del error, pero: "

comentarios: MMP tiene una implementación en 2005, la implementación se publica en [1]. El enlace al código se encuentra en https://code.google.com/p/geodesic/

"c) no me queda claro si se puede usar en un escenario de múltiples semillas".

Se puede utilizar en el escenario de múltiples semillas y el código anterior lo implementó.

"Chen & Han (CH) y Kapoor (KP) han propuesto otros algoritmos de ruta más cortos, pero mientras el primero es absolutamente lento, el segundo es demasiado complicado para implementarlo en la práctica".

Comentarios: el primero es lento, pero en [2] el autor mejoró el algoritmo CH y dio una implementación práctica que es exacta y más rápida que MMP. El código está en sites.google.com/site/xinshiqing/knowledge-share

[1] Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven Gortler, Hugues Hoppe. Rápido geodésico exacto y aproximado sobre mallas. ACM Trans. Gráficos (SIGGRAPH), 24 (3), 2005.

[2] Mejora del algoritmo de Chen y Han sobre el problema geodésico discreto. Shiqing Xin y Guo-Jin Wang. ACM Transactions on Graphics (TOG): 28 (4), pp. 1–8, agosto de 2009.

dada una malla hecha completamente de quads, donde cada vértice tiene valencia n (con n> = 3), y no se encuentra en el mismo plano, necesito encontrar la distancia de cada vértice en la malla desde un conjunto cerrado de vértices semilla . Es decir, dado uno o más vértices de malla (un conjunto de semillas), necesito construir un mapa de distancia que almacene la distancia de cada vértice de malla desde el conjunto de semillas (que tendrá una distancia de 0 a ellos mismos).

Después de pasar un tiempo buscando posibles soluciones, obtuve la siguiente imagen:

1) no es trivial, y se han desarrollado diferentes enfoques durante los últimos 20 años más o menos

2) todo algoritmo que tenga en cuenta un dominio 3d está restringido a un dominio triangular

Dicho esto, esta es la foto que tengo:

El algoritmo de Dijkstra se puede usar como una forma de encontrar la ruta más corta entre 2 vértices, siguiendo los bordes de la malla, pero es muy inexacto y dará lugar a una geodésica errónea. Lanthier (LA) propuso una mejora, pero el error sigue siendo bastante alto.

Kimmel y Sethian (KS) propusieron un Método de marcha rápida (FMM) para resolver la ecuación de Eikonal, abordando el problema al calcular la propagación de una onda que comienza en los puntos de la semilla y registrando el tiempo en que la onda cruza cada vértice. Desafortunadamente, este algoritmo, aunque es lo suficientemente simple de implementar, todavía trae un resultado bastante inexacto, y se debe tener cuidado para evitar los triángulos obtusos, o tratarlos de una manera muy especial. Novotni (NV) abordó el problema de la precisión (KS) en un escenario semilla único, pero no está claro si:

a) todavía sufre el problema del ángulo obtuso

b) cuando se usa en un escenario de múltiples puntos de semilla, se debe implementar un solo FMM para cada semilla para poder encontrar la distancia mínima para cada vértice de malla de cada semilla (es decir, en un escenario de 10 puntos de semilla, el FMM tendría para ser ejecutado 10 veces por cada vértice de malla)

En el otro lado, Mitchell & al ha presentado un algoritmo exacto -MMP- que lleva a un error de 0. (MI) en 87, y AFAIK nunca ha sido realmente integrado (probablemente debido a la potencia de cálculo requerida). En el mismo enfoque exacto, Surazhsky y al. (SU) proporcionó un algoritmo exacto alternativo basado en MMP que debería superar a este último en términos de velocidad, lo que todavía conduce a un resultado correcto. Desafortunadamente, la potencia de cálculo requerida para el cálculo, incluso si es mucho menor que la MMP original, todavía es lo suficientemente alta como para que la implementación interactiva en tiempo real no sea factible en este momento. (SU) también propuso una aproximación de su algoritmo exacto, lo que llamaron plano-exacto. Debería tomar el mismo tiempo de cómputo de FMM, mientras que solo trae 1/5 del error, pero:

c) no me queda claro si se puede usar en un escenario de múltiples semillas.

Chen & Han (CH) y Kapoor (KP) han propuesto otros algoritmos de ruta más cortos, pero aunque el primero es absolutamente lento, el segundo es demasiado complicado para implementarlo en la práctica.

así que ... la conclusión es: necesito una distancia desde un conjunto, no el camino más corto entre 2 puntos.

si lo entendí bien

o bien uso FMM para obtener una distancia de cada vértice de un conjunto en una sola pasada,

-o-

use otro algoritmo para calcular la geodésica desde cada vértice de malla a cada punto de semilla y encuentre el más corto (y si lo entendiera bien, eso significaría llamar a ese algoritmo en cada punto de semilla para cada vértice de malla, es decir, en una malla de 10,000 vértices y un conjunto de semillas de 50 puntos, tendría que calcular 500,000 geodésicos para obtener el 10,000 más corto.

¿Me estoy perdiendo de algo? ¿Es FMM la única forma de lidiar con múltiples semillas de distancias en una sola pasada? ¿Alguien sabe si se puede usar el algoritmo plano exacto en un escenario de múltiples puntos de semilla?

thnx

Notas:

(LA): Lanthier & al. "Aproximando caminos más cortos ponderados en superficies poliédricas"

(KS): Kimmel, Sethian "Computación de rutas geodésicas en múltiples"

(NV): Novotni "Computación de distancias geodésicas en mallas triangulares"

(MI): Mitchell & al. "El problema geodésico discreto"

(SU): Surazhsky, Kirsanov & al. "Geodésicas precisas y aproximadas rápidas en mallas"

(CH): Chen, Han, "Los caminos más cortos en el poliedro"

(KP): Kapoor "Cálculo eficiente de las rutas más cortas de geodeisc"

Hay un nuevo documento que explica exactamente cómo resolver su problema: Geodesics in Heat . (Solo lo vi y me recordó su pregunta). La idea es que la ecuación de calor puede considerarse como una descripción de la difusión de partículas desde algún punto central. Aunque modela la difusión aleatoria, si ejecuta la ecuación de calor durante un tiempo suficientemente corto, entonces cualquier partícula que pase de A a B debe haber seguido el camino más corto para que matemáticamente pueda obtener una estimación de la distancia.

El problema es que la proporción de partículas que siguen un camino cerca del camino más corto es muy pequeña, por lo que debe resolver una ecuación diferencial que comienza en grande en alguna región y termina rápidamente en otro lugar. Eso no es probable que se comporte bien numéricamente. El truco es que para mayor t, aunque no mide la distancia correctamente, proporciona el gradiente de la función de distancia y esto se puede usar con otros métodos para obtener la distancia.

TL; DR El papel vinculado resuelve la distancia desde cada punto de una malla a cualquier subdominio, incluidos conjuntos finitos de puntos semilla.

Oh ... y no lo he probado yo mismo.