¿Cuál es el camino más rápido para encontrar la distancia más corta entre dos cartesiano polígonos

Question

tengo 1 polígono rojo decir y 50 colocadas al azar polígonos azules - que están situados en el espacio geográfico 2D. ¿Cuál es el algoritmo más rápido/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 es un simple caso de tomar los puntos que forman los vértices del polígono como valores para probar la distancia, ya que pueden no ser necesariamente los puntos más cercanos.

Por lo tanto, 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!

Answer 1

Dudo que es mejor solución que el cálculo de la distancia entre el rojo y cada uno azul y clasificación de éstos por la longitud.

En cuanto a la clasificación, generalmente QuickSort es difícil de superar en rendimiento (uno optimizado, que interrumpe 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 funcionará para 3D, así, pero probablemente no es el más rápido:

Minimum Polygon Distance in 2D Space

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

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

Oriented Bounding Boxes - OBB

Sin embargo, esto hace que el cálculo de la distancia menos trivial. Se utiliza para la detección de colisiones, ya que no necesita conocer 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 alineado ejes:

Axes Aligned Bounding Box - AABB

oobs son más precisos, AABBs son más rápidos. Tal vez le gustaría leer este artículo:

Advanced Collision Detection Techniques

Esto siempre es suponiendo, que está dispuesto a negociar la precisión para la velocidad. Si la precisión es más importante que la velocidad, es posible que necesite una técnica más avanzada.

Answer 2

¿Tal vez la distancia Frechet es lo que buscas?

Computing the Fréchet distance between two polygonal curves
Computing the Fréchet Distance Between Simple Polygons

Answer 3

El enfoque ingenuo es encontrar la distancia entre el rojo y el azul 50 objetos - por lo que usted está buscando en 50 cálculos pitagóricos 3D + de clasificación para encontrar la respuesta. Sin embargo, eso solo funcionaría realmente para encontrar la distancia entre los puntos centrales.

Si desea polígonos arbitrarios, quizás su mejor opción sea una solución de trazado de rayos que emite rayos desde la superficie del polígono rojo con respecto a la normal e informa cuando se golpea 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 descartar el conjunto de resultados al más cercano, luego usar el trazado de rayos para reducir el (los) polígono (s) verdaderamente más cercano (s).

Answer 4

Para formas poligonales con un número razonable de puntos límite, como en un SIG o aplicación de juegos, podría ser más fácil 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 el más cercano (pista, compare distancia^2 para no necesitar el sqrt()) Encuentre lo más cercano, luego controle 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 acercamiento 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 caso 2d)

Answer 5

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

Proceso de cada polígono primero mediante la búsqueda de:

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

Ahora puede recopilar, por ejemplo, los 5-10 polígonos más cercanos al rojo (busque el centro de distancia para centrar, restar el radio, ordenar la lista y tomar los 5 primeros) y luego realizar una rutina mucho más exhaustiva.

Answer 6

Puede comenzar comparando la distancia entre los cuadros delimitadores. Probar la distancia entre los rectángulos es más fácil que probar la distancia entre los polígonos, y puedes eliminar inmediatamente cualquier polígono que esté más cercano que close_rect + its_diagonal (posiblemente puedas refinar eso 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 del polígono. Estoy seguro de que Wikipedia los revisa bien. Si recuerdo correctamente, aquellos que solo permiten polígonos convexos son sustancialmente más rápidos.

Answer 7

Sé que dijiste "la distancia más corta" pero realmente querías decir 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 de poligon de origen y de destino (no solo los vértices). Si estás en el espacio 3D, cada límite es un avión. Eso puede ser un gran problema (O (n^2)) dependiendo de cuántos vértices tenga.

Así que si tiene conteo de vértices que hace que los cuadrados sean un número aterrador Y una solución "buena/muy buena" está bien para usted, busque una solución heurística o una aproximación.

Answer 8

Esta técnica de detección está diseñada para reducir el número 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.

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

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

Answer 9

Es posible que desee mirar Voronoi Culling. Papel y video aquí:

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

Answer 10

Me gustaría empezar por saltando todos los polígonos por un círculo de delimitación 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 es menor que el límite superior de la distancia mínima con respecto a 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 sus 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 se 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 tan rápido simplemente verificar cada borde rojo contra cada borde azul.

creo que sirve

Answer 11

Como otros han mencionado el uso de áreas delimitadas (cajas, círculos) le puede permitir descartar algunas interacciones polígono polígonos. Existen varias estrategias para esto, p.

1. Elija cualquier polígono azul y encuentre la distancia desde el rojo. Ahora elige cualquier otro polígono. Si la distancia mínima entre las áreas delimitadas es mayor que la distancia ya encontrada, puede ignorar este polígono. Continúa para todos los polígonos.
2. Encuentra la distancia mínima/distancia centroide entre el polígono rojo y todos los polígonos azules. Clasifique las distancias y considere primero la distancia más pequeña. Calcule la distancia mínima real y continúe por la lista ordenada hasta que la distancia máxima entre los polígonos sea mayor que la distancia mínima encontrada hasta el momento.

Su elección de círculos/cajas alineadas axialmente, o cajas orientadas puede tener un gran efecto en el rendimiento del algoritmo, dependiendo de la disposición real de los polígonos de entrada.

Para el cálculo de la distancia mínima real se puede usar el 'A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram' de Yang et al 'que es O (log n + log m).

Answer 12

Tengo que correr a un funeral en un segundo, pero si divide sus polígonos en subpolies convexos, hay algunas optimizaciones que puede hacer. Puede hacer una búsqueda binaria en cada poli para encontrar el vértice más cercano, y luego I cree que 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 polies. Esto es un poco apresurado, entonces podría estar mal. Dará más detalles más adelante si lo desea.

Answer 13

Creo que lo que está buscando es el algoritmo A *, se usa en la búsqueda.