Comprobar la conexión entre dos puntos en el plano 2D

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

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

EDITAR:

Así que permítanme ser más formal: construir un gráfico G(Ver, Edg) donde Ver contiene todos los extremos del segmento, S y E; y Edg contiene todos los pares de vértices que son directamente visibles (incluyendo después del segmento).

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: Encuentre el polígono que abarca 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 ordenación de los vértices de los polígonos. Esto sería máximo O (n largo n)

Así que la complejidad del algoritmo resultante sería O (n^3)

Calcule el gráfico plano de línea recta formado por los segmentos de línea y localice 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 dos primeros pasos son algoritmos de tiempo polinómico estándar de geometría computacional, con muchas descripciones e implementaciones disponibles.

1. buscar todas las intersecciones entre segmentos de línea
2. elimine 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. encuentra el segmento de línea más cercano al punto S
4. buscar polígono cuyo lado se encuentra previamente segmento de línea, utilizando el siguiente enfoque:
   1. se da el segmento de la línea de salida
   2. marca ambos extremos del segmento inicial, starting = lsS, ending = lsE
   3. buscar todos los segmentos de línea conectados a lsE, excluido el segmento inicial
   4. de los segmentos encontrados elija el segmento que está más cerca del punto S la línea más cercana es la que, cuyo centro es posible conectar con el punto S sin intersecar ninguna de las líneas examinadas
   5. elimine todos los demás segmentos de línea examinados del espacio problema
   6. repita hasta que tenga polígono completo
5. si el polígono completo contiene ambos puntos E y S, estos están conectados

Es un poco similar a la profundidad primero búsqueda.

En cada paso solo se trabaja con vecinos inmediatos del último punto resuelto con éxito.