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

Question

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

It's easy to do with a bunch of IF statements. But I was wondering if their is a more efficient math formula.

E.g. 1:

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

L1 = line segment 1, L2 = line segment 2; the distance here is 0 because of intersection

E.g. 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 is always > x1.

Line segment 1 may be to the left, right, equal to etc. of line segment 2. The algorithm has to solve for this.

EDIT 2:

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

EDIT 3:

If a line segment is a line segment of the other 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 slightly on whether you already know which range is smallest already, 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're running this, your compiler should optimise it nicely. In any case, you should probably profile to make sure that your code is a bottleneck before making it less readable for a theoretical performance improvement.

Answer 2

This works in all cases:

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

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

Proof

Note that the algorithm is symmetric, so asymmetric cases only need to covered once. So I'm going to assert s2 >= s1 w.l.o.g. Also note e1 >= s1 and e2 >= s2.

Cases:

• L2 starts after L1 ends (s2 >= e1): s1 max s2 = s2, e1 min e2 = e1. Result is s2 - e1, which is non-negative and clearly the value we want (the distance).
• L2 inside L1 (s2 <= e1, e2 <= e1): s1 max s2 = s2, e1 min e2 = e2. s2 - e2 is non-positive by s2 <= e2, so the result is 0 as expected during overlap.
• L2 starts within L1 but ends after (s2 <= e1, e2 >= e1): s1 max s2 = s2, e1 min e2 = e1. s2 - e1 is non-positive by s2 <= e1, so the result is 0 as expected during overlap.

Answer 3

I do not think there is a way around the conditions. But this is succinct:

var diff1 = L2x1 - L1x2;
var diff2 = L2x2 - L1x1;

return diff1 > 0 ? max(0, diff1) : -min(0,diff2);

This assumes LNx1 < LNx2.

Answer 4

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

so store all these x values in a array and sort the array and minimum distance will the differece between 1st 2 elemenst of the array.

Here you need to be careful while storing element in the array so that duplicate elemenst are not stored

Answer 5

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

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