Пересечение линии сегмента - иногда работает, иногда нет

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é здесь к коду, используемому для вычисления пересечения. Я живу в другом классе Хелпер и выглядит так:

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

Более простое решение состоит в том, чтобы проверить, находятся ли концы одного сегмента на разных полуплоскостях относительно другого сегмента и наоборот. Это не требует делений:

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

Вещи более раздражающие, если вам нужно включить пересечение граничных точек и / или коллинеарных сегментов (обратите внимание также, что точка пересечения двух сегментов, даже с целочисленными координатами, может быть невозможна представитьточно с числами с плавающей запятой без аппроксимации - например, (0, 0)-(1, 10) с (0, 1)-(10, 1)).

Answer 2

Переменная dot в действительности является детерминантом (или перекрестным произведением 2D). Проблема в том, что определитель может быть отрицательным. Таким образом, вам необходимо проверить абсолютное значение определителя. Более того, 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 3

Используемая мной функция похожа на следующую. Значения 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, 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) {
        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;
    }
}