Je voudrais afficher le point d'intersection de deux segments de ligne. Les segments sont animés, ils commencent et s'arrêtent donc pour se croiser, en fonction de la progression.

J'ai donc ce code:

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

Quelque part dans le code que j'utilise comme ceci:

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
}

En fait, ces intersections «scintillent», cela signifie qu'elles fonctionnent parfois et parfois non. Qu'est-ce que je manque ici, je suppose que je rencontre des problèmes numériques ici?

En raison du commentaire de @ Gilles-Philippe Paillé ici pour coder utilisé pour calculer l'intersection. Je vis dans une autre classe d'aide et ressemble à ceci:

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 ];
  }
1
philipp 4 nov. 2019 à 16:52

3 réponses

Meilleure réponse

La variable dot est en réalité le déterminant (ou le produit croisé 2D). Le problème est que le déterminant peut être négatif. Vous devez donc tester la valeur absolue du déterminant. De plus, Number.EPSILON est le plus petit nombre non nul, ce qui n'est pas utile en cas d'inexactitude numérique. Vous devriez plutôt utiliser une valeur plus raisonnable:

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

De plus, le déterminant doit être calculé en utilisant le point de segment, et non la boîte englobante min / max:

dot = ((x - this.x1) * (this.y2 - this.y1)) - ((y - this.y1) * (this.x2 - this.x1))
1
Gilles-Philippe Paillé 4 nov. 2019 à 15:02

La fonction que j'utilise est similaire à la suivante. Les valeurs u2 et u1 sont la position unitaire de l'ordonnée à l'origine pour les première et deuxième lignes depuis le début

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

Et pour ignorer la longueur du segment

// 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;
    }
}
0
Blindman67 5 nov. 2019 à 03:13

Une solution plus simple consiste à vérifier si les extrémités d'un segment sont sur des demi-plans différents par rapport à l'autre segment et vice-versa. Cela ne nécessite aucune division:

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

Les choses sont plus ennuyeuses si vous devez inclure l'intersection de points limites et / ou de segments colinéaires (notez également que le point d'intersection de deux segments même avec des coordonnées entières peut être impossible à représenter exactement avec des nombres à virgule flottante sans approximation - par exemple (0, 0)-(1, 10) avec (0, 1)-(10, 1)).

2
6502 4 nov. 2019 à 14:21