首页 文章

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

提问于
浏览
4

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

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

例如 . 1:

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

L1 =线段1,L2 =线段2;由于交叉,这里的距离是0

例如 . 2:

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

这里的距离是L2x1 - L1x2

EDIT:

唯一的假设是线段是有序的,即x2总是> x1 .

线段1可以是线段2的左,右,等于等 . 算法必须解决此问题 .

EDIT 2:

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

EDIT 3:

如果线段是另一条线的线段,则距离为0 .

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

线段2是线段1的一段,使距离为0 .

如果它们相交或触摸,则距离为0 .

5 回答

  • 3

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

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

    然后:

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

    根据您运行它的位置,编译器应该很好地优化它 . 在任何情况下,您都应该进行分析,以确保您的代码成为瓶颈,然后再降低其可读性,从而提高理论性能 .

  • 0

    这适用于所有情况:

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

    作为奖励,删除max 0意味着否定结果表明两个段中有多少重叠 .

    Proof

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

    案例:

    • L2在L1结束后开始(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 .

  • 0

    我认为没有办法解决这些问题 . 但这很简洁:

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

    假设LNx1 <LNx2 .

  • 0

    我想因为1D中的所有线段都是形式(X,0)或(0,Y)之一

    所以将所有这些x值存储在一个数组中并对数组进行排序,最小距离将是数组的第一个2元之间的差异 .

    在这里,您需要小心将元素存储在数组中,以便不存储重复的元素

  • 2

    这个公式似乎适用于所有情况,但是一条线完全位于另一条线上 .

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

相关问题