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

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?

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).

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.

Changes of visibility can only occur when an obstacle vertex lies on the Point1-Point2 line segment. So, calculate the times of all such vertex collisions. (Intuitively this should be a relatively simple test since the endpoints are travelling linearly, but I'll need to actually work through it to check. I'll give it a go later on and get back.)

You now have a finite set of collision times. For each one, check if the segment intersects any other obstacle edges. If it does, that edge governs the visibility and the time isn't a visibility boundary. If it doesn't, you can check visibility at (t-ε) and (t+ε) to determine the nature of the change.

You'll need to have a policy on some edge cases, such as when the vertex is on the connecting line for a continuous stretch. I think these probably all boil down to the question of whether points (and edges viewed end on) are opaque.

Update

The process of identifying the vertex collisions is indeed reasonably straightforward, it just involves solving a slightly tedious quadratic equation in t. You need to do this for each vertex for each piecewise segment of movement, so I guess the cost will be O(n*m) for n vertices and m time periods. (If the time periods of the position functions are not in sync, you will need to subdivide them to become so.)

Consider just a single time period, and scale t to be in the range [0,1]. Each position function is linear in t, so define x1(t) = x10 + x1m * t (ie, x10 is the start value and x1m is the gradient), and similarly for y1(t), x2(t) and y2(t). For a vertex V = (vx, vy), the time (if any) at which V lies on the line segment connecting the points is given by the equation At^2 + Bt + C = 0, where:

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

(Or something like that. Given the likelihood of transcription errors from the back of the envelope, I'd strongly suggest working it through yourself before implementing!)

If this has a real solution in the range [0,1], Bob's your uncle. If it reduces to 0 = 0 or somesuch, then the point is on the line the whole time, in which case you have to consider your policy.