¿Cómo determino cuándo se pueden ver dos puntos móviles entre sí?

Question

Supongamos que tengo dos puntos, Punto1 y Punto2. En un momento dado, estos puntos pueden estar en diferentes posiciones, no son necesariamente estáticos.

El punto 1 se encuentra en alguna posición en el tiempo t, y su posición está definida por las funciones continuas x1 (t) y y1 (t) que dan las coordenadas xey en el tiempo t. Estas funciones no son diferenciables, se construyen por partes a partir de segmentos de línea.

Point2 es lo mismo, con x2 (t) y y2 (t), cada función tiene las mismas propiedades.

Los obstáculos que pueden evitar la visibilidad son polígonos simples (e inmóviles).

¿Cómo puedo encontrar los puntos límite para la visibilidad?

es decir, hay dos tipos de límites: donde los puntos se vuelven visibles y se vuelven invisibles.

Para un límite convertido en visible i, existe algo de ε> 0, de modo que para cualquier número real a, a ∈ (i-ε, i), Point1 y Point2 no son visibles (es decir, el segmento de línea que conecta (x1(a), y1(a)) a (x2(a), y2(x)) cruza algunos obstáculos).

Para b ∈ (i, i + ε) están visibles.

Y es al revés para se convierte en invisible.

¿Pero puedo encontrar un límite preciso y, de ser así, cómo?

Answer 1

Es fácil de check if two lines intersect. Use esto para verificar la intersección de la línea (p1, p2) y cada borde del polígono. Si tiene una intersección, la línea (p1, p2) está obstruida por algún obstáculo.

Si necesita un intervalo de tiempo (en el cual p1 y p2 no están a la vista) puede hacer la verificación anterior para diferentes valores de t (preferiblemente con diferencias relativamente pequeñas), y entre un "visible-t" y una "t invisible" podría hacer una búsqueda binaria hasta llegar a un umbral lo suficientemente pequeño, como eps.

Answer 2

Los cambios de visibilidad solo pueden ocurrir cuando un vértice de obstáculo se encuentra en el segmento de línea Point1-Point2. Por lo tanto, calcule los tiempos de todas las colisiones de vértices. (Intuitivamente, esta debería ser una prueba relativamente simple, ya que los puntos finales viajan linealmente, pero tendré que trabajar en ello para verificar. Lo intentaré más adelante y volveré)

Ahora tiene un conjunto finito de tiempos de colisión. Para cada uno, verifique si el segmento intersecta con cualquier otro borde de obstáculo. Si lo hace, ese borde gobierna la visibilidad y el tiempo no es un límite de visibilidad. Si no lo hace, puede verificar la visibilidad en (t- & epsilon;) y (t + & epsilon;) para determinar la naturaleza del cambio.

Deberá tener una política en algunos casos extremos, como cuando el vértice está en la línea de conexión para un estiramiento continuo. Creo que probablemente todo se reduzca a la pregunta de si los puntos (y los bordes que se ven al final) son opacos.

actualización

El proceso de identificación de las colisiones vértice es de hecho bastante sencillo, sólo implica resolver una ecuación cuadrática poco tediosa en t.Debe hacer esto para cada vértice para cada segmento de movimiento por partes, por lo que supongo que el costo será O (n * m) para n vértices ym periodos de tiempo. (Si los períodos de tiempo de las funciones de posición no están sincronizados, deberá subdividirlos para que así sea).

Considere un solo período de tiempo, y la escala t esté en el rango [0,1]. Cada función de posición es lineal en t, así que defina x1(t) = x10 + x1m * t (es decir, x10 es el valor de inicio y x1m es el gradiente), y de manera similar para y1(t), x2(t) y y2(t). Para un vértice V = (vx, vy), el tiempo (si existe) en la que V se encuentra en el segmento de línea que conecta los puntos viene dada por la ecuación At^2 + Bt + C = 0, donde:

A = x1m * y2m - x2m * y1m 
B = vx * (y1m - y2m) + vy * (x2m - x1m) 
    + x10 * y2m - x20 * y1m 
    + y20 * x1m - y10 * x2m 
C = vx * (y10 - y20) + vy * (x20 - x10) 
    + x10 * y20 + x20 * y10 

(O algo así Dada la probabilidad de errores de transcripción. desde la parte posterior del sobre, recomiendo trabajar con usted mismo antes de implementarlo.)

Si esto tiene una solución real en el rango [0,1], Bob es su tío. Si se reduce a 0 = 0 o somesuch, entonces el punto está en línea todo el tiempo, en cuyo caso debe considerar su política.

Answer 3

Ok, tengo una idea más clara del problema ahora, e inspirada por @walkytalky sugerencia, aquí hay una respuesta más elaborada.

Usted mencionó que p1 y viajan a lo largo de segmentos de línea recta. No sé si estos segmentos están alineados de manera que tanto p1 como siempre comiencen nuevos segmentos al mismo tiempo. Sin embargo, siempre puede cortar un segmento de línea en dos segmentos de línea (con la misma pendiente) para que tanto p1 como siempre comiencen nuevos segmentos de línea al mismo tiempo.

Supongamos p1 desplaza a lo largo de línea A-B, y p2 viajes (al mismo tiempo) a lo largo C-D como un parámetro t va desde 0 a 1. (Esto es, en el tiempo de t=0.5, p1 está en el medio de A-B y p2 en el medio de C-D.)

al permitir que Ax y Ay denotan la coordenada x e y del punto A (y lo mismo para B, C y D) podemos expresar p1 y 01.230.como funciones de t de la siguiente manera:

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay)) 
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy)) 

(. Por ejemplo, cuando t=0, Ax + t*(Bx - Ax) evalúa a Ax, y cuando se evalúa como t=1Bx)

para encontrarse "a-vertex- IS-paso-por-entre-P1-P2" -y -tiempo que hacer lo siguiente:

para cada obstáculo vértice v=(Vx, Vy) tenemos que encontrar una manera que tp1(t), p2(t) y v están en línea uno con el otro.

Esto se puede hacer mediante la resolución de las ecuaciones siguientes (dos ecuaciones y dos desconocido, t y k):

Vx=p1(t).x + k*(p2(t).x - p1(t).x) 
Vy=p1(t).y + k*(p2(t).y - p1(t).y)` 

Si k se encuentra entre 0 y 1, el vértice de polígono v es en realidad entre la línea (extendida) A-B y la línea (extendida) C-D. Si t también está entre 0 y 1, el vértice v se pasa realmente por la línea p1-p2 durante el tiempo que los puntos viajan a lo largo de estos segmentos (ya que cuando t es, digamos, 1.3, los puntos ya estarán en segmentos nuevos).

Una vez que se ha calculado todo "a-vertex-is-passing-by-between-p1-and-p2" -times, es una tarea sencilla de entender el resto. (Es decir, averiguar si se trata de un "devenir-en-vista", "devenir-fuera de la vista" o "ni" tipo de paso):

Para todos los pares t0 y t1 de vertex- consecutiva En los tiempos pasados, verifica si la línea p1((t1-t0)/2)-p2((t1-t0)/2) está libre de intersecciones con un borde de polígono. Si está libre de intersecciones, los puntos estarán a la vista durante todo el período (t0-t1), de lo contrario estarán fuera de la vista durante todo el período (ya que no se pasan otros vértices durante este período de tiempo).