How do I determine when two moving points become visible to each other?

Question

Suppose I have two points, Point1 and Point2. At any given time, these points may be at different positions-- they are not necessarily static.

Point1 is located at some position at time t, and its position is defined by the continuous functions x1(t) and y1(t) giving the x and y coordinates at time t. These functions are not differentiable, they are constructed piecewise from line segments.

Point2 is the same, with x2(t) and y2(t), each function having the same properties.

The obstacles that might prevent visibility are simple (and immobile) polygons.

How can I find the boundary points for visibility?

i.e. there are two kinds of boundaries: where the points become visible, and become invisible.

For a become-visible boundary i, there exists some ϵ>0, such that for any real number a, a ∈ (i-ϵ, i) , Point1 and Point2 are not visible (i.e. the line segment that connects (x1(a), y1(a)) to (x2(a), y2(x)) crosses some obstacles).

For b ∈ (i, i+ϵ) they are visible.

And it is the other way around for becomes-invisible.

But can I find a precise such boundary, and if so, how?

Answer 1

It's easy to check if two lines intersect. Use this to check intersection of the line (p1, p2) and each polygon edge. If you have any intersection, the line (p1, p2) is obstructed by some obsticle.

If you need a time interval (at which p1 and p2 are not in line of sight) you could do the above check for different values of t (preferably with relatively small differences), and between a "visible-t" and an "invisible-t" you could do a binary search until you reach a small enough threshold, such as eps.

Answer 2

Ok, I have a clearer picture of the problem now, and inspired by @walkytalky suggestion, here is a more ellaborate answer.

You mentioned that p1 and p2 travel along straight line segments. I don't know if these segments are aligned in a way such that both p1 and p2 always start new segments at the same time. However, you can always cut a line segment into two line segments (with the same slope) so that both p1 and p2 always start new line segments at the same time.

Assume p1 travels along line A-B, and p2 travels (at the same time) along C-D as a parameter t goes from 0 to 1. (That is, at time t=0.5, p1 is in the middle of A-B and p2 in the middle of C-D.)

By letting Ax and Ay denote the x and y coordinate of point A (and similarly for B, C and D) we can express p1 and p2 as functions of t in the following way:

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

(For instance, when t=0, Ax + t*(Bx - Ax) evaluates to Ax, and when t=1 it evaluates to Bx.)

To find each "a-vertex-is-passing-by-between-p1-and-p2"-time we do the following:

For each obstacle vertex v=(Vx, Vy) we need to find a t so that p1(t), p2(t) and v are in line with each other.

This can be done by solving the following equations (two equations, and two unknown, t and k):

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

If k lies between 0 and 1, the polygon vertex v is actually between the (extended) A-B line and the (extended) C-D line. If t is also between 0 and 1, the vertex v is actually passed by the p1-p2 line during the time the points travel along these segments (since when t is, say, 1.3, the points will already be on new segments).

Once all "a-vertex-is-passing-by-between-p1-and-p2"-times has been computed, it's a simple task to figure out the rest. (That is, figuring out if it is a "becoming-in-sight", "becoming-out-of-sight" or "neither" type of passing):

For all pairs t0 and t1 of consecutive vertex-passing times, you check if the line p1((t1-t0)/2)-p2((t1-t0)/2) is free of intersections with a polygon edge. If it is free of intersections, the points will be in line of sight the entire period (t0-t1), otherwise they will be out of sight the entire period (since no other vertices are passed during this time period).