algorithm - for - Verifique la conexión entre dos puntos en el plano 2D

graph theory for dummies

Question

ASI QUE,

El problema

Tengo una pregunta sobre el algoritmo para determinar si dos puntos están conectados en el plano 2D. Yo tengo:

• Matriz de líneas 2D. Cada línea está limitada con su punto inicial de inicio punto 2D. Cada punto es una matriz simple de dos elementos [x,y] - es decir, cada línea se ve como [''start''=>[X0, Y0], ''end''=>[X1, Y1]] Permita que este conjunto de líneas se nombre como L . Las líneas pueden pertenecer una a otra (es decir, una puede ser parte de otra), pueden intersecarse con un solo punto, etc., es decir, no hay restricciones para ellas en el plano 2D. Pero la línea no puede ser un punto, es decir, el inicio de la línea no puede ser igual al final de la línea.
• Dos puntos S y E , es decir matrices [Xs, Ys] y [Xe, Ye]

Ahora, todas las líneas de L se dibujan en el plano. Entonces, S y E también se dibujan y necesito responder a la pregunta: ¿ se puede llegar a E desde S sin intersección de ninguna línea en L ? Y, para ser más específico, ¿qué algoritmo será óptimo? Por ''podría ser alcanzado'' quiero decir que hay una manera en el avión de S a E sin intersección ninguna línea desde L - y, por causa, de esta manera podría ser cualquier cosa, no solo la línea.

Muestra

-como ves, en la muestra S y E no están conectados. También en la muestra hay un caso en el que una línea pertenece por completo a otra (líneas grises y moradas), y un caso en el que una línea tiene un inicio / fin en otra línea (líneas verde y rosa).

Mi acercamiento

Actualmente, tengo un algoritmo polinomial (NP) no determinista para hacer eso. Sus pasos son:

• Encuentra todas las intersecciones para cada par de líneas.
• Crear un nuevo conjunto de líneas a partir de los puntos del primer paso. Si dos líneas tienen una intersección, entonces habrá 4 nuevas líneas con punto de intersección al inicio de cada nueva línea, o pueden ser 3 nuevas líneas si la primera línea tiene su inicio / fin en la segunda línea, o puede ser 2 nuevas líneas si la primera línea tiene su inicio / final coinciden exactamente con el inicio / fin de la segunda línea. Es decir:

por lo tanto, la primera casilla dará como resultado 4 líneas nuevas, 2-4 cajas en 3 líneas nuevas y 5 cajas en 2 líneas nuevas. (las líneas son [A, B] y [C, D] )

• A continuación, en las líneas paso del 2do paso estoy buscando todos los polígonos. El polígono es un conjunto de líneas cerradas (es decir, contiene una parte cerrada del área)
• Estoy determinando para el subconjunto S de tales polígonos que contienen S Para hacer esto, estoy usando un algoritmo simple: contar el número de intersecciones con los bordes del polígono y alguna línea desde S hasta el plano exterior (si es impar, entonces S está dentro del polígono y si es par, entonces afuera). Este es un algoritmo de ray-casting . Entonces lo hago por E
• Ahora, cuando tengo los polígonos establecidos para S y E , simplemente estoy comparando ambos conjuntos. Si son iguales, entonces E podría alcanzarse desde S y no podría ser; de lo contrario.

¿Por qué es este NP?

La respuesta es simple: en el 3er paso realizo la búsqueda de todos los loops en 2D-graph. Dado que el problema de encontrar la longitud de bucle máxima / mínima es NP, entonces también lo es el mío (porque puedo obtener la longitud de bucle máxima / mínima simplemente con la clasificación de bucles resultantes). Buena información sobre esto se encuentra here .

La pregunta

Dado que mi solución actual es NP, quiero saber: ¿puede ser que mi solución para el problema sea una exageración? Es decir, ¿puede haber una solución más simple que dará como resultado un tiempo polinomial?

Answer 1

1. encontrar toda la intersección entre los segmentos de línea
2. eliminar todos los puntos que tienen rango = 1; es decir, es un punto final, solo un segmento de línea está conectado a este punto
3. encontrar el segmento de línea más cercano al punto S
4. encontrar el polígono cuyo lado se encuentra previamente segmento de línea, utilizando el siguiente enfoque:
   1. segmento de línea de partida se da
   2. Marque ambos extremos del segmento inicial, starting = lsS , ending = lsE
   3. encontrar todos los segmentos de línea conectados a lsE , excluyendo el segmento inicial
   4. de los segmentos encontrados elija el segmento más cercano al punto S La línea más cercana es aquella, cuyo centro es posible conectar con el punto S sin intersectar ninguna de las líneas examinadas
   5. eliminar todos los otros segmentos de línea examinados del espacio problema
   6. repite hasta que tengas un polígono completo
5. si el polígono completo contiene ambos puntos E y S, están conectados

Es un poco similar a la primera búsqueda en profundidad.

En cada paso solo trabajas con vecinos inmediatos del último punto que hayas resuelto con éxito.

Answer 2

Básicamente, el problema se reduce a:
1) Determine todos los polígonos que encierran un espacio que no contenga ningún otro polígono. En tu ejemplo anterior, tienes 3 formas / ciclos / polígonos que no contienen ninguna otra: el cuadrilátero que contiene S, el cuadrilátero que contiene E y el triángulo debajo de los 2 de ellos.
2) Determine si S y E están en el lado opuesto dentro / fuera de cualquiera de estos polígonos.

Para la parte 1, debes construir un gráfico:

Cree una matriz de puntos de intersección de su línea determinada, esto es N ^ 2. Recuerde de qué 2 líneas proviene cada punto de intersección. Estos puntos de intersección son los vértices de tu gráfica.

Dos vértices están "conectados" si son de la misma línea y no hay otro punto de intersección entre ellos. No confíes en la precisión del punto flotante para determinar esto, obviamente.

Ahora deseas encontrar los polígonos en tu diseño. Un gráfico puede, en general, contener un número exponencial de ciclos. Sin embargo, cada borde solo puede bordear 2 polígonos "internos", por lo que solo estamos interesados ​​en un subconjunto polinómico de los ciclos. Así que elija un borde, luego encuentre el siguiente borde en el polígono y siga repitiendo hasta que regrese al punto de partida o determine que el primer borde no era parte de un polígono.

Supongamos que vienes del borde E = (U, V) y quieres encontrar el siguiente borde en el polígono (compartiendo el mismo vértice V).
1) Crea un vector T como U - V.
2) Cree el conjunto de aristas A que son adyacentes al vértice V. Elimine E de ese conjunto.
3) Si el conjunto está vacío, entonces el borde no es parte de un polígono.
4) Para cada borde (Q, V) en A, construya un vector R como Q - V. (Recuerde que Q y V representan puntos en el plano 2D).
5) Normalizar R: divídelo por su longitud para crear un vector de longitud 1.
6) Determine CrossProductValue (T, R).
7) El borde en A con el mínimo CrossProductValue es el siguiente borde en uno de los polígonos adyacentes. El borde en A con el CrossProductValue más grande es el siguiente borde en el otro polígono.

CrossProductChecker(2D T, 2D R) {
  return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions
}

Entonces usa esto para encontrar tus polígonos. Busca la relación entre productos cruzados y sinusoides para tener una idea de cómo funciona esto.

============

Ahora que tiene todos sus polígonos, todo lo que hay que hacer es verificar si hay uno en el que S está dentro y E fuera de, o al revés.

La forma más fácil de hacerlo es trazar una línea de S a E. Si se cruza con un polígono (ciclo desde arriba) un número par de veces, ambos están dentro o fuera del polígono, así que sigue comprobando.

Si la línea se cruza con un ciclo un número impar de veces, una está dentro del polígono y la otra está afuera, por lo que puede decir que no hay una ruta.

Answer 3

Calcule el gráfico plano lineal formado por los segmentos de línea y ubique las caras a las que pertenecen S y E. Hay un camino si y solo si S y E pertenecen a la misma cara. Los primeros dos pasos son algoritmos estándar, de tiempo polinomial de geometría computacional, con muchas descripciones e implementaciones disponibles.

Answer 4

Hay dos pasos para el algoritmo.

1. Find out the maximum polyogn encompassing S and E 
    (which could possibly be an open polygon, so convex hull algorithm needs 
    to be modified)
2. E can be reached from S if
    (Case 1) The polygons are the same
    (Case 2) Both are open polygons.

Explicación:

Paso 1: Encuentra el polígono abarcador máximo de un punto P

Form a set of points by adding the end-points and all possible 
    intersections. (O(n^2))
Eliminate points that can only be reached from P by crossing another line. 
    This can be done by finding the intersection of the line joining P to each 
    point with all other lines (O (n^3)).
Form a convex hull of the remaining points. 
    Here it should be noted that the resulting polygon may not be closed. 
    So, the convex hull algorithm needs to be modified to get rid of 
    those possible edges which don''t have a direct connection. 
    This can be efficiently done by an appropriate data structure 
    like a graph (O(n^2) in worst case)

Paso 2: la comparación necesitaría algún tipo de clasificación de los vértices del polígono. Esto sería máximo O (n long n)

Entonces, la complejidad del algoritmo resultante sería O (n ^ 3)

Answer 5

Puede construir un llamado "Gráfico de visibilidad" que conecta dos vértices de obstáculo si son directamente visibles. El camino más corto en este gráfico (con S y E agregado) será el camino libre de obstáculos más corto entre S y E en su espacio de configuración. Los algoritmos y las optimizaciones relativas al Gráfico de visibilidad son bien conocidos y ampliamente descritos.

La dificultad principal que tendrá es manejar casos de esquina para que no pueda "fugarse" en una intersección incorrecta al otro lado del segmento (segmentos compartidos, punto final como intersección, etc.). Manejar tales casos de esquina no es algorítmicamente difícil, pero requiere paciencia.

EDITAR:

Así que permítanme ser más formal: construyan un gráfico G(Ver, Edg) donde Ver contenga todos los puntos finales del segmento, S y E ; y Edg contiene todos los pares de vértices que son directamente visibles (incluso siguiendo el segmento).