1D中两条线段之间最短距离的高效算法

Question

我可以找到很多公式来计算两条斜线之间的距离。我想要计算在一个维度内两条线段之间的距离。

使用一堆 IF 语句很容易实现，但我想知道是否有更高效的数学公式。

例如1：

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

L1 = 线段1，L2 = 线段2；由于交点存在，距离为0。

例如2：

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

这里的距离是L2x1 - L1x2。

编辑：

唯一的假设是线段有序，即x2始终大于x1。

线段1可能在线段2的左侧、右侧、相等等。算法必须解决这个问题。

编辑2：

我必须在T-SQL（SQL Server 2008）中实现这个，我只需要逻辑...我可以写T-SQL。

编辑3：

如果一条线段是另一条线段的一部分，则距离为0。

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

线段2是线段1的一部分，因此它们的距离为0。

如果它们相交或接触，则距离为0。

- IamIC

---

为了让问题更清晰，我建议您使用线段。所有一维线段都是相同的。您能否澄清假设，例如对于每个线段，“x2> = x1”（不确定是否是这种情况）？ - Ani

Answer 1

这个问题与问题“两个范围是否相交，如果不相交则它们之间的距离是多少？”相同。答案略有不同，取决于您是否已经知道哪个范围最小，以及范围内的点是否正确排序（即，线是否具有相同方向）。

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

然后：

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

根据您运行代码的位置，编译器应该可以很好地进行优化。无论如何，在通过影响可读性来实现理论上的性能改进之前，您应该进行性能分析以确保您的代码是瓶颈。

- Andrew Aylett

---

太棒了！在Excel中证明这个方法有效不到1分钟。谢谢！ - IamIC

Answer 2

这适用于所有情况：

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

作为奖励，删除max 0意味着负结果确切地指示了两个段重叠的程度。

证明：

请注意该算法是对称的，因此不对称情况只需要覆盖一次。因此，我要断言s2 >= s1 w.l.o.g。还要注意e1 >= s1和e2 >= s2。

情况：

1. L2在L1结束后开始（s2 >= e1）：s1 max s2 = s2，e1 min e2 = e1。结果为s2 - e1，这是非负数，显然是我们想要的值（距离）。 2. L2在L1内部（s2 <= e1，e2 <= e1）：s1 max s2 = s2，e1 min e2 = e2。由于s2 <= e2，所以s2-e2是非正数，因此结果为0，与重叠期间所预期的相同。 3. L2在L1内部开始但之后结束（s2 <= e1，e2 >= e1）：s1 max s2 = s2，e1 min e2 = e1。由于s2 <= e1，因此s2-e1是非正数，因此结果为0，与重叠期间所预期的相同。

- Craig Gidney

---

+1。或者更多，根据海报上的语法，d = max(0, max(L1x1,L2x1)-min(L1x2,L2x2) )。 - phkahler

这是我写的代码：MAX(0,IF(L1x1<L2x1,L2x1-L1x2,L1x1-l2x2)) - IamIC

@IanC 那也可以正常工作，但我觉得它更复杂了，并且失去了没有最大值为0的属性。 - Craig Gidney

最终，我会用 T-SQL 来编写它。那里的代码一点也不漂亮 :) - IamIC

Answer 3

我认为没有绕过这些条件的方法。但是这很简洁：

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

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

这里假设 LNx1 < LNx2。

- Aliostad

---

这些线条可以重叠，并且可以以任何关系彼此存在（左侧、右侧、内部、相交等）。 - IamIC

Answer 4

我认为在一维中，所有线段都是形式为（X，0）或（0，Y）之一

因此将所有这些x值存储在数组中并对数组进行排序，最小距离将是数组的前两个元素之间的差。

在存储元素时，您需要小心，以避免存储重复元素。

- TalentTuner

---

这不会在 Line 1 是 Line 2 的一部分时返回 0。 - IamIC

Answer 5

这个公式似乎在所有情况下都有效，但当一条线完全落在另一条线上时就无法奏效。

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

- bezmax

---

我尝试过了。如果第一行是第二行的一部分，则结果应为0。 - IamIC