Efficient algorithm for the shortest distance between two line segments in 1D

Question

I can find many formulas for finding the distance between two skew lines. I want to calculate the distance between two line segments in one dimension.

This is easy to do with a bunch of IF statements. But I was wondering if their more effective mathematical formula.

eg. 1:

----L1x1-------L2x1-------L1x2------L2x2---------------------------- 

L1 = line segment 1, L2 = line segment 2; distance here is 0 due to intersection

eg. 2:

 ----L1x1-------L1x2-------L2x1------L2x2---------------------------- 

the distance here is L2x1 - L1x2

EDIT:

The only assumption is that the line segments are ordered, i.e. x2 always> x1.

Line segment 1 can be left, right, equal, etc. segment 2. This algorithm should solve for this.

EDIT 2:

I have to implement this in T-SQL (SQL Server 2008). I just need logic ... I can write T-SQL.

EDIT 3:

If the line segment is a line segment of another line, the distance is 0.

 ----L1x1-------L2x1-------L2x2------L1x2---------------------------- 

Line segment 2 is a segment of line segment 1, making the distance 0.

If they intersect or touch, the distance is 0.

Answer 1

This question is the same as the question "do two ranges intersect, and if not, then what is the distance between them?" The answer depends a little on whether you know which range is the smallest, and whether the points in the ranges are ordered correctly (that is, whether the lines have the same direction).

 if (a.start < b.start) { first = a; second = b; } else { first = b; second = a; } 

Then:

 distance = max(0, second.start - first.end); 

Depending on where you work, your compiler should optimize it. In any case, you should probably profile to make sure your code is a bottleneck before making it less readable to theoretically improve performance.

Answer 2

This works in all cases:

 d = (s1 max s2 - e1 min e2) max 0 

As a bonus, removing max 0 means that a negative result indicates exactly how many of the two segments overlap.

Proof

Note that the algorithm is symmetric, therefore asymmetric cases need to be covered only once. So I'm going to state s2> = s1 wlog Also pay attention to e1> = s1 and e2> = s2.

Cases:

• L2 starts after the end of L1 (s2> = e1): s1 max s2 = s2, e1 min e2 = e1. The result of s2 is e1, which is non-negative and, obviously, the value we want (distance).
• L2 inside L1 (s2 <= e1, e2 <= e1): s1 max s2 = s2, e1 min e2 = e2. s2 - e2 is not positive with respect to s2 <= e2; therefore, the result is 0, as expected during the overlap.
• L2 starts at L1, but ends after (s2 <= e1, e2> = e1): s1 max s2 = s2, e1 min e2 = e1. s2 - e1 is not positive with respect to s2 <= e1, therefore the result is 0, as expected during the overlap.

Answer 3

I don’t think there is a way around the conditions. But this is concise:

 var diff1 = L2x1 - L1x2; var diff2 = L2x2 - L1x1; return diff1 > 0 ? max(0, diff1) : -min(0,diff2); 

This suggests that LNx1 <LNx2.

Answer 4

I think, since all line segments in 1D are one of the forms (X, 0) or (0, Y)

therefore, save all these x values ​​in an array and sort the array, and the minimum distance will differ between the 1st and 2nd element of the array.

Here you need to be careful when storing an element in an array so that duplicate elements are not saved

Answer 5

This formula seems to work in all cases except the one where one line lies completely on the other line.

 return -min(a2-b1,b2-a1)