What is the point at this!

December 5, 2012 2:23 PM

Here’s a simple computational geometry problem. I am trying to figure out the value at an point of two line segments based off of the values at both of one of the segment’s endpoints. The problem is that I don’t exactly know the best way of going about finding the value at one of those points. Here is a reference figure. Given values (X_C, YC) = F_C (X_D, YD) = F_D How can I calculate the value of F_E, where F_E = (X_E, Y_E), where E is the point on the segment CD, where CD intersects with the line AB? (Extraneous details inside)

For those who care for some context, I have a hurricane track that is split into segments. One of these segments overlaps a line that is used for extracting hurricane characteristics for a given storm to give to an storm forecasting interpolator. Since I only have exact values of some of those characteristics at either side of the intersecting segment, I need to find an estimate for the value at the intersection point based off of the distance between the points at either side of the intersecting segment.

If you could walk me through your steps, that would be fantastic. I never took geometry in high school. :)

posted by oceanjesse to science & nature (10 answers total)

Wikipedia: Line-line intersection
posted by stebulus at 2:36 PM on December 5, 2012

It's unclear exactly what your question is.

1) If you are asking what the formula is for the intersection of two line segments. This requires you to have the coordinates of 'A' and 'B'.

2) If the line AB is the track of hurricane and you don't know the coordinates of A and B, you would need info like, say, the speed of the hurricane and the direction the hurricane is heading.

Note, if you are solving 1) you need to keep account of the scenarios where the two line segments don't intersect.

Honestly, 1) is high school geometry. It's something you probably can figure out if you are doing all of these other technical things. It seems like you need to think more clearly about what the mathematical problem you are solving actually is...
posted by ennui.bz at 2:36 PM on December 5, 2012

What you want to do is interpolation: Based on the values at the endpoints, you want to find the value somewhere in between.

The simplest thing you can do is linear interpolation. You guess that the value changes linearly as you move from C to D. Then if E is located (say) 64% of the way from C to D, you would assume that the value is also 64% of the way from F_C to F_D. Or in an equation:

F_E = (F_C + F_D) * length(CE)/length(CD)

(You can think of this as a weighted average. For example, as a special case, notice that if E is exactly halfway between C and D, then F_E is just the average of F_C and F_D.)

If you had more than two known values you could do other types of interpolation that give smoother results around transitions, but with just two values this is probably the best approximation you'll get.
posted by mbrubeck at 2:38 PM on December 5, 2012

I'm having trouble following the explanation and notation, but are you saying you have values f(A) and f(B) (say those are temperatures) and you want to estimate f(E), the temperature at the point of intersection with another line segment?

The general term for this is interpolation, and the simplest way if you have no other information is linear interpolation: f(E) = f(A) + (f(B) - f(A)) * len(AE) / len(AB).

Other methods of interpolation can be more appropriate for different kinds of data and tasks.
posted by jjwiseman at 2:39 PM on December 5, 2012

Aha, thinking of it in terms of segment length is totally what I need to do. I was getting hung up on delta x, delta y, but it's totally simpler to keep things flat and just worry about three points on one line.

Thanks everyone!
posted by oceanjesse at 2:47 PM on December 5, 2012

In case stebulus's suggestion is a little dense, line-line intersection with high school algebra (and this might help you with your "dx, dy" understanding:

Given line segments CD and AB, you can decompose the two lines into a point, (Cx,Cy) and (Ax,Ay), and a direction (Dx-Cx, Dy-Cy) and (Bx-Ax, By-Cy).

You can then "parameterize" each of these lines with a point along the line from 0 to 1. Let's call one of the "U" and the other "V".

So if we set up equations for a hypothetical point where these lines intersect, it might look like:

Cx+U*(Dx-Cx) = Ax+V(Bx-Ax)
Cy+U*(Dy-Cy) = Ay+V(By-Ay)


You can see that on the left side of these equations, if U is 0 you get C, if U is 1 you get D, and on the right side if V is zero you get A, and if V is 1 you get B. If, U and V are between 0 and 1, you have an intersection. If you divide by zero when trying to solve, the lines are parallel.
posted by straw at 2:50 PM on December 5, 2012

Do you need to do this a lot? If so, let me suggest a linear-algebraic approach, which (if you have access to technology), may generalize better. This is essentially the approach suggested by straw above.

(1) parametrize the line from A to B as f(t) = (1-t)*A + t*B, where A = (ax, ay) and B = (bx, by) are both vectors (think of them as ordered pairs. This parameterization is a function of t (so, as t varies, different points on the line are drawn), and when t = 0, you're at A, and when t = 1, you're at B.

(2) Similarly, parametrize the line from C to D as g(s) = (1-s)*C + s*D. I'm using a different parameter to make clear that there is no relationship between s and t.

We want to know where these two parametric functions intersect; that is, we want to solve the vector equation (1-t)*A + t*B = (1-s)*C + s*D for (t, s); the value of t that we get is the value of the parameter needed to get to the intersection point P travelling along the line f(t) (that is, beginning at A and going to B), and the value of s you get is the value of the parameter needed to get to P travelling along the other line g(s).

The corresponding system of equations, after you kick everything involving a parameter to one side and all the constants to the other side, is (B-A)t + (C-D)s = (C-A), or as a system of two equations in two unknowns,

(Bx - Ax) t + (Cx-Dx) s = Cx - Ax
(By-Ay)t + (Cy - Dy) s = Cy - Ay.

One approach is to slam everything into a matrix and row reduce:

[ (Bx - Ax), (Cx - Dx), Cx - Ax] [1, 0, tAns]
[(By - Ay), (Cy - Dy), Cy - Ay)] --->[0, 1, sAns]

If you end up with the thing on the right-hand side (with the 1s and 0s), then the thing in the tAns slot tells you how far along the first line from A you have to travel to get to the intersection point, and f(tAns) actually gives you the coordinates, and likewise for sAns and the other segment. (If you don't end up with the thing on the RHS, then your lines don't intersect transversally like you want.)

The advantage to this is that the orientation of the points doesn't matter (i.e., no worry about undefined slope = vertical lines).

And hey, I can do this row-reduction in general (it's ugly):
t = (-Ay Cx+Dy Cx+Ax Cy+Ay Dx-Cy Dx-Ax Dy)/(-Ay Cx+By Cx+Ax Cy-Bx Cy+Ay Dx-By Dx-Ax Dy+Bx Dy)
and plug that into (1-t)*(Ax, Ay) + t*(Bx, By) to get the coordinates.

One more advantage: this is answering the question for infinite lines. If you need the answer to be in the interior of the segments, you simply look to see if tAns is between 0 and 1 to see if the intersection is in the interior of AB (i.e., in the segment rather than the extended line), and if sAns is between 0 and 1 to see if it's in the interior of CD.


(On looking back at your original question, it looks like your diagram---which is what I was discussing---doesn't quite match your question, where C and D are determined by A and B. So if you don't really care about the intersection of line segments and want to know the answer to some other question, try rephrasing.)
posted by leahwrenn at 3:14 PM on December 5, 2012 [1 favorite]

Sorry, I should have said that I have values for (X_C, Y_C), F_C, (X_D, Y_D), F_D, and (X_E, Y_E).

I just needed help figuring out how best to find a value of F_E from just those values.

I’m going to write a function to do this in Matlab. I already wrote a function to find the intersection, so that’s why I have (X_E, Y_E).

Does that clarify the original question?
posted by oceanjesse at 3:18 PM on December 5, 2012

It sounds like you are trying to interpolate the function f at some point E on the line CD, where you know f(C) and f(D). Assuming that's true, you want to set up the problem like leahwrenn described, and solve for s. Then, if you want to use linear interpolation, f(E) = (1-s) f(C) + s f(D).

If you already have Cx, Dx, and Ex through some other method, then

Ex = (1-s) Cx + s Dx ,

so you can find s by

s = (Ex - Cx ) / (Dx - Cx) .

If Cx = Dx, or if they are extremely close, then use Cy, Dy, and Ey instead.
posted by Serf at 11:08 PM on December 5, 2012

Serf -> that was the last piece in the puzzle. Thanks so much!
posted by oceanjesse at 2:24 PM on December 8, 2012