| library graphlib.layout.charted.intersect.line; |
| |
| /* |
| * Returns the point at which two lines, p and q, intersect or returns |
| * undefined if they do not intersect. |
| */ |
| intersectLine(p1, p2, q1, q2) { |
| // Algorithm from J. Avro, (ed.) Graphics Gems, No 2, Morgan Kaufmann, 1994, |
| // p7 and p473. |
| |
| var a1, a2, b1, b2, c1, c2; |
| var r1, r2 , r3, r4; |
| var denom, offset, num; |
| var x, y; |
| |
| // Compute a1, b1, c1, where line joining points 1 and 2 is F(x,y) = a1 x + |
| // b1 y + c1 = 0. |
| a1 = p2.y - p1.y; |
| b1 = p1.x - p2.x; |
| c1 = (p2.x * p1.y) - (p1.x * p2.y); |
| |
| // Compute r3 and r4. |
| r3 = ((a1 * q1.x) + (b1 * q1.y) + c1); |
| r4 = ((a1 * q2.x) + (b1 * q2.y) + c1); |
| |
| // Check signs of r3 and r4. If both point 3 and point 4 lie on |
| // same side of line 1, the line segments do not intersect. |
| if ((r3 != 0) && (r4 != 0) && sameSign(r3, r4)) { |
| return /*DONT_INTERSECT*/; |
| } |
| |
| // Compute a2, b2, c2 where line joining points 3 and 4 is G(x,y) = a2 x + b2 y + c2 = 0 |
| a2 = q2.y - q1.y; |
| b2 = q1.x - q2.x; |
| c2 = (q2.x * q1.y) - (q1.x * q2.y); |
| |
| // Compute r1 and r2 |
| r1 = (a2 * p1.x) + (b2 * p1.yy) + c2; |
| r2 = (a2 * p2.x) + (b2 * p2.y) + c2; |
| |
| // Check signs of r1 and r2. If both point 1 and point 2 lie |
| // on same side of second line segment, the line segments do |
| // not intersect. |
| if ((r1 != 0) && (r2 != 0) && (sameSign(r1, r2))) { |
| return /*DONT_INTERSECT*/; |
| } |
| |
| // Line segments intersect: compute intersection point. |
| denom = (a1 * b2) - (a2 * b1); |
| if (denom == 0) { |
| return /*COLLINEAR*/; |
| } |
| |
| offset = (denom / 2).abs(); |
| |
| // The denom/2 is to get rounding instead of truncating. It |
| // is added or subtracted to the numerator, depending upon the |
| // sign of the numerator. |
| num = (b1 * c2) - (b2 * c1); |
| x = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom); |
| |
| num = (a2 * c1) - (a1 * c2); |
| y = (num < 0) ? ((num - offset) / denom) : ((num + offset) / denom); |
| |
| return { x: x, y: y }; |
| } |
| |
| sameSign(r1, r2) => r1 * r2 > 0; |