- #1
ScottB
- 4
- 0
0. Background
I am a Doctoral student studying Geographic Information Science. I do a good bit of programming during the course of my work. Recently, I happened upon a problem which I cannot solve on my own (my post-calc math comfort zone is mostly in procedure and repetition, not in formulating new approaches to unseen problems; also, I've forgotten important bits of it). This problem arose as I was working on a statistical analysis package for spatial data.
I am a first time reader and poster, and apologize in advance for any faux pas I may commit out of ignorance.
The statistical software component I am developing needs to calculate the distance between two line segments. Not the absolute distance, as that is trivial. In these data, the x and y dimensions represent space and the z dimension is time (t). The distance must be in terms of space, not of time, meaning that for any point (x,y,t) on the first line distance can only be measured to a single point (x2,y2,t) on the second line (obviously where t=t).
None given that I didn't derive myself; as I mentioned, this is not a homework problem per say, but rather a problem encountered in the course of separate research.
I've taken enough calculus to know that there lies a solution therein. I can, in theory, derive two parabolas on a 2d plane whose distance corresponds to the distance between the two line segments, and then break out a little calculus and solve it. There are two problems with this approach. First, I don't know how to form a translation that will stretch a curved plane (between two skew lines, i think its what they're called) and flatten it while maintaining its properties (thereby translating the two straight line segments into parabolas). I don't even have the correct math vocabulary to explain that understandably. Second, calculus rarely translates well into a computing environment, so that's a dead end I fear.
I'm hoping there is a linear algebra / matrix-related solution to my problem.
In my pursuit of this I have formulated the problem as follows:
I start with four points in 3-space:
(Fx(t0), Fy(t0), t0),
(Fx(t2), Fy(t2), t2),
(Gx(t1), Gy(t1), t1),
(Gx(t3), Gy(t3), t3),
where
t0 <= t1 < t2 <= t3
and
Fx(t) = Afx t + Bfx for t in (t0, t2)
Fy(t) = Afy t + Bfy for t in (t0, t2)
Gx(t) = Agx t + Bgx for t in (t1, t3)
Gy(t) = Agy t + Bgy for t in (t1, t3)
where Afx, Bfx, Afy, Bfy, Agx, Bgx, Agy and Bgy are constants.
Minimize ( (Fx(t) - Gx(t))2 + (Fy(t) - Gy(t))2 )0.5 over t in (t1, t2)
To explain this, I have 'projected' the two line segments onto the x,t and y,t planes, and derived a general expression for each as a function of t. But now that I have my fancy formulation, I haven't the faintest idea where to go from here. Even a keyword would help me, as I am (obviously) deficient in appropriate math vocabulary.
Anyway, I greatly appreciate any help or suggestions I can get; thanks in advance!
- Scott
I am a Doctoral student studying Geographic Information Science. I do a good bit of programming during the course of my work. Recently, I happened upon a problem which I cannot solve on my own (my post-calc math comfort zone is mostly in procedure and repetition, not in formulating new approaches to unseen problems; also, I've forgotten important bits of it). This problem arose as I was working on a statistical analysis package for spatial data.
I am a first time reader and poster, and apologize in advance for any faux pas I may commit out of ignorance.
Homework Statement
The statistical software component I am developing needs to calculate the distance between two line segments. Not the absolute distance, as that is trivial. In these data, the x and y dimensions represent space and the z dimension is time (t). The distance must be in terms of space, not of time, meaning that for any point (x,y,t) on the first line distance can only be measured to a single point (x2,y2,t) on the second line (obviously where t=t).
Homework Equations
None given that I didn't derive myself; as I mentioned, this is not a homework problem per say, but rather a problem encountered in the course of separate research.
The Attempt at a Solution
I've taken enough calculus to know that there lies a solution therein. I can, in theory, derive two parabolas on a 2d plane whose distance corresponds to the distance between the two line segments, and then break out a little calculus and solve it. There are two problems with this approach. First, I don't know how to form a translation that will stretch a curved plane (between two skew lines, i think its what they're called) and flatten it while maintaining its properties (thereby translating the two straight line segments into parabolas). I don't even have the correct math vocabulary to explain that understandably. Second, calculus rarely translates well into a computing environment, so that's a dead end I fear.
I'm hoping there is a linear algebra / matrix-related solution to my problem.
In my pursuit of this I have formulated the problem as follows:
I start with four points in 3-space:
(Fx(t0), Fy(t0), t0),
(Fx(t2), Fy(t2), t2),
(Gx(t1), Gy(t1), t1),
(Gx(t3), Gy(t3), t3),
where
t0 <= t1 < t2 <= t3
and
Fx(t) = Afx t + Bfx for t in (t0, t2)
Fy(t) = Afy t + Bfy for t in (t0, t2)
Gx(t) = Agx t + Bgx for t in (t1, t3)
Gy(t) = Agy t + Bgy for t in (t1, t3)
where Afx, Bfx, Afy, Bfy, Agx, Bgx, Agy and Bgy are constants.
Minimize ( (Fx(t) - Gx(t))2 + (Fy(t) - Gy(t))2 )0.5 over t in (t1, t2)
To explain this, I have 'projected' the two line segments onto the x,t and y,t planes, and derived a general expression for each as a function of t. But now that I have my fancy formulation, I haven't the faintest idea where to go from here. Even a keyword would help me, as I am (obviously) deficient in appropriate math vocabulary.
Anyway, I greatly appreciate any help or suggestions I can get; thanks in advance!
- Scott
Last edited: