Determining line of sight over time
Moderators: gmalivuk, Moderators General, Prelates
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?
How would I go about determining at what point in time, if any, the points would have line of sight to each other?
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?
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: 5268
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 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 lineofsight 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)))
Re: Determining line of sight over time
You should be able to fairly trivially write a timevarying 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.
The problem doesn't actually change that much depending on whether the objects are stationary or not, I don't think.

 Posts: 7073
 Joined: Thu Jun 03, 2010 12:21 am UTC
Re: Determining line of sight over time
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.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?
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
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.
Re: Determining line of sight over time
morriswalters wrote:What am I missing? The question being asked, at least to me is, How far can you see.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?
[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.

 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?
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.
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 linesegmentcircle or linesegmentsphere 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 linesegmentsnowflake 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 lineofsight. (or take the intersection of all time intervals when the lineofsight is not blocked, same thing)
*since the
Re: Determining line of sight over time
Flumble wrote:*since thelineend 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 spacetime 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.

 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.
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.
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 thelineend 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 1d involves the observers passing through an object. If you allow that in 3d, too, then you definitely get the same thing there.
But I think you are right, even in 2d. You can consider the lineofsight 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.
Re: Determining line of sight over time
jaap wrote:In 1d involves the observers passing through an object. If you allow that in 3d, too, then you definitely get the same thing there.
But I think you are right, even in 2d. You can consider the lineofsight 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: 2963
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Determining line of sight over time
I was thinking of defining a surface, a twisted^{1} trapezoid^{2}, based upon the presumably straight line spacetime motion of each bounding body on two opposing sides and the spaceonly difference^{3} 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 nonlinear partnertrajectories. 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 A_{0}B_{0} to A_{t}B_{t} sweep. Or else be recalculated as distances from the plane at any given t, at a normal angle^{4} from which zerocrossing (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 linesegments intersect by simultaneous equations and lineend limiting, with as much or as little additional dimensionality added as necessary. So long as the endtrajectories and the obscurationpoint trajectories can be sharply defined (so no totally chaotic motions, like the results of an Nbody problem) on a Euclidean spacetime (though I'm sure it can be extended, I've already considered a relativityskewed reference frame) then all the rest is just formulacrunching 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 shortcut 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} Nonplanar, unless endpoints are always moving relative to one another in any direction other than towards/away from each other.
^{2} With (nontwisted?) 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 timelike bounds, towards each. Logic dictates that object A might be obscured from seeing object B, though never viceversa. Or, if so, by a different conjunction.
^{4} Far easier than looking for a normal upon the tdimensioned 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 spacetime approach..
(And this, it seems, is exactly that hyperbolic paraboloid just mentioned. At least until you get to more complex versions of the problem with nonlinear partnertrajectories. 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 A_{0}B_{0} to A_{t}B_{t} sweep. Or else be recalculated as distances from the plane at any given t, at a normal angle^{4} from which zerocrossing (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 linesegments intersect by simultaneous equations and lineend limiting, with as much or as little additional dimensionality added as necessary. So long as the endtrajectories and the obscurationpoint trajectories can be sharply defined (so no totally chaotic motions, like the results of an Nbody problem) on a Euclidean spacetime (though I'm sure it can be extended, I've already considered a relativityskewed reference frame) then all the rest is just formulacrunching 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 shortcut 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} Nonplanar, unless endpoints are always moving relative to one another in any direction other than towards/away from each other.
^{2} With (nontwisted?) 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 timelike bounds, towards each. Logic dictates that object A might be obscured from seeing object B, though never viceversa. Or, if so, by a different conjunction.
^{4} Far easier than looking for a normal upon the tdimensioned 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 spacetime approach..
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 nonzero 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.
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:
I don't know whether SATcollision 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.)
I'll admit, I hadn't considered the scenario "all objects are permanent, bounded and have a constant nonzero 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 thelineend 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 SATcollision 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.)

 Posts: 7073
 Joined: Thu Jun 03, 2010 12:21 am UTC
Re: Determining line of sight over time
Then I question your understanding of the problem.jaap wrote:I guess so, because I never really thought of the objects as stationary.
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.
Out there somewhere is your evil twin.The space is filled with objects.
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.There are two points in a space.
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: 26035
 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.
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.

 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: 26035
 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.
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.
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, nonrotating) 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.
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.

 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.
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:
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, nonrotating) 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 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.

 Posts: 7073
 Joined: Thu Jun 03, 2010 12:21 am UTC
Re: Determining line of sight over time
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.Derek wrote:I also don't get why you're so antagonistic to OP.
Here's what he said, for the umpteenth time.
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.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 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.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.
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.
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 pointtoeverywhere problem, while the OP is trying to solve the pointtopoint 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:

 Posts: 7073
 Joined: Thu Jun 03, 2010 12:21 am UTC
Re: Determining line of sight over time
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: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.
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.Derek wrote:I've written a basic ray tracer, I know how it works. But that is to solve the pointtoeverywhere problem, while the OP is trying to solve the pointtopoint problem, albeit with moving points. This is a different problem.
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.
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.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.
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.
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 linesofsight 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.
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.
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!
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 linesofsight 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!

 Posts: 7073
 Joined: Thu Jun 03, 2010 12:21 am UTC
Re: Determining line of sight over time
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.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.
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 x^{a}=x^{a} 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.
ax^{g}+by^{g}+cz^{g}=d
ex^{g}+fy^{g}+gz^{g}=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.
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.
ax^{g}+by^{g}+cz^{g}=d
ex^{g}+fy^{g}+gz^{g}=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.

 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:
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:
Who is online
Users browsing this forum: No registered users and 6 guests