Finding Collinear Points Given 1 point and 2 lines

[Helpme21]

Hello -

I need help finding collinear points:

Given:
Equations of 2 lines, L1 and L2
1 points, P3

Want to find points P1 and P2 that lie on L1 and L2 respectively that are collinear to P3. I know that there can be multiple combinations of points P1 and P2 so to narrow down the list to just one set, I want to minimize the distance between P1 and P2.

I'm trying to program this into an excel macro, so the method which would take the least computation time would be great.

Thanks in advance!

 

[bossman27]

Hmm, are L1 and L2 parallel? Because if they aren't, the shortest distance between P1 and P2 will always be 0, when P1 and P2 both lie at the intersection point. Of course, this would satisfy collinearity because they would all lie on the line between the intersection and P3.

If they are parallel, then the shortest distance will be given by placing P1 and P2 at the intersections of L1 and L2 with a line through P3 that has a slope perpendicular to L1 and L2.

I'm just going of the top of my head here, so let me know if I'm missing something...

 

[Helpme21]

Hmm, are L1 and L2 parallel? Because if they aren't, the shortest distance between P1 and P2 will always be 0, when P1 and P2 both lie at the intersection point. Of course, this would satisfy collinearity because they would all lie on the line between the intersection and P3.

If they are parallel, then the shortest distance will be given by placing P1 and P2 at the intersections of L1 and L2 with a line through P3 that has a slope perpendicular to L1 and L2.

I'm just going of the top of my head here, so let me know if I'm missing something...

L1 and L2 are not parallel, but that is a good point you bring up with the intersection point. I want the shortest distance between P1 and P2 that does not include the intersection point between L1 and L2.

 

[Norwegian]

L1 and L2 are not parallel, but that is a good point you bring up with the intersection point. I want the shortest distance between P1 and P2 that does not include the intersection point between L1 and L2.

So you want the shortest possible distance that is greater than zero??

Btw, are you sure you are talking about points and lines in the plane? If it all happened in 3-dimensional space, you actually have a meaningful question with a unique answer in the general case.

 

[Helpme21]

So you want the shortest possible distance that is greater than zero??

Btw, are you sure you are talking about points and lines in the plane? If it all happened in 3-dimensional space, you actually have a meaningful question with a unique answer in the general case.

Yes, shortest distance greater than zero.

This is all in a 2-D plane. How is there more than one answer to the question? I think I've constrained it enough that there is only one answer.

 

[Norwegian]

Yes, shortest distance greater than zero.

OK, thought so, no further questions.

 

[Helpme21]

OK, thought so, no further questions.

To further Clarify:

L1 has a range of values (x1,y1) to (x2,y2)
L2 has a range of values (x3,y3) to (x4,y4)

The points P1 and P2 have to fall into the range of their respective lines and the range does not contain the intersection of L1 and L2.

 

[jbriggs444]

To further Clarify:

L1 has a range of values (x1,y1) to (x2,y2)
L2 has a range of values (x3,y3) to (x4,y4)

The points P1 and P2 have to fall into the range of their respective lines and the range does not contain the intersection of L1 and L2.

With that clarification it seems clear that the shortest distance cannot be from a point in the interior of the one line segment to a point in the interior of the other line segment except in the boundary case where the two line segments are parallel.

The shortest distance must be achieved from an endpoint on the one line segment to an endpoint on the other line segment or from an endpoint on one line segment to an interiior point on the other line segment.

I count eight cases to examine to determine the minimum distance.

 

[Norwegian]

To further Clarify:

L1 has a range of values (x1,y1) to (x2,y2)
L2 has a range of values (x3,y3) to (x4,y4)

The points P1 and P2 have to fall into the range of their respective lines and the range does not contain the intersection of L1 and L2.

OK, so the game has changed somewhat, and we are now talking about line segments, and not lines. I have two observations:

1) In most cases, there are no such P1 and P2 collinear with P3.

2) When such P1 and P2 do exist, they may very well be interior points, so what jbriggs say above is just wrong.

 

[Helpme21]

OK, so the game has changed somewhat, and we are now talking about line segments, and not lines. I have two observations:

1) In most cases, there are no such P1 and P2 collinear with P3.

2) When such P1 and P2 do exist, they may very well be interior points, so what jbriggs say above is just wrong.

I agree with you statements. What would be the best way to determine what the Points P1 and P2 are if they exist?

 

[bossman27]

I agree with you statements. What would be the best way to determine what the Points P1 and P2 are if they exist?

Ahh, this is much more interesting now that we have segments, not lines. First of all, are there any assumptions about the segments here? Are they sure to not intersect? Are we assuming that the problem can be solved, or do we need to determine whether such colinear points exist first?

 

[bossman27]

Also, are the endpoints given in a particular order: i.e. L1 (a,b) to (c,d) where a<c and b<d, or something like that? The format of your input/spreadsheet, and any assumptions given would help determine the best computational route.

Edit: Finally, just to clarify, you want to find points with the shortest distance between P1 and P2... NOT with the shortest line segment connecting P1, P2 and P3, correct?

 

[Helpme21]

Ahh, this is much more interesting now that we have segments, not lines. First of all, are there any assumptions about the segments here? Are they sure to not intersect? Are we assuming that the problem can be solved, or do we need to determine whether such colinear points exist first?

The line segments might intersect but we don't want that point. It can be assumed that if the segments do intersect then they only intersect at the endpoints ie the intersection will not be in the middle of any segment. Cannot assume the problem can be solved, but it is a simple test to see if the collinear points are in the line segments.

Also, are the endpoints given in a particular order: i.e. L1 (a,b) to (c,d) where a<c and b<d, or something like that? The format of your input/spreadsheet, and any assumptions given would help determine the best computational route.

Edit: Finally, just to clarify, you want to find points with the shortest distance between P1 and P2... NOT with the shortest line segment connecting P1, P2 and P3, correct?

The end points are not given in any order, but a simple max, min calculation in excel can determine the order. Currently I'm using solver to solve this problem in excel, but there is lot of computation time required and the tool takes forever since 100s of these calculation are done. Hoping for something less costly. My spreadsheet essentially works like this:
1. get the slope and y-intercept of both lines
2. Solver is set up to vary P1 and P2 until the distance between P1,P2 is minimized with the constraint that P1,P2,P3 are on the same line, distance between P1,P2 is greater than 1(to avoid the intersection point if there(safe assumption that distance is always >1 if possible)), the point P1 is greater than the min of segment L1 and less than the max of L1, the point P2 is greater than the min of segment L2 and less than the max of L2

Yes, shortest distance between P1 and P2.

 

[bossman27]

Actually, I think with some important exceptions, jbriggs444 is correct that the closest separation will often be the endpoint of one segment and somewhere in the middle of the other.

I just typed out a bunch of random ideas, but I'm not sure what you're looking for. There are a number of ways to go about this. If I was writing a python or C program to do this, I would probably write conditional statements defining all the possible exceptions and what to do in their cases, and then use the general rule if none of them applied. But with that said, it sounds like your looking for more of a brute force approach? I'm not familiar with how much you can make use conditional statements in a spreadsheet, if at all. If I'm off base here, let me know.

One possible brute force method (that may need refinement): If you were to find the slopes of lines connecting P3 to each of the 4 endpoints (call the slopes s1, s1' (endpts of L1) s2, s2' (endpts of L2)), you could narrow your search down. If s1 and s1' are both < or both > than s2 and s2', you don't have any collinear points. That is, if [s1,s1'] doesn't intersect with [s2, s2']. If the ranges do overlap, then you only care about points P1 and P2 that have a line through P3 with a slope between the two middle values. To retirate, that is to say that L123 must have a slope that is in between s1 and s1' AND between s2 and s2'. In some cases, you'll still be checking all possible pairs, but this should help check for existence and narrow down your possible pairs in most cases.

Do keep in mind that if you make an arbitrary minimum separation value, it is possible that you could get two line segments where collinear points exist, but with all P1 and P2 pairs having a separation >0 and <1. You may not care, but I think it's worth noting that you could have false negatives.

 

[jbriggs444]

Actually, I think with some important exceptions, jbriggs444 is correct that the closest separation will often be the endpoint of one segment and somewhere in the middle of the other.

I had completely ignored the requirement that the shortest path pass through point P3, so any correctness on my part is largely accidental.

Given that requirement it looks like one brute force approach would be to parameterize the problem in terms of the intersection point of a candidate shortest-path and one of the two lines and to express the parameter as the distance from one of the two segment endpoints.

The candidate shortest path length would then be a [possibly messy] formula in one variable. The goal is to minimize the value of that function subject to the constraint that both intersection points lie within the two given line segments.

The only possible minima are at the four boundaries (where the candidate shortest path intersects a segment endpoint) and any places where the first derivitive of the distance formula is zero.

If one could solve for the zeroes of the first derivitive that then would lead to a bulky if-then-else construct picking out a global minimum from the various candidates.

 

[bossman27]

After drawing out quite a few examples, I'm fairly confident that if solutions exist, they will involve at least one of the endpoints. Like I said, find the slopes from P3 to each of the endpoints. You just need to look for overlap between the ranges [S1, S1'] and [S2, S2']. The only exception I can find (other than intersection) is if the segments are parallel and P3 can be reached by a line perpendicular to BOTH of the segments. In that case, such a perpendicular line is actually the one connecting your P1 and P2 solutions. In other cases, parallel segments will still have a solution involving one of the endpoints.

If P3 = (1,1)
L1: y1 = -(1/2)x1 + 4 [endpts = (2,3) and (4,2)]
L2: y2 = -x2 + 8 [endpts = (2,6) and (4,4)]

Then the end points of L1 and P3 give a slope range [(1/3), 2]
The end points of L2 and P3 give a slope range [1, 5]

Overlap is the range [1, 2], which in this case corresponds to the "bottom" endpt of L2 and "top" endpt of L1. The slopes of lines connecting all possible pairs of P1 and P2 will be between 1 and 2.

(Try m = 2) --> P3 line --> y = 2x - 1
P1 = (2,3)
Find P2 --> 2x-1 = -x+8 --> x =3 --> y = 5
P2 = (3,5)

(Try m=1): --> P3 line --> y = x
P2 = (4,4)
Find P1 --> x = -(1/2)x + 4 --> x = (8/3) --> y = (8/3)
P1 = (8/3, 8/3)

With m = 2 you get a P1-P2 distance of 2.24

With m = 1 you get a distance of 1.89

Any other solution will have a distance somewhere between these two. As I said, this holds in all cases I can think of drawing except the types of parallel lines I described at the top.

Also, if the segments share an endpoint, finding P1 and P2 will be more complicated, but the [S1, S1'] overlap with [S2, S2'] still works to check existence of solutions, though note that the ranges will share a common endpoint, so you're looking to make sure they OVERLAP, not just touch.

 

[Norwegian]

After drawing out quite a few examples, I'm fairly confident that if solutions exist, they will involve at least one of the endpoints.

I remind you that we are doing mathematics here. Being fairly confident is just not good enough.

Any other solution will have a distance somewhere between these two. As I said, this holds in all cases I can think of drawing except the types of parallel lines I described at the top.

Then I suggest adding to your imagination the possibility of two slightly angled lines and a point somewhere in the middle, as well as other cases, where the shortest distance in question is not attained at any endpoint.

 

[bossman27]

I remind you that we are doing mathematics here. Being fairly confident is just not good enough.

...I suggest adding to your imagination the possibility of two slightly angled lines and a point somewhere in the middle, as well as other cases, where the shortest distance in question is not attained at any endpoint.

Point taken, I was a bit hasty there. I suppose I shouldn't be so confident in my mental sharpness after an all-nighter.

Nonetheless, even if an endpoint isn't involved in the solution, looking at the slopes between P3 and the endpoints is still of value in reducing the number of computations in a brute force approach. Unless I'm just going nutty, of course.