线段交点-有时有效，有时无效 [英] Line Segement Intersection — works sometimes, sometimes not

问题描述

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

I'd like to display the point of intersection of two line segments. The Segments are animated, so they start and stop to intersect, based on progress.

因此我有以下代码:

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;
  }
}

我在代码中的某处使用了这样的代码:

Somewhere in the code I use that like this:

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
}

实际上，那些闪烁"的交点表示它们有时有效，有时无效.我在这里想念的是什么，我想我在这里遇到了数字问题?

In fact, those intersections »flicker«, means they sometimes work and sometimes not. What am I missing here, I guess I am running into numerical issues here?

由于@ Gilles-PhilippePaillé的评论此处为用于计算交点的代码.我住在另一个Helper班上，看起来像这样:

Due to the comment of @Gilles-Philippe Paillé here to code used to calculate the intersection. I lives in another Helper class and looks like this:

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 ];
  }

推荐答案

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

The dot variable is in reality the determinant (or the 2D cross product). The problem is that the determinant can be negative. Thus you need to test the absolute value of the determinant. Moreover, Number.EPSILON is the smallest non-zero number, which is not useful is case of numerical inaccuracy. You should instead use a more reasonable value:

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

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

Moreover, the determinant should be calculated using the segment point, not the bounding box min/max:

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

这篇关于线段交点-有时有效，有时无效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！