## Determining line of sight over time

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

cribbit
Posts: 1
Joined: Wed Jul 19, 2017 11:32 pm UTC

### Determining line of sight over time

There are two points in a space. The space is filled with objects. If both points are stationary is it trivial to determine whether or not they can see each other. However, both points are moving. Luckily, they are moving in straight lines with a constant speed.

How would I go about determining at what point in time, if any, the points would have line of sight to each other?

Posts: 163
Joined: Sat Feb 13, 2010 11:25 pm UTC

### Re: Determining line of sight over time

I wonder if it might be possible to transform the problem into a version where they are stationary, but the location/movement of everything else gets warped.

If we assign both of them a "mass" of 1, then the "center of mass" should be their midpoint, and because they are moving in a constant speed and direction, the "center of mass" will also be moving in a constant speed and direction.

Then I think we could shift our coordinates and the velocity of everything so that the same stuff is described except that the center of mass of the two points is stationary. The line segment between the two moving points will always go through this point, and have the same distance in both directions.

So, the things that change with the line segment (line of sight) would then be its direction along with its length.

Then I think you could probably rotate the space over time in order to keep the orientation of the line segment fixed, and then if you just also stretch/squash the space, either in the direction of the line segment or in all directions, in order to keep the length of it fixed, all that is left is figuring out when the other objects pass through / don't pass through the line segment, after their motion has been suitably adjusted.

Oh, wait, were the other objects already moving or no?

If the other objects are stationary I'd guess it is probably more efficient to handle it some other way?
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.

Xanthir
My HERO!!!
Posts: 5358
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Determining line of sight over time

You can trace the path of each object individually, seeing when, if at all, it intersects the line going between the two target points. Do this for every object, and you'll have a list of precisely when the line-of-sight is blocked, and thus can easily tell if there are any clear periods where nothing is blocking.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

LaserGuy
Posts: 4559
Joined: Thu Jan 15, 2009 5:33 pm UTC

### Re: Determining line of sight over time

You should be able to fairly trivially write a time-varying equation for the line that connects the two objects you're interested in, then look at the trajectories of all of the other objects you're interested in and see when they intersect it.

The problem doesn't actually change that much depending on whether the objects are stationary or not, I don't think.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

cribbit wrote:There are two points in a space. The space is filled with objects. If both points are stationary is it trivial to determine whether or not they can see each other. However, both points are moving. Luckily, they are moving in straight lines with a constant speed.

How would I go about determining at what point in time, if any, the points would have line of sight to each other?
What am I missing? The question being asked, at least to me is, How far can you see. Restating the problem with this in mind, asks the question, how far can you see in a snow storm? Which is a function of how quickly it is snowing and the average size of the snowflakes. 3D game designers ask similar questions a lot. If you were a nasty, cranky, suspicious old man you would eye this question with caution.

Lets do that.

01 There are two points in a space. Check
02 The space is filled with objects. What does this mean? How many angels can stand on the head of a pin?
03 If both points are stationary is it trivial to determine whether or not they can see each other. See footnote.
04 However, both points are moving.
05 Luckily, they are moving in straight lines with a constant speed.

06 How would I go about determining at what point in time, if any, the points would have line of sight to each other?

Footnote:
The movement of the points doesn't matter. If the condition is seeing or not seeing then you are talking about a specific instant in time. Look at your photograph collection if that needs demonstrating. This trivializes to, can I see it or not from a fixed perspective? If 03 is true than 06 is trivial as well because they are functionally equivalent.

It is possible that my fundamental conceptual understanding is defective. In which case the foregoing is noise and thus my apology to the poster.

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Determining line of sight over time

morriswalters wrote:
cribbit wrote:There are two points in a space. The space is filled with objects. If both points are stationary is it trivial to determine whether or not they can see each other. However, both points are moving. Luckily, they are moving in straight lines with a constant speed.

How would I go about determining at what point in time, if any, the points would have line of sight to each other?
What am I missing? The question being asked, at least to me is, How far can you see.
[snip]
The movement of the points doesn't matter. If the condition is seeing or not seeing then you are talking about a specific instant in time.

Sure, for any particular point in time you can calculate whether the points see each other. It is not so easy to solve in the opposite direction - at what time will the view be obscured and when will it not?

If they can see each other at t=0, and can't see each other at t=1, then you can use a binary search to home in on the exact point in time when the view became obscured.

Suppose they can't see at t=0, and they can't see at t=1. Was there ever a moment in between where they could see? With some work this too can be checked. Just examine the object that blocks the view at t=0, and see if the trajectories are such that it no longer blocks the view at some time before t=1. If so, see what is blocking the view then, if anything, and repeat the same thing. Eventually you either have an unobscured view, or you reach t=1 without ever seeing each other.

Suppose they can see each other at t=0, and also at t=1. Was there ever a moment in between where the view was obscured? This is much harder to work out. You basically have to check all the objects in the space to see if they cross the line of sight. In computer graphics this is where clever data structures are needed (e.g. Octrees) so that whole clusters of objects can be eliminated at once.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

Sure. I'm trying to understand the point? Do you think her/his problem is solvable?

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Determining line of sight over time

morriswalters wrote:Sure. I'm trying to understand the point? Do you think her/his problem is solvable?

The OP is not clear:
cribbit wrote:If both points are stationary is it trivial to determine whether or not they can see each other. However, both points are moving.

As you said, and I agree, that part is still essentially trivial with moving observers.

But this is the question they asked:
cribbit wrote:How would I go about determining at what point in time, if any, the points would have line of sight to each other?

This question is not trivial at all, as it asks for the times when the visibility changes, not for the visibility at a specific time. I explained why this is hard in some situations in the sense that it can take a lot of (relatively straightforward) calculations and it is difficult to reduce that amount. It is hard to optimise it for a computer game for example.
By the way, having the observers moving instead of stationary does not change the difficulty of this question.

Flumble
Yes Man
Posts: 2111
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Determining line of sight over time

jaap wrote:By the way, having the observers moving instead of stationary does not change the difficulty of this question.

Are you dropping the implicit assumption that the objects in the space are stationary?

Let me add some cents:

Depending on the type of objects, you can calculate exactly when the moving line segment intersects with one of them. E.g. with a linesegment-circle or linesegment-sphere intersection, the distance of the line to the midpoint can be parametrized and the moments when the line touches the object, if any, can be solved (checking whether the hyposphere/hypercircle is touching the line segment is left as an exercise for the reader). If I understand correctly, this can be done for any convex object using the Separating Axes theorem*, and any concave object can be decomposed into convex objects. (Well, decomposing something like a Koch snowflake will lead to an infinite number of convex objects, but you can make a special case for linesegment-snowflake intersections.)

And as Xanthir said, given the intersection time interval(s) of each object, you can take the union of them and the gaps that are left are the periods when there is a line-of-sight. (or take the intersection of all time intervals when the line-of-sight is not blocked, same thing)

*since the line end points resp. the object has a constant velocity and the object is convex, the object can only intersect over one time interval, so you only have to look for a collision time from t=0 and t=1.

DavidSh
Posts: 174
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Determining line of sight over time

Flumble wrote:*since the line end points resp. the object has a constant velocity and the object is convex, the object can only intersect over one time interval, so you only have to look for a collision time from t=0 and t=1.

But consider the simple case in 1 dimension, where the obstacle is the interval [0,1], and endpoint A starts at -1, and moves to 4, and endpoint Z starts at 4, and moves to -1. The line intersects the obstacle for t<= 0.4, and for t >= 0.6. For 0.4 < t < 0.6 there is no intersection. It looks like in higher dimensions the possibility is there of two separate time intervals of intersection.

---
I add that while a line segment is convex, the set of points in space-time on the line segment between linearly moving endpoints is not necessarily convex, in dimension 2 or more.
Last edited by DavidSh on Wed Jul 26, 2017 12:12 pm UTC, edited 1 time in total.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

The problem is with initial conditions. If you know where the 2 points are at the start, and the size and placement of the objects, and the size of the space, the problem, while not trivial, is solvable. The OP didn't bound his problem. In a computer game you know where everything is. In effect you know what it is possible to see. So you can test. His set up is chaotic.

He didn't define the space.
He didn't define the objects.
He defined the view port as a line between two points.
He put the points in motion.
And he never mentions any initial conditions.

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Determining line of sight over time

Flumble wrote:
jaap wrote:By the way, having the observers moving instead of stationary does not change the difficulty of this question.

Are you dropping the implicit assumption that the objects in the space are stationary?

I guess so, because I never really thought of the objects as stationary.

DavidSh wrote:
Flumble wrote:*since the line end points resp. the object has a constant velocity and the object is convex, the object can only intersect over one time interval, so you only have to look for a collision time from t=0 and t=1.

But consider the simple case in 1 dimension, where the obstacle is the interval [0,1], and endpoint A starts at -1, and moves to 4, and endpoint Z starts at 4, and moves to -1. The line intersects the obstacle for t<= 0.4, and for t >= 0.6. For 0.4 < t < 0.6 there is no intersection. It looks like in higher dimensions the possibility is there of two separate time intervals of intersection.

In 1-d involves the observers passing through an object. If you allow that in 3-d, too, then you definitely get the same thing there.
But I think you are right, even in 2-d. You can consider the line-of-sight over time to form a ruled surface, like Hyperbolic paraboloid, and even a stationary convex object can be made to intersect that in two places.

DavidSh
Posts: 174
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Determining line of sight over time

jaap wrote:In 1-d involves the observers passing through an object. If you allow that in 3-d, too, then you definitely get the same thing there.
But I think you are right, even in 2-d. You can consider the line-of-sight over time to form a ruled surface, like Hyperbolic paraboloid, and even a stationary convex object can be made to intersect that in two places.

It may be wandering a bit from the original question, but I think it interesting to ask whether more than two time intervals of intersection is possible for convex obstacles. My intuition says no for spheres.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3824
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Determining line of sight over time

I was thinking of defining a surface, a twisted1 trapezoid2, based upon the presumably straight line space-time motion of each bounding body on two opposing sides and the space-only difference3 as the two adjacents.

(And this, it seems, is exactly that hyperbolic paraboloid just mentioned. At least until you get to more complex versions of the problem with non-linear partner-trajectories. But that's beyond my understanding of what the OP states.)

Then see what points (or trajectories?) intersect that surface within those simple bounds. You could have quite complex trajectories (epicyclic or hyperbolic tracks) that, so long as they were definable by formulae that you could process, could indicate real roots upon the A0B0 to AtBt sweep. Or else be recalculated as distances from the plane at any given t, at a normal angle4 from which zero-crossing (absolute obscuring) ±r crossing (for an intermediate object of radius r, contact is gained/lost at these points) or just minima (signless, to establish points of closest approaches to investigate more fully, later).

It ends up just being a (more complicated) version of whether two line-segments intersect by simultaneous equations and line-end limiting, with as much or as little additional dimensionality added as necessary. So long as the end-trajectories and the obscuration-point trajectories can be sharply defined (so no totally chaotic motions, like the results of an N-body problem) on a Euclidean spacetime (though I'm sure it can be extended, I've already considered a relativity-skewed reference frame) then all the rest is just formula-crunching to derive the "what is the(/are the) intersect points" and "is(/are) the point(s) within the bounds" sufficient that you can encode it (or enact it) at will with the chosen boundary objects and each potential conjuctionee.

('Just'... You do have to fling about any number of formulaic conversions, e.g. generalised derivations, and it's possible it won't look pretty if you don't find an elegant short-cut along the way, but once you'd established that it works then it's not much more than numbers in and numbers out for any similar situations.)

1 Non-planar, unless end-points are always moving relative to one another in any direction other than towards/away from each other.
2 With (non-twisted?) parallelograms and rectangles being even more special cases, but not something worth betting upon.
3 Though interesting to imagine solving for 'simultaneity' in both directions by assessing the parallel solutions capped with separate time-like bounds, towards each. Logic dictates that object A might be obscured from seeing object B, though never vice-versa. Or, if so, by a different conjunction.
4 Far easier than looking for a normal upon the t-dimensioned curve, though that's possible too, to get other 'nearness' information such as a closest approach to conjunction being when x km and y minutes was the closest space-time approach..

Flumble
Yes Man
Posts: 2111
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Determining line of sight over time

Note that the OP did state that, when the points are stationary, the problem is trivial. (Well, the OP said "is it" instead of "it is", but I assume they meant the latter. ) And it is insinuated that the problem is not trivial when the points are moving.
I'll admit, I hadn't considered the scenario "all objects are permanent, bounded and have a constant non-zero speed, so at some point in time they must all be out of the way and therefore the problem is trivial only when the points are stationary", but in other cases the objects must be stationary for the first problem to be trivial and the second one hard, right?
As for the space, I agree it can be anything and the OP should specify (well, it needs enough structure to define a line of sight, like an ordered geometry). A vector space seems to be the most fun to elaborate on, though.

DavidSh wrote:
Flumble wrote:*since the line end points resp. the object has a constant velocity and the object is convex, the object can only intersect over one time interval, so you only have to look for a collision time from t=0 and t=1.

But consider the simple case in 1 dimension, where the obstacle is the interval [0,1], and endpoint A starts at -1, and moves to 4, and endpoint Z starts at 4, and moves to -1. The line intersects the obstacle for t<= 0.4, and for t >= 0.6. For 0.4 < t < 0.6 there is no intersection. It looks like in higher dimensions the possibility is there of two separate time intervals of intersection.

Hmph, you're absolutely right. And in higher dimensions you don't even need the end points to intersect with each other nor with any object:
Spoiler:

I don't know whether SAT-collision detection would allow you to easily find out the moment a collision ends. (and I haven't really given any thought to how a line segment "rotates" over time. A quick search shows that in CCD there's simply an iterative method to find the intersection time for two generic moving and rotating shapes. Better not use generic CCD then and actually parametrize the moving line and the object.)

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

jaap wrote:I guess so, because I never really thought of the objects as stationary.
Then I question your understanding of the problem.

I'll do it by example. You're back in school. Your math instructor has given you this problem on a test. Solve it.

You're in the asteroid belt.
The space is filled with objects.
Out there somewhere is your evil twin.
There are two points in a space.
Given just that information, tell me how to draw a line from you, to your evil twin, such that the line never hits any rocks.
How would I go about determining at what point in time, if any, the points would have line of sight to each other?

Later.

gmalivuk
GNU Terry Pratchett
Posts: 26566
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Determining line of sight over time

Yeah, it's not explicit but I agree that the objects are meant to be stationary and only the two points are moving.

The answer is only trivial if *everything* is stationary, points and objects alike. Then after acknowledging that, the OP only mentions the two points moving.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

I'm having some cognitive dissonance. Why is this problem reasonable? Or solvable, as posted? I assumed after a period of time the problem didn't give me enough information to do much of anything. It's trivial for some possibilities and impossible for others. Considering some recent posts I reasoned that this was spam or trolling. In either case I seem to be the only one who seems to believe that. So my apologies to the OP.

gmalivuk
GNU Terry Pratchett
Posts: 26566
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Determining line of sight over time

Oh I'm fairly confident it's either spam or someone who wants us to do their homework. But it's still a question with some interesting features to discuss, even if it's not solvable in general.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Derek
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Determining line of sight over time

morriswalters wrote:I'm having some cognitive dissonance. Why is this problem reasonable? Or solvable, as posted? I assumed after a period of time the problem didn't give me enough information to do much of anything. It's trivial for some possibilities and impossible for others. Considering some recent posts I reasoned that this was spam or trolling. In either case I seem to be the only one who seems to believe that. So my apologies to the OP.

This problem is solvable as long as the objects are sufficiently simple shapes. For example it's solvable with spheres, and probably with convex polyhedrons. Assume the two points are fixed, or make whatever adjustments are necessary to make them fixed. Then you need to find the times when each shape is tangent to the line between the two stationary points (for convex shapes, there are either two points of tangency or one, if there is one then just count it double). From this you can easily calculate when the points of line of sight to each other, and when they are occluded.

Some additional thoughts: Consider the line between the two points and the line of motion for an object. If we translate the line of motion onto the line of sight we can define a plane through the line of sight, which is also parallel to the line of motion. This plane may slice the moving object. If it does, the problem is reduced to 2 dimensions. If it does not, the object never occludes the line of sight.

DavidSh
Posts: 174
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Determining line of sight over time

The original case with two points, each moving at its own constant velocity, and stationary objects, is not equivalent to the case of two stationary points, and (rigid, non-rotating) objects moving at constant velocities. The length and direction of the line segment between the two points may vary in the first case, while they do not in the second.

Pay attention to the case in which the positions of the two points at t=0 and the positions of the two points at t=1, four positions in all, are not coplanar.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

@ Derek
I've spoilered my first response. If you don't see the point of this, then looking inside the spoiler would be a waste of time. A women died of starvation just off the Appalachian Trail after becoming disoriented when using the facilities. A extensive regional search failed to find her. Her body was discovered through random chance more than 2 years after she died. The trail is over a thousand miles long. Her location was less than two miles from the trail. Her problem was simpler than that of the OP's. To solve it she only had to intercept the trail at any point.

Spoiler:
I'm of the opinion that all of us have been manipulated by the OP, and if he ever comes back, I would love to ask him why I shouldn't believe that. Consider Flumble's observation and then apply the appropriate punctuation for either of those cases.

Mathematically you have answered this from a god's POV. Consider it from the POV of the points, given that you can only look one direction at a time, and that you were blindfolded before you started looking. Statistically this is like a coin just before you flip it. With no prior knowledge of previous flips.

The chances of seeing the other point is one divided by the number of places you have to look. And it doesn't matter if the points are moving or obstructed. That is statistical blindness. That is the OP's setup.

The question you are answering is regards to visibility. It's the way I answered initially. If you know where everything is at, then when can you see, what you can see? But it isn't what the OP asked.
cribbit wrote:How would I go about determining at what point in time, if any, the points would have line of sight to each other?

Consider if the second point is occluded. How do you test? By looking everywhere it could be. And if you don't see it, move one step and look everywhere again. Rinse and repeat.

Derek
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Determining line of sight over time

DavidSh wrote:The original case with two points, each moving at its own constant velocity, and stationary objects, is not equivalent to the case of two stationary points, and (rigid, non-rotating) objects moving at constant velocities. The length and direction of the line segment between the two points may vary in the first case, while they do not in the second.

Pay attention to the case in which the positions of the two points at t=0 and the positions of the two points at t=1, four positions in all, are not coplanar.

Hmm, somewhere in the thread I got mixed up and thought that the objects were moving and the points were stationary. I'm pretty sure it's still solvable for at least spheres. As long as you can parametrize the movement of the line of sight, then you can calculate at what times it will be tangent to a sphere (either fixed, or also moving along a parametric curve).

morriswalters wrote:@ Derek
I've spoilered my first response. If you don't see the point of this, then looking inside the spoiler would be a waste of time. A women died of starvation just off the Appalachian Trail after becoming disoriented when using the facilities. A extensive regional search failed to find her. Her body was discovered through random chance more than 2 years after she died. The trail is over a thousand miles long. Her location was less than two miles from the trail. Her problem was simpler than that of the OP's. To solve it she only had to intercept the trail at any point.

Spoiler:
I'm of the opinion that all of us have been manipulated by the OP, and if he ever comes back, I would love to ask him why I shouldn't believe that. Consider Flumble's observation and then apply the appropriate punctuation for either of those cases.

Mathematically you have answered this from a god's POV. Consider it from the POV of the points, given that you can only look one direction at a time, and that you were blindfolded before you started looking. Statistically this is like a coin just before you flip it. With no prior knowledge of previous flips.

The chances of seeing the other point is one divided by the number of places you have to look. And it doesn't matter if the points are moving or obstructed. That is statistical blindness. That is the OP's setup.

The question you are answering is regards to visibility. It's the way I answered initially. If you know where everything is at, then when can you see, what you can see? But it isn't what the OP asked.
cribbit wrote:How would I go about determining at what point in time, if any, the points would have line of sight to each other?

Consider if the second point is occluded. How do you test? By looking everywhere it could be. And if you don't see it, move one step and look everywhere again. Rinse and repeat.

I'm not really sure what any of this has to do with the problem. A hiker getting lost on the Appalachian Trail is not comparable to an abstract mathematical problem with perfect information. I also don't get why you're so antagonistic to OP. Ok, maybe he's asking us to do his homework, but nowhere has he promised that the problem has a solution or implied that he knows one, so I don't understand how you think we're being manipulated. I also don't see what Flumble's post has to do with being manipulated.

Your spoiler suggests a different and much more difficult problem then the one OP posed. I agree it's intractable to solve this from the point of view of a single point where you can only look in a single direction at a time. But that was never the problem that the OP posed. As originally posed, the problem is from a god's POV, as you put it.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

Derek wrote:I also don't get why you're so antagonistic to OP.
Given that the OP had posted once when he posted this, it isn't because I am in the position to hold any personal animus towards him. At any point in time he can come in and tell me why I'm an idiot. I've been shamed for being wrong before. And I warned you if you didn't accept my comparison to the graphic, that reading inside the spoiler was a waste.

Here's what he said, for the umpteenth time.
cribbit wrote:How would I go about determining at what point in time, if any, the points would have line of sight to each other?
Draw any line of your choice. Now convey the magnitude and direction of that line using one point. Good luck. For computer graphics John Carmack came up with his first engine in 1992 to solve exactly this general problem for games. Ray tracing solved it before that. In meat space radar was developed in the 1930's. Lidar whenever it became available.
Derek wrote:I agree it's intractable to solve this from the point of view of a single point where you can only look in a single direction at a time.
This is precisely what you propose when you suggest any technique that would let you draw line of sight. The line has magnitude and direction. Perhaps you know another way to draw a line of sight? If your interested then look at this.

So in your general solution, what accounts for his stated condition of " what point in time, if any, the points would have line of sight to each other?". Since that set a condition where the obstacles can occlude the line, how do you account for the general condition, always occluded? And I didn't set that condition, he did. Do you imagine that I would open myself up this way if I wasn't familiar with the problems nature? Bound the problem and it's solvable, if very computationally intensive. Pixar does it as a matter of course. Using render farms. You can rent them. Present an unbounded problem and you have worse odds than a theist hunting for Russell's Teapot.

Derek
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Determining line of sight over time

morriswalters wrote:Given that the OP had posted once when he posted this, it isn't because I am in the position to hold any personal animus towards him. At any point in time he can come in and tell me why I'm an idiot. I've been shamed for being wrong before. And I warned you if you didn't accept my comparison to the graphic, that reading inside the spoiler was a waste.

Why would the OP call you an idiot? The OP isn't posing a challenge trying to prove his superiority. He's posed an interesting problem that he hopes to find a solution for. This discussion should be collaborative, not antagonistic.

Draw any line of your choice. Now convey the magnitude and direction of that line using one point. Good luck. For computer graphics John Carmack came up with his first engine in 1992 to solve exactly this general problem for games. Ray tracing solved it before that. In meat space radar was developed in the 1930's. Lidar whenever it became available.

I've written a basic ray tracer, I know how it works. But that is to solve the point-to-everywhere problem, while the OP is trying to solve the point-to-point problem, albeit with moving points. This is a different problem.

This is precisely what you propose when you suggest any technique that would let you draw line of sight. The line has magnitude and direction. Perhaps you know another way to draw a line of sight? If your interested then look at this.

I was mistaken in my original post about the points being stationary, therefore having a single line of sight. That would make the problem much simpler. The problem is still solvable with moving points and sufficiently simple objects, I'm pretty sure, but now you have to parametrize the line of sight over time, essentially giving yourself a 2D surface embedded in 4D. Then you are looking for intersections of that surface with spheres. Significantly more complicated, but I think can still be solved exactly.

I am also making no claims to the efficiency of such a solution, only that I think it can be solved exactly.

Math sketch below:
Spoiler:
p1(t) = p1_0 + v1*t
p2(t) = p2_0 + v2*t

los(t, s) = p2(t)*s - p1(t)*(1 - s)

los(t, s) defines of the line of sight between p1 and p2 at time t.

Consider a sphere at stationary position p3 with radius r. To find a tangent point we use the formula for finding the minimum distance between a line and a point and then set this equal to r.

d1(t) = p3 - p1(t)
d2(t) = p2(t) - p1(t)

d(t) = d1(t) - proj(d1(t), d2(t))
|d(t)| = sqrt(d1(t)^2 - [d1(t)*d2(t)]^2/d2(t)^2) = r
d(t)^2 = d1(t)^2 - [d1(t)*d2(t)]^2/d2(t)^2 = r^2

d1(t)^2 - [d1(t)*d2(t)]^2 = r^2 * d2(t)^2

All vector multiplications are dot products of course. Now substitute the values for d1(t) and d2(t) and you should get a big ass polynomial in t of degree 2. Solve this and you will have the values of t for which the line of sight is tangent to the sphere. If there is one value of t, the sphere only ever becomes tangent to the line of sight but never fully obstructs it. If there are no real values of t then the sphere never obstructs the line of sight. Now this assumes a line of sight that is infinite in both directions, so for each t you will need to find the s in los(t, s) that minimizes |p3 - los(t, s)|, which is easy since it's just the projection of d1(t) onto d2(t):

los(t, s) = p2(t)*s - p1(t)*(1 - s) = p1(t) + proj(d1(t), d2(t))

After a bunch of messy substitutions again, this will be a linear equation in s. Now if s < 0 or s > 1, then the tangency point is not between p1(t) and p2(t) and therefore does not obstruct the line of sight. There are some edge cases to deal with however. If one value of t has s < 0 and the other value of t has s > 1, then at some point the sphere must have been between p1(t) and p2(t) and obstructed line of sight. The other case is if a point passes through a sphere in such a way that the center of the sphere is never between the points (s < 0 or s > 1), but the points would be occluded by the surface of the sphere anyways. This is easily checked by simply checking if either point is ever inside the sphere, which is done by finding |p3 - p1(t)| < r or |p3 - p2(t)| < r. This is a very simple operation, similar to when we checked for a tangent line of sight but with less variables. If such an overlap exists, the previous equations will give us the t values for the occlusion.

I believe this handles all edge cases. Some of my math may be wrong, but I don't think in any significant way. Thus we conclude that given two points, each moving linearly, and a stationary sphere, we can find the values t for which the sphere will occlude the line of sight between the two points, if ever. Solving for a collection of sphere is simply done by solving each sphere individually and taking the union of occlusions.

Future work: Extend solution to support spheres moving linearly. I believe this may be possible. Solve similar problem for stationary and moving triangles, if a solution for triangles exists, then a solution for any polyhedral figure exists.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

Derek wrote:Why would the OP call you an idiot? The OP isn't posing a challenge trying to prove his superiority. He's posed an interesting problem that he hopes to find a solution for. This discussion should be collaborative, not antagonistic.
Because I have implied he is being disingenuous. And if his purpose is pure then I would be an ass. And he would be right to feel that way. This is the second example of this type of problem I have seen lately.
Derek wrote:I've written a basic ray tracer, I know how it works. But that is to solve the point-to-everywhere problem, while the OP is trying to solve the point-to-point problem, albeit with moving points. This is a different problem.
Absent initial conditions they are one and the same. A ray trace to one point is exactly the problem. The underlying assumption is that it's the only place you have to look. If you don't know where that point is at the moment you start to look implies that you have to look everywhere until you see it. It's why ray tracing isn't used more in day to day animations. Modern game graphics is about finding ways of short cutting the process by defining the things that can't be seen, in advance of ray tracing.

In addition at the instant you trace you have to test the intersection in that same instant, it can't move while you are looking at it. So you test discrete points. Each one is a snapshot of a moving event. It's why high speed video can show you images that your eye can't see.
Derek wrote:I was mistaken in my original post about the points being stationary, therefore having a single line of sight. That would make the problem much simpler. The problem is still solvable with moving points and sufficiently simple objects, I'm pretty sure, but now you have to parametrize the line of sight over time, essentially giving yourself a 2D surface embedded in 4D. Then you are looking for intersections of that surface with spheres. Significantly more complicated, but I think can still be solved exactly.

I am also making no claims to the efficiency of such a solution, only that I think it can be solved exactly.
Give me the path for each point stated as a vector and fix all the objects and define the view port size, and I'll tell you where you will be able to see it, with the error never greater than the uncertainty about the geometry of the objects . Give me their starting points and time in flight and I can tell you when they will pass. Have them moving faster than I can test and none of it matters.

The problem is that there are an infinite number of possible solutions if you don't set initial conditions. It isn't that your solution doesn't work. The OP gave you an indeterminate problem.
Indeterminate problem
(Math.) a problem which admits of an infinite number of solutions, or one in which there are fewer imposed conditions than there are unknown or required results.
- Gray.

DavidSh
Posts: 174
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Determining line of sight over time

Derek's last described method is about how I would go about defining and solving the problem. I think the polynomial that you need to find the zeros for is of degree 4 -- it isn't hard to generate an instance where there are four separate times when the lines-of-sight between the two moving points are tangent to the single spherical obstacle, but maybe Derek has some way of generating these four times out of the two zeros of a degree 2 polynomial.

Derek
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Determining line of sight over time

Morris, I don't know why you're stuck on the idea of trying to find a hidden point. I think the OP was fairly clear that the position and velocity of every point and object is known beforehand. This is the only way to make the problem tractable. If we make this reasonable assumption then the problem isn't indeterminate, it just has variables.

DavidSh wrote:Derek's last described method is about how I would go we about defining and solving the problem. I think the polynomial that you need to find the zeros for is of degree 4 -- it isn't hard to generate an instance where there are four separate times when the lines-of-sight between the two moving points are tangent to the single spherical obstacle, but maybe Derek has some way of generating these four times out of the two zeros of a degree 2 polynomial.

You're right, it's degree 4. I missed that when looking at my equation, but [d1(t)*d2(t)]^2 is degree 4. The rest of my analysis is easily corrected for this fact.

Still solvable algebraically!

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

Derek wrote:Morris, I don't know why you're stuck on the idea of trying to find a hidden point. I think the OP was fairly clear that the position and velocity of every point and object is known beforehand.
Ok, show me that. As an alternative formulation, quit asking about why I think anything, attack my math. Anything else is an ad hominem. It's that simple.

He certainly didn't say anything like, "assume we know the equation of the line for both points" followed some condition for the objects, like "we have objects of uniform size distributed in space with the distribution defined in some way." .

Or alternatively, "We have a well defined system."

I can assume as well as you. For instance I can assume the that the solution is such the the two lines are equal in both magnitude and direction, thus always being superimposed and always visible. Irregardless of the nature of the equation of the line or the geometric nature of the objects.

As in xa=xa Where a lies on the real number line.

To draw the intersecting line otherwise requires the solution to two simultaneous linear equations at a point.

axg+byg+czg=d
exg+fyg+gzg=h

My 10th grade teacher swore that these weren't directly solvable at a point. He used the word indeterminate. Which I took to mean that there are an infinite number of solutions that can satisfy the condition.

As a bonus question, share with me why it makes a difference the the motion is linear versus curvilinear in terms of solvability? That would tell me why it is lucky we are talking about straight lines since I have never had a problem in school that involved luck in this context.

Barring some other input from the OP to clarify, and due to the construction of the problem as written by the OP, my default position is that the OP's point was to prime you to believe something he implied but never said. He did it thus.

If both points are stationary is it trivial to determine whether or not they can see each other. ?
Flumble pointed out that he assumed the OP meant it is rather than is it.
That assumption leads you to answer the question by assuming it is trivial. The firsts states it's trivial, the second asks if it is. That is, it is, is declarative, is it, is interrogatory. I agree that it is probably a homework assignment. The only question in my mind is what is the nature of the homework?

Since I can't answer my own question, I'll speculate. Suppose I suggested that the problem was defined to demonstrate how two people, confronted with exactly the same facts, can construe them in two different ways. And that how you perceive the problem, will be influenced by the way the question is asked. The effect is called priming.

This is why I used the term cognitive dissonance. Had I not just had an argument where, after a hundred or so iterations, I demonstrated why Russell's Teapot will never be found. I would be sitting on a fence cheering you on and feeling a gee whiz moment.

Derek
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Determining line of sight over time

morriswalters wrote:He certainly didn't say anything like, "assume we know the equation of the line for both points" followed some condition for the objects, like "we have objects of uniform size distributed in space with the distribution defined in some way."

While I suppose he never said that we know the initial positions and velocity of the points and objects, I think it's pretty well implied by the fact that he didn't say these were unknown, didn't say anything about trying to find the other object (only trying to determine when line of sight exists), and the fact that the problem is obviously intractable if we do not know the initial states and have to search for the points, but tractable and interesting if we do. You seem to be the only person in the thread assuming that the points do not have known initial conditions. And I mean, that's a problem we can discuss, but I don't think it's interesting to discuss and I don't think it's what the OP wanted to discuss.

To draw the intersecting line otherwise requires the solution to two simultaneous linear equations at a point.

axg+byg+czg=d
exg+fyg+gzg=h

Can you explain where these equations came from? Do they represent the motion of the points? The line of sight? I'm particularly confused by the power of g.

My 10th grade teacher swore that these weren't directly solvable at a point. He used the word indeterminate. Which I took to mean that there are an infinite number of solutions that can satisfy the condition.

Without understanding what the equations represent, I can't say whether they are indeterminate or not, but an infinite number of solutions is still a solution. Saying "the points can always see each other" or "the points can never see each other" is a valid answer to the OP's question (for some initial conditions).

As a bonus question, share with me why it makes a difference the the motion is linear versus curvilinear in terms of solvability? That would tell me why it is lucky we are talking about straight lines since I have never had a problem in school that involved luck in this context.

Because linear motion is easy to compute and results in easier equations. If the motion of the points was parabolic instead of linear, the equation I posted above would be degree 8 instead of degree 4, becoming much more difficult to solve (and probably not solvable algebraically, the OP didn't ask specifically for an algebraic solution but it would be nice). Other kinds of motion may also be easy and solvable though, I don't know, but I know that linear motion is solvable.

Barring some other input from the OP to clarify, and due to the construction of the problem as written by the OP, my default position is that the OP's point was to prime you to believe something he implied but never said. He did it thus.

If both points are stationary is it trivial to determine whether or not they can see each other. ?
Flumble pointed out that he assumed the OP meant it is rather than is it.
That assumption leads you to answer the question by assuming it is trivial. The firsts states it's trivial, the second asks if it is. That is, it is, is declarative, is it, is interrogatory. I agree that it is probably a homework assignment. The only question in my mind is what is the nature of the homework?

Since I can't answer my own question, I'll speculate. Suppose I suggested that the problem was defined to demonstrate how two people, confronted with exactly the same facts, can construe them in two different ways. And that how you perceive the problem, will be influenced by the way the question is asked. The effect is called priming.

This is why I used the term cognitive dissonance. Had I not just had an argument where, after a hundred or so iterations, I demonstrated why Russell's Teapot will never be found. I would be sitting on a fence cheering you on and feeling a gee whiz moment.

Perhaps, but I'm going to apply Hanlon's Razor and assume that that was a typo, not some scheme to spark a metadiscussion on the meaning of the OP.

Derek wrote:Future work: Extend solution to support spheres moving linearly.

I now realize that this is trivial. Given a moving sphere, we can transform the velocity of the points such that the sphere is now stationary and only the points are moving. Then the moving sphere case reduces to the stationary sphere case which I discussed above.

morriswalters
Posts: 7073
Joined: Thu Jun 03, 2010 12:21 am UTC

### Re: Determining line of sight over time

Derek wrote:While I suppose he never said that we know the initial positions and velocity of the points and objects, I think it's pretty well implied by the fact that he didn't say these were unknown, didn't say anything about trying to find the other object (only trying to determine when line of sight exists), and the fact that the problem is obviously intractable if we do not know the initial states and have to search for the points, but tractable and interesting if we do. You seem to be the only person in the thread assuming that the points do not have known initial conditions. And I mean, that's a problem we can discuss, but I don't think it's interesting to discuss and I don't think it's what the OP wanted to discuss.
Spoiler:
He didn't say much of anything. And I recognize that you find it interesting and I'm the only one who seems to see this. And we have been discussing it. And I haven't had to assume anything to arrive at my conclusion. Except to his motivation for asking the question, which is opinion.

In the case you are confused about, g would represent the real numbers. In the the linear form, g=1 would represent all possible vectors about the center presented by the constants. By symmetry therefore, all lines about the center. I held g constant because the geometry is difficult in higher dimensions. I'm good up until g=2. Maybe. I can't begin to picture the surfaces except as rotation of the lines around the axis at the various translations in two space. The truer sense is the vectors are drawing a surface, point by point, as they move.

This implies, I believe(I'm outside my comfort zone by a large margin), that there are multiple non unique solutions containing x,y, and z equal to any value. So for the constants a, b, and c, there are infinite vectors different only by the constants. The solution is indeterminate. You can solve x as it relates to y or y as it relates to x. But you can't solve x+y=c There are multiple unique answers.

You had trouble understanding it because I didn't bound g. You can solve for a unique solution by identifying a point that that is the same in both equations. Thus the second equation. Although there should have been three since I stated it in 3 space. My apologies. I believe that represents an intersection of the two lines in 2 space and 3 lines in 3 space.

I have probably botched what I am trying to say. I haven't used this math for more than thirty years. But if I have reasoned correctly, your problem, while interesting, has an infinite number of points, for which your values of of x,y, and, z, there exists another interesting problem very close to yours, which looks exactly like your interesting problem.
Edit
I've spoilered everything else because on rereading I discover that this makes the point better than my crappy math can do it.

I don't try to guess what people want when they ask a question. I answer the question that they ask. I'm not a mind reader. If I need clarification I ask. In particular, and for me the most bothersome, is that you picked your point by assuming you could see the other point when you did your setup. So you were able to start to look without without first testing if you could see. In effect you said I can see x, and if I can see x than I need only look for the point where I can no longer see x, rather than the more difficult question of, can I see x, and if I can't, what do I do next?

Spoiler:
It would seem to me to be reasonable, that if he wanted to study the issue he would have bounded it so that he could have related his purpose clearly. The general case you are solving is called well defined. And if he can understand the problem, and the solution, it is at least plausible that he would have understood that bounding it that way meant exactly what you have assumed. I am left no other conclusion, then that he chose not to bound it purposely. Rather than the alternative where he didn't know how to. I don't expect you to either attack or defend that, its opinion and irrelevant. But you did ask why.

You now have seen the sum total of my pitiful math skills.