线段相交——有时有效，有时无效

Question

我想显示两条线段的交点。分段是动画的，因此它们根据进度开始和停止相交。

因此我有这个代码：

class LineSegment {
  constructor(x1,y1,x2,y2) {
    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;
  }

  contains (x,y) {
    const
      x1 = Math.min(this.x1, this.x2),
      y1 = Math.min(this.y1, this.y2), 
      x2 = Math.max(this.x1, this.x2),
      y2 = Math.max(this.y1, this.y2),
      dot = ((x - x1) * (y2 - y1)) - ((y - y1) * (x2 - x1))
    ;

    return  dot <= Number.EPSILON && 
            x >= x1 && x <= x2 && 
            y >= y1 && y <= y2;
  }
}

我在代码中的某个地方这样使用：

const 
  seg1 = new LineSegment(…),
  seg2 = new LineSegment(…),
  i    = Intersect(seg1, seg2), //working code that calculates x and y values
                                //for the »unbounded« intersection
  contains = i !== null &&
             seg1.contains(i.x, i.y) &&
             seg2.contains(i.x, i.y)
;

if (contains) {
  //show a circle around x and y

} else {
  //remove that one
}

事实上，那些路口 » 闪烁 «，意味着它们有时有效，有时无效。我在这里错过了什么，我想我运行陷入了这里的数字问题？

由于@Gilles-Philippe Paillé 在此处对用于计算交集的代码进行了评论。我住在另一个 Helper class，看起来像这样：

intersect ({ a: a2, b: b2, c: c2 }) {
  const 
    {
      a:a1, 
      b:b1, 
      c:c1
    } = this,
    denom = det(a1, a2, b1, b2)
  ;

  //only chuck norris can devide by zero!
  return denom == 0 ?
    null :
    [ -1 * det(b1, c1, b2, c2) / denom,
           det(a1, c1, a2, c2) / denom ];
  }

Answer 1

dot 变量实际上是行列式（或二维叉积）。问题在于行列式可能为负。因此，您需要测试行列式的绝对值。此外，Number.EPSILON 是最小的非零数，在数值不准确的情况下没有用。您应该改用更合理的值：

Math.abs(dot) <= 1e-8

此外，行列式应该使用分割点计算，而不是边界框min/max:

dot = ((x - this.x1) * (this.y2 - this.y1)) - ((y - this.y1) * (this.x2 - this.x1))

Answer 2

一个更简单的解决方案是检查一段的末端是否位于相对于另一段的不同半平面上，反之亦然。这不需要除法：

function side(a, b, p) {
    return (p.x - a.x)*(b.y - a.y) + (p.y - a.y)*(a.x - b.x);
}

function xsect(a0, b0, a1, b1) {
    return (side(a0, b0, a1) * side(a0, b0, b1) < 0 &&
            side(a1, b1, a0) * side(a1, b1, b0) < 0)
}

如果你需要包括边界点，事情会更烦人 and/or 共线线段交点（另请注意，即使是整数坐标，两条线段的交点也可能无法在没有近似的情况下用浮点数精确表示- 例如 (0, 0)-(1, 10) 和 (0, 1)-(10, 1)).

Answer 3

截线

以下函数查找截距（如果有的话）作为由每条线上的两个点 {p1:{x,y}, p2{x,y}} 定义的两条线的一个点 {x, y}。

前两个函数用于线段（每个都有固定长度），后两个函数是无限长的线。

线段截距

作为4个点p1 = {x,y}、p2 = {x,y}、p3 = {x,y}、p4 = {x,y}定义两条线段的端点。 Returns 仅在有拦截时点，否则 return undefined.

function interceptSegs(p1, p2, p3, p4, p = {}) {
    const x1 = p2.x - p1.x, y1 = p2.y - p1.y;
    const x2 = p4.x - p3.x, y2 = p4.y - p3.y;
    const c = x1 * y2 - y1 * x2;
    if (c) {
        const x3 = p1.x - p3.x, y3 = p1.y - p3.y;
        const u = (x1 * y3 - y1 * x3) / c;
        if (u >= 0 && u <= 1) {
            const u = (x2 * y3 - y2 * x3) / c;
            if (u >= 0 && u <= 1) {
                p.x = p1.x + x1 * u;
                p.y = p1.y + y1 * u;    
                return p;
            }
        }
    }
}

或作为两条线l1 = {p1:{x,y}, p2{x,y}},l2 = {p1:{x,y}, p2{x,y}}returns只有在有截距时才指向

function interceptSegs(l1, l2) {
    const a = {x: l1.p2.x - l1.p1.x, y: l1.p2.y - l1.p1.y};
    const b = {x: l2.p2.x - l2.p1.x, y: l2.p2.y - l2.p1.y};
    const c = a.x * b.y - a.y * b.x;
    if (c) {
        const e = {x: l1.p1.x - l2.p1.x, y: l1.p1.y - l2.p1.y};
        const u = (a.x * e.y - a.y * e.x) / c;
        if (u >= 0 && u <= 1) {
            const u = (b.x * e.y - b.y * e.x) / c;
            if (u >= 0 && u <= 1) {
                return {x: l1.p1.x + a.x * u, y: l1.p1.y + a.y * u};
            }
        }
    }
}

拦截线

与上述函数类似，但假设行是无限长的。将 return 一个点或 undefined 如果线是平行的。

function intercept(p1, p2, p3, p4, p = {}) {
    const x1 = p2.x - p1.x, y1 = p2.y - p1.y;
    const x2 = p4.x - p3.x, y2 = p4.y - p3.y;
    const c = x1 * y2 - y1 * x2;
    if (c) {
        let u = (x1 * (p1.y - p3.y) - y1 * (p1.x - p3.x)) / c;
        p.x = p3.x + x2 * u;
        p.y = p3.y + y2 * u;    
        return p;
    }
}

OR 作为行 l1，l2 returns 仅当存在截距时才指向。 Returns undefined 如果直线平行。

function interceptLines(l1, l2) {
    const a = {x: l1.p2.x - l1.p1.x, y: l1.p2.y - l1.p1.y};
    const b = {x: l2.p2.x - l2.p1.x, y: l2.p2.y - l2.p1.y};
    const c = a.x * b.y - a.y * b.x;
    if (c) {
        const u = (a.x * (l1.p1.y - l2.p1.y) - a.y * (l1.p1.x - l2.p1.x)) / c;
        return {x: l2.p1.x + b.x * u, y: l2.p1.y + b.y * u};
    }
}

线段相交——有时有效，有时无效

Line Segement Intersection — works sometimes, sometimes not

javascript

geometry

computational-geometry

截线

线段截距

拦截线