¿Cuál es la forma más rápida de encontrar la distancia cartesiana más corta entre dos polígonos?

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

Pregunta

Tengo 1 polígono rojo decir y 50 polígonos azules colocados al azar - están situados en zonas geográficas espacio 2D.¿Cuál es el algoritmo más rápido para encontrar la distancia más corta entre un polígono rojo y su polígono azul más cercano?

Tenga en cuenta que no se trata de un caso sencillo de tomar los puntos que forman los vértices del polígono como valores para probar la distancia, ya que no necesariamente pueden ser los puntos más cercanos.

Entonces, al final, la respuesta debería devolver el polígono azul más cercano al rojo singular.

¡Esto es más difícil de lo que parece!

¿Fue útil?

Solución

Dudo que haya una mejor solución que calcular la distancia entre el rojo y cada azul y ordenarlos por longitud.

Con respecto a la clasificación, por lo general QuickSort es difícil de superar en rendimiento (uno optimizado, que corta la recursividad si el tamaño es inferior a 7 elementos y cambia a algo como InsertionSort, tal vez ShellSort).

Por lo tanto, supongo que la pregunta es cómo calcular rápidamente la distancia entre dos polígonos; después de todo, es necesario hacer este cálculo 50 veces.

El siguiente enfoque también funcionará para 3D, pero probablemente no sea el más rápido:

Distancia mínima del polígono en el espacio 2D

La pregunta es: ¿estás dispuesto a cambiar la precisión por la velocidad?P.ej.puede empaquetar todos los polígonos en cuadros delimitadores, donde los lados de los cuadros sean paralelos a los ejes del sistema de coordenadas.Los juegos 3D utilizan este enfoque con bastante frecuencia.Por lo tanto, necesita encontrar los valores máximo y mínimo para cada coordenada (x, y, z) para construir el cuadro delimitador virtual.Calcular las distancias de estos cuadros delimitadores es entonces una tarea bastante trivial.

Aquí hay una imagen de ejemplo de cuadros delimitadores más avanzados, que no son paralelos a los ejes del sistema de coordenadas:

Cuadros delimitadores orientados - OBB

Sin embargo, esto hace que el cálculo de la distancia sea menos trivial.Se utiliza para la detección de colisiones, ya que no necesita saber la distancia para eso, solo necesita saber si un borde de un cuadro delimitador se encuentra dentro de otro cuadro delimitador.

La siguiente imagen muestra un cuadro delimitador con ejes alineados:

Cuadro delimitador de ejes alineados - AABB

Los OOB son más precisos, los AABB son más rápidos.Quizás te gustaría leer este artículo:

Técnicas avanzadas de detección de colisiones

Esto siempre supone que está dispuesto a cambiar la precisión por la velocidad.Si la precisión es más importante que la velocidad, es posible que necesites una técnica más avanzada.

Otros consejos

Es posible que pueda reducir el problema y luego realizar una búsqueda intensiva en un conjunto pequeño.

Procese cada polígono primero encontrando:

  • Centro del polígono
  • Radio máximo del polígono (es decir, punto en el borde/superficie/vértice del polígono más alejado del centro definido)

Ahora puedes recolectar, digamos, los 5 a 10 polígonos más cercanos al rojo (encontrar la distancia de centro a centro, restar el radio, ordenar la lista y tomar los 5 primeros) y luego hacer una rutina mucho más exhaustiva.

Para formas poligonales con un número razonable de puntos límite, como en un SIG o una aplicación de juegos, podría ser más rápido y sencillo realizar una serie de pruebas.

Para cada vértice en el polígono rojo calcule la distancia a cada vértice en los polígonos azules y encuentre la más cercana (sugerir, compare la distancia^2 para que no necesite el sqrt ()) encuentre el más cercano, luego verifique el vértice en cada lado. del vértice rojo y azul encontrado para decidir qué segmentos de línea están más cerca y luego encontrar el enfoque más cercano entre dos segmentos de línea.

Ver http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (es fácil simplemente para el segundo caso)

Esta técnica de detección tiene como objetivo reducir la cantidad de cálculos de distancia que necesita realizar en el caso promedio, sin comprometer la precisión del resultado.Funciona en polígonos convexos y cóncavos.

Encuentre la distancia mínima entre cada par de vértices de modo que uno sea rojo y el otro azul.Llámalo r.La distancia entre los polígonos es como máximo. r.Construya una nueva región a partir del polígono rojo donde cada segmento de línea se mueve hacia afuera por r y está unida a sus vecinas por un arco de radio r está centrado en el vértice.Encuentra la distancia desde cada vértice dentro de esta región hasta cada segmento de línea del color opuesto que cruza esta región.

Por supuesto, puede agregar un método aproximado, como cuadros delimitadores, para determinar rápidamente cuál de los polígonos azules no puede intersectarse con la región roja.

Sé que dijiste "la distancia más corta", pero realmente querías decir que la solución óptima o una solución "buena/muy buena" está bien para tu problema.

Porque si necesita encontrar la solución óptima, debe calcular la distancia entre todos los límites del polígono de origen y de destino (no solo los vértices).Si estás en un espacio 3D, entonces cada límite es un plano.Eso puede ser un gran problema (O(n^2)) dependiendo de cuántos vértices tenga.

Entonces, si tiene un recuento de vértices que lo convierte en un número aterrador Y una solución "buena/muy buena" está bien para usted, opte por una solución o aproximación heurística.

Quizás quieras mirar el sacrificio de Voronoi.Documento y vídeo aquí:

http://www.cs.unc.edu/~geom/DVD/

Comenzaría por delimitar todos los polígonos mediante un círculo delimitador y luego encontrar un límite superior de la distancia mínima.Luego, simplemente verificaría los bordes de todos los polígonos azules cuyo límite inferior de distancia sea menor que el límite superior de distancia mínima con todos los bordes del polígono rojo.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Pero todo depende de tus datos.Si los polígonos azules son relativamente pequeños en comparación con las distancias entre ellos y el polígono rojo, entonces este enfoque debería funcionar bien, pero si están muy cerca, no guardará nada (muchos de ellos estarán lo suficientemente cerca).Y otra cosa: si estos polígonos no tienen muchos vértices (como si la mayoría de ellos fueran triángulos), entonces podría ser casi igual de rápido comparar cada borde rojo con cada borde azul.

Espero eso ayude

Como otros han mencionado, el uso de áreas delimitadoras (cuadros, círculos) puede permitirle descartar algunas interacciones polígono-polígono.Hay varias estrategias para esto, p.e.

  1. Elige cualquier polígono azul y encuentra la distancia desde el rojo.Ahora elige cualquier otro polígono.Si la distancia mínima entre las áreas delimitadoras es mayor que la distancia ya encontrada, puede ignorar este polígono.Continúe para todos los polígonos.
  2. Encuentre la distancia mínima/distancia centroide entre el polígono rojo y todos los polígonos azules.Ordena las distancias y considera primero la distancia más pequeña.Calcule la distancia mínima real y continúe a través de la lista ordenada hasta que la distancia máxima entre los polígonos sea mayor que la distancia mínima encontrada hasta ahora.

Su elección de círculos/cuadros alineados axialmente o cuadros orientados puede tener un gran efecto en el rendimiento del algoritmo, dependiendo del diseño real de los polígonos de entrada.

Para el cálculo de la distancia mínima real, puede utilizar el método de Yang et al.Un nuevo algoritmo rápido para calcular la distancia entre dos polígonos convexos separados basado en el diagrama de Voronoi' que es O(log n + log m).

Tengo que irme corriendo a un funeral en un segundo, pero si divides tus polígonos en subpoliías convexas, hay algunas optimizaciones que puedes hacer.Puedes hacer una búsqueda binaria en cada poli para encontrar el vértice más cercano, y luego creer el punto más cercano debe ser ese vértice o un borde adyacente.Esto significa que deberías poder hacerlo en log(log m * n) donde m es el número promedio de vértices en un poli y n es el número de polis.Esto es algo apresurado, por lo que podría estar equivocado.Daré más detalles más adelante si así lo desea.

Podrías comenzar comparando la distancia entre los cuadros delimitadores.Probar la distancia entre rectángulos es más fácil que probar la distancia entre polígonos, y puedes eliminar inmediatamente cualquier polígono que esté a una distancia mayor que el recto_más cercano + su_diagonal (posiblemente puedas refinarlo aún más).Luego, puedes probar los polígonos restantes para encontrar el polígono más cercano.

Existen algoritmos para encontrar la proximidad de polígonos; estoy seguro de que Wikipedia tiene una buena reseña de ellos.Si no recuerdo mal, aquellos que sólo permiten polígonos convexos son sustancialmente más rápidos.

Creo que lo que estás buscando es el algoritmo A*, que se utiliza en la búsqueda de rutas.

El enfoque ingenuo es encontrar la distancia entre los objetos rojos y 50 azules, por lo que estás viendo 50 cálculos pitagóricos en 3D + clasificación para encontrar la respuesta.Sin embargo, eso solo funcionaría para encontrar la distancia entre los puntos centrales.

Si desea polígonos arbitrarios, tal vez lo mejor sea una solución de trazado de rayos que emita rayos desde la superficie del polígono rojo con respecto a la normal e informe cuando se alcanza otro polígono.

Un híbrido podría funcionar: podríamos encontrar la distancia desde los puntos centrales, suponiendo que tuviéramos alguna noción del tamaño relativo de los polígonos azules, podríamos seleccionar el conjunto de resultados al más cercano entre ellos y luego usar el trazado de rayos para reducir los puntos verdaderamente polígono(s) más cercano(s).

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