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

Question

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

使用一堆 IF 语句很容易做到。但我想知道它们是否是一个更有效的数学公式。

例如1：

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

L1=线段1，L2=线段2； ，这里的距离为 0

由于相交 2：

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

这里的距离是L2x1 - L1x2

编辑：

唯一的假设是线段是有序的，即x2总是> x1。

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

编辑2：

我必须在T-SQL (SQL Server 2008) 中实现这一点。我只需要逻辑...我可以编写 T-SQL。

编辑3：

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

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

线段2是线段1的线段，使得距离为0。

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

Answer 1

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

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

然后：

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

根据您运行它的位置，您的编译器应该很好地优化它。无论如何，您可能应该进行分析以确保您的代码是瓶颈，然后再降低其可读性以提高理论上的性能。

Answer 2

这适用于所有情况：

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

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

证明

请注意，该算法是对称的，因此非对称情况只需覆盖一次。所以我要断言 s2 >= s1 wlog 另请注意 e1 >= s1 和 e2 >= s2。

情况：

• L1 结束后开始 L2（s2 >= e1）：s1 max s2 = s2，e1 min e2 = e1。结果是 s2 - e1，它是非负数，显然是我们想要的值（距离）。
• L1 内的 L2（s2 <= e1，e2 <= e1）：s1 max s2 = s2，e1 min e2 = e2。 s2 - e2 为非正数，s2 <= e2，因此重叠期间结果如预期为 0。
• L2 在 L1 内开始，但在 (s2 <= e1, e2 >= e1) 之后结束： s1 max s2 = s2, e1 min e2 = e1。由于 s2 <= e1，s2 - e1 为非正数，因此重叠期间结果如预期为 0。

Answer 3

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

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

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

假设 LNx1 LNx2。

Answer 4

我认为由于 1D 中的所有线段都是 (X,0) 或 (0,Y) 形式之一，

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

在这里，在数组中存储元素时需要小心，以免存储重复的元素

Answer 5

这个公式似乎适用于所有情况，但一条线完全位于另一条线上的情况除外。

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