resueltos puntos punto plano partir numeros negativos julioprofe hallar fracciones faltante entre ejercicios ejemplos distancia coordenada con c# algorithm gis polygon distance

c# - puntos - distancia entre punto



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

Dudo que haya una mejor solución que calcular la distancia entre el rojo y todos los azules y ordenarlos por longitud.

En cuanto a la clasificación, generalmente 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 así como InserciónSort, 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, necesitas 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 de polígono en espacio 2D

La pregunta es, ¿estás dispuesto a cambiar la precisión por la velocidad? Por ejemplo, puede empaquetar todos los polígonos en cajas delimitadoras, donde los lados de las cajas 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í hay una imagen de ejemplo de recuadros delimitadores más avanzados, que no son paralelos a los ejes del sistema de coordenadas:

Cajas de delimitación orientadas - OBB

Sin embargo, esto hace que el cálculo de distancia sea 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 de ejes:

Cuadro delimitador alineado de ejes - AABB

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

Técnicas avanzadas de detección de colisiones

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

Tengo 1 polígono rojo decir y 50 polígonos azules colocados al azar : 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 componen los vértices del polígono como valores para probar la distancia, ya que pueden no ser necesariamente 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!

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

Si quieres polígonos arbitrarios, tal vez lo mejor 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.

Podría funcionar un híbrido: 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 entre ellos, luego usar el trazado de rayos para reducir el verdadero polígono (s) más cercano (s).

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 tiene una buena revisión de ellos. Si recuerdo correctamente, aquellos que solo permiten polígonos convexos son sustancialmente más rápidos.

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 sus límites de poligono 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.

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

Esta técnica de detección tiene la intención de 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 sea un vértice rojo y el otro azul. Llámalo r . La distancia entre los polígonos es a lo sumo 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 mediante un arco de radio r centrado en el vértice. Encuentre la distancia de cada vértice dentro de esta región a 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 cruzarse con la región roja.

Para las formas de polígono 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 hacer 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 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 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)

Comenzaría delimitando todos los polígonos por un círculo delimitador y luego encontraría 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 más bajo que el límite superior de la distancia mínima contra 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 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.

Espero eso ayude

Como otros mencionaron el uso de áreas delimitadoras (recuadros, círculos) pueden permitir descartar algunas interacciones polígono-polígono. Hay varias estrategias para esto, por ejemplo

  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 delimitadas es mayor que la distancia ya encontrada, puede ignorar este polígono. Continúa para todos los polígonos.
  2. Encuentre 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 / cuadros alineados axialmente, o cuadros orientados 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, podría utilizarse el nuevo algoritmo rápido de Yang et al para calcular la distancia entre dos polígonos convexos disjuntos basados ​​en el diagrama de Voronoi que es O (log n + log m).

Tengo que irme a un funeral en un segundo, pero si divide sus polígonos en subpolies convexos, hay algunas optimizaciones que puede hacer. Puedes hacer búsquedas binarias en cada poli para encontrar el vértice más cercano, y luego creo 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 poly, 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.

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

Procese cada polígono primero encontrando:

  • Centro de 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 puede recopilar, por ejemplo, los 5-10 polígonos más cercanos al rojo (busque el centro de distancia para centrar, restar el radio, clasifique la lista y tome los 5 primeros) y luego realice una rutina mucho más exhaustiva.

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