线段交点-有时有效，有时无效

2024-05-21 • 问答

我想显示两个线段的交点。这些段具有动画效果，因此它们可以根据进度开始和停止相交。

因此我有以下代码：

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,y2 = Math.max(this.y1,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-PhilippePaillé的评论此处为用于计算交点的代码。我住在另一个Helper班上，看起来像这样：

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,c2) / denom ];
  }

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

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,a1) * side(a0,b1) < 0 &&
            side(a1,b1,a0) * side(a1,b0) < 0)
}

如果您需要包括边界点和/或共线段的交点，则事情会更烦人（另请注意，即使是整数坐标，两个段的交点也可能无法精确地用浮点数来表示，例如：{{ 1}}和(0,0)-(1,10)）。

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

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

此外，行列式应使用分段点而不是边界框的最小值/最大值来计算：

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

我使用的功能类似于以下内容。 u2和u1值是从开始起第一行和第二行的截距的单位位置

// returns undefined if no intercept
// else returns a new point or the point passed
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 cross = x1 * y2 - y1 * x2;
    if (cross) {
        const x3 = p1.x - p3.x,y3 = p1.y - p3.y;
        const u2 = (x1 * y3 - y1 * x3) / cross;
        if (u2 >= 0 && u2 <= 1) {
            const u1 = (x2 * y3 - y2 * x3) / cross;
            if (u1 >= 0 && u1 <= 1) {
                p.x = p1.x + x1 * u1;
                p.y = p1.y + y1 * u1;    
                return p;
            }
        }
    }
}

并忽略段长度

// And line intercepts ignoring end points
function intercept(p1,y2 = p4.y - p3.y;
    const cross = x1 * y2 - y1 * x2;
    if (cross) {
        let u = (x1 * (p1.y - p3.y) - y1 * (p1.x - p3.x)) / cross;
        p.x = p3.x + x2 * u;
        p.y = p3.y + y2 * u;    
        return p;
    }
}

线段交点-有时有效，有时无效

cisya 回答：线段交点-有时有效，有时无效

大家都在问