Brunobkr/llama.cpp_AlgMor24_github

1/**2 * This class maintains a list of static geometry related utility methods.3 *4 *5 * Copyright: i-Vis Research Group, Bilkent University, 2007 - present6 */7 8const Point = require('./Point');9 10function IGeometry() {11 12}13 14/**15 * This method calculates *half* the amount in x and y directions of the two16 * input rectangles needed to separate them keeping their respective17 * positioning, and returns the result in the input array. An input18 * separation buffer added to the amount in both directions. We assume that19 * the two rectangles do intersect.20 */21IGeometry.calcSeparationAmount = function (rectA, rectB, overlapAmount, separationBuffer)22{23  if (!rectA.intersects(rectB)) {24    throw "assert failed";25  }26 27  let directions = new Array(2);28 29  this.decideDirectionsForOverlappingNodes(rectA, rectB, directions);30 31  overlapAmount[0] = Math.min(rectA.getRight(), rectB.getRight()) -32      Math.max(rectA.x, rectB.x);33  overlapAmount[1] = Math.min(rectA.getBottom(), rectB.getBottom()) -34      Math.max(rectA.y, rectB.y);35 36  // update the overlapping amounts for the following cases:37  if ((rectA.getX() <= rectB.getX()) && (rectA.getRight() >= rectB.getRight()))38  {39    /* Case x.1:40    *41    * rectA42    * 	|                       |43    * 	|        _________      |44    * 	|        |       |      |45    * 	|________|_______|______|46    * 			 |       |47    *           |       |48    *        rectB49    */50    overlapAmount[0] += Math.min((rectB.getX() - rectA.getX()),51        (rectA.getRight() - rectB.getRight()));52  }53  else if ((rectB.getX() <= rectA.getX()) && (rectB.getRight() >= rectA.getRight()))54  {55    /* Case x.2:56    *57    * rectB58    * 	|                       |59    * 	|        _________      |60    * 	|        |       |      |61    * 	|________|_______|______|62    * 			 |       |63    *           |       |64    *        rectA65    */66    overlapAmount[0] += Math.min((rectA.getX() - rectB.getX()),67        (rectB.getRight() - rectA.getRight()));68  }69  if ((rectA.getY() <= rectB.getY()) && (rectA.getBottom() >= rectB.getBottom()))70  {71    /* Case y.1:72     *          ________ rectA73     *         |74     *         |75     *   ______|____  rectB76     *         |    |77     *         |    |78     *   ______|____|79     *         |80     *         |81     *         |________82     *83     */84    overlapAmount[1] += Math.min((rectB.getY() - rectA.getY()),85        (rectA.getBottom() - rectB.getBottom()));86  }87  else if ((rectB.getY() <= rectA.getY()) && (rectB.getBottom() >= rectA.getBottom()))88  {89    /* Case y.2:90    *          ________ rectB91    *         |92    *         |93    *   ______|____  rectA94    *         |    |95    *         |    |96    *   ______|____|97    *         |98    *         |99    *         |________100    *101 */102    overlapAmount[1] += Math.min((rectA.getY() - rectB.getY()),103        (rectB.getBottom() - rectA.getBottom()));104  }105 106  // find slope of the line passes two centers107  let slope = Math.abs((rectB.getCenterY() - rectA.getCenterY()) /108      (rectB.getCenterX() - rectA.getCenterX()));109  // if centers are overlapped110  if ((rectB.getCenterY() === rectA.getCenterY()) &&111      (rectB.getCenterX() === rectA.getCenterX()))112  {113    // assume the slope is 1 (45 degree)114    slope = 1.0;115  }116 117  let moveByY = slope * overlapAmount[0];118  let moveByX = overlapAmount[1] / slope;119  if (overlapAmount[0] < moveByX)120  {121    moveByX = overlapAmount[0];122  }123  else124  {125    moveByY = overlapAmount[1];126  }127  // return half the amount so that if each rectangle is moved by these128  // amounts in opposite directions, overlap will be resolved129  overlapAmount[0] = -1 * directions[0] * ((moveByX / 2) + separationBuffer);130  overlapAmount[1] = -1 * directions[1] * ((moveByY / 2) + separationBuffer);131};132 133/**134 * This method decides the separation direction of overlapping nodes135 *136 * if directions[0] = -1, then rectA goes left137 * if directions[0] = 1,  then rectA goes right138 * if directions[1] = -1, then rectA goes up139 * if directions[1] = 1,  then rectA goes down140 */141IGeometry.decideDirectionsForOverlappingNodes = function (rectA, rectB, directions)142{143  if (rectA.getCenterX() < rectB.getCenterX())144  {145    directions[0] = -1;146  }147  else148  {149    directions[0] = 1;150  }151 152  if (rectA.getCenterY() < rectB.getCenterY())153  {154    directions[1] = -1;155  }156  else157  {158    directions[1] = 1;159  }160};161 162/**163 * This method calculates the intersection (clipping) points of the two164 * input rectangles with line segment defined by the centers of these two165 * rectangles. The clipping points are saved in the input double array and166 * whether or not the two rectangles overlap is returned.167 */168IGeometry.getIntersection2 = function(rectA, rectB, result)169{170  //result[0-1] will contain clipPoint of rectA, result[2-3] will contain clipPoint of rectB171  let p1x = rectA.getCenterX();172  let p1y = rectA.getCenterY();173  let p2x = rectB.getCenterX();174  let p2y = rectB.getCenterY();175 176  //if two rectangles intersect, then clipping points are centers177  if (rectA.intersects(rectB))178  {179    result[0] = p1x;180    result[1] = p1y;181    result[2] = p2x;182    result[3] = p2y;183    return true;184  }185  //variables for rectA186  let topLeftAx = rectA.getX();187  let topLeftAy = rectA.getY();188  let topRightAx = rectA.getRight();189  let bottomLeftAx = rectA.getX();190  let bottomLeftAy = rectA.getBottom();191  let bottomRightAx = rectA.getRight();192  let halfWidthA = rectA.getWidthHalf();193  let halfHeightA = rectA.getHeightHalf();194  //variables for rectB195  let topLeftBx = rectB.getX();196  let topLeftBy = rectB.getY();197  let topRightBx = rectB.getRight();198  let bottomLeftBx = rectB.getX();199  let bottomLeftBy = rectB.getBottom();200  let bottomRightBx = rectB.getRight();201  let halfWidthB = rectB.getWidthHalf();202  let halfHeightB = rectB.getHeightHalf();203 204  //flag whether clipping points are found205  let clipPointAFound = false;206  let clipPointBFound = false;207 208  // line is vertical209  if (p1x === p2x)210  {211    if (p1y > p2y)212    {213      result[0] = p1x;214      result[1] = topLeftAy;215      result[2] = p2x;216      result[3] = bottomLeftBy;217      return false;218    }219    else if (p1y < p2y)220    {221      result[0] = p1x;222      result[1] = bottomLeftAy;223      result[2] = p2x;224      result[3] = topLeftBy;225      return false;226    }227    else228    {229      //not line, return null;230    }231  }232  // line is horizontal233  else if (p1y === p2y)234  {235    if (p1x > p2x)236    {237      result[0] = topLeftAx;238      result[1] = p1y;239      result[2] = topRightBx;240      result[3] = p2y;241      return false;242    }243    else if (p1x < p2x)244    {245      result[0] = topRightAx;246      result[1] = p1y;247      result[2] = topLeftBx;248      result[3] = p2y;249      return false;250    }251    else252    {253      //not valid line, return null;254    }255  }256  else257  {258    //slopes of rectA's and rectB's diagonals259    let slopeA = rectA.height / rectA.width;260    let slopeB = rectB.height / rectB.width;261 262    //slope of line between center of rectA and center of rectB263    let slopePrime = (p2y - p1y) / (p2x - p1x);264    let cardinalDirectionA;265    let cardinalDirectionB;266    let tempPointAx;267    let tempPointAy;268    let tempPointBx;269    let tempPointBy;270 271    //determine whether clipping point is the corner of nodeA272    if ((-slopeA) === slopePrime)273    {274      if (p1x > p2x)275      {276        result[0] = bottomLeftAx;277        result[1] = bottomLeftAy;278        clipPointAFound = true;279      }280      else281      {282        result[0] = topRightAx;283        result[1] = topLeftAy;284        clipPointAFound = true;285      }286    }287    else if (slopeA === slopePrime)288    {289      if (p1x > p2x)290      {291        result[0] = topLeftAx;292        result[1] = topLeftAy;293        clipPointAFound = true;294      }295      else296      {297        result[0] = bottomRightAx;298        result[1] = bottomLeftAy;299        clipPointAFound = true;300      }301    }302 303    //determine whether clipping point is the corner of nodeB304    if ((-slopeB) === slopePrime)305    {306      if (p2x > p1x)307      {308        result[2] = bottomLeftBx;309        result[3] = bottomLeftBy;310        clipPointBFound = true;311      }312      else313      {314        result[2] = topRightBx;315        result[3] = topLeftBy;316        clipPointBFound = true;317      }318    }319    else if (slopeB === slopePrime)320    {321      if (p2x > p1x)322      {323        result[2] = topLeftBx;324        result[3] = topLeftBy;325        clipPointBFound = true;326      }327      else328      {329        result[2] = bottomRightBx;330        result[3] = bottomLeftBy;331        clipPointBFound = true;332      }333    }334 335    //if both clipping points are corners336    if (clipPointAFound && clipPointBFound)337    {338      return false;339    }340 341    //determine Cardinal Direction of rectangles342    if (p1x > p2x)343    {344      if (p1y > p2y)345      {346        cardinalDirectionA = this.getCardinalDirection(slopeA, slopePrime, 4);347        cardinalDirectionB = this.getCardinalDirection(slopeB, slopePrime, 2);348      }349      else350      {351        cardinalDirectionA = this.getCardinalDirection(-slopeA, slopePrime, 3);352        cardinalDirectionB = this.getCardinalDirection(-slopeB, slopePrime, 1);353      }354    }355    else356    {357      if (p1y > p2y)358      {359        cardinalDirectionA = this.getCardinalDirection(-slopeA, slopePrime, 1);360        cardinalDirectionB = this.getCardinalDirection(-slopeB, slopePrime, 3);361      }362      else363      {364        cardinalDirectionA = this.getCardinalDirection(slopeA, slopePrime, 2);365        cardinalDirectionB = this.getCardinalDirection(slopeB, slopePrime, 4);366      }367    }368    //calculate clipping Point if it is not found before369    if (!clipPointAFound)370    {371      switch (cardinalDirectionA)372      {373        case 1:374          tempPointAy = topLeftAy;375          tempPointAx = p1x + (-halfHeightA) / slopePrime;376          result[0] = tempPointAx;377          result[1] = tempPointAy;378          break;379        case 2:380          tempPointAx = bottomRightAx;381          tempPointAy = p1y + halfWidthA * slopePrime;382          result[0] = tempPointAx;383          result[1] = tempPointAy;384          break;385        case 3:386          tempPointAy = bottomLeftAy;387          tempPointAx = p1x + halfHeightA / slopePrime;388          result[0] = tempPointAx;389          result[1] = tempPointAy;390          break;391        case 4:392          tempPointAx = bottomLeftAx;393          tempPointAy = p1y + (-halfWidthA) * slopePrime;394          result[0] = tempPointAx;395          result[1] = tempPointAy;396          break;397      }398    }399    if (!clipPointBFound)400    {401      switch (cardinalDirectionB)402      {403        case 1:404          tempPointBy = topLeftBy;405          tempPointBx = p2x + (-halfHeightB) / slopePrime;406          result[2] = tempPointBx;407          result[3] = tempPointBy;408          break;409        case 2:410          tempPointBx = bottomRightBx;411          tempPointBy = p2y + halfWidthB * slopePrime;412          result[2] = tempPointBx;413          result[3] = tempPointBy;414          break;415        case 3:416          tempPointBy = bottomLeftBy;417          tempPointBx = p2x + halfHeightB / slopePrime;418          result[2] = tempPointBx;419          result[3] = tempPointBy;420          break;421        case 4:422          tempPointBx = bottomLeftBx;423          tempPointBy = p2y + (-halfWidthB) * slopePrime;424          result[2] = tempPointBx;425          result[3] = tempPointBy;426          break;427      }428    }429  }430  return false;431};432 433/**434 * This method returns in which cardinal direction does input point stays435 * 1: North436 * 2: East437 * 3: South438 * 4: West439 */440IGeometry.getCardinalDirection = function (slope, slopePrime, line)441{442  if (slope > slopePrime)443  {444    return line;445  }446  else447  {448    return 1 + line % 4;449  }450};451 452/**453 * This method calculates the intersection of the two lines defined by454 * point pairs (s1,s2) and (f1,f2).455 */456IGeometry.getIntersection = function(s1, s2, f1, f2)457{458  if (f2 == null) {459    return this.getIntersection2(s1, s2, f1);460  }461 462  let x1 = s1.x;463  let y1 = s1.y;464  let x2 = s2.x;465  let y2 = s2.y;466  let x3 = f1.x;467  let y3 = f1.y;468  let x4 = f2.x;469  let y4 = f2.y;470  let x, y; // intersection point471  let a1, a2, b1, b2, c1, c2; // coefficients of line eqns.472  let denom;473 474  a1 = y2 - y1;475  b1 = x1 - x2;476  c1 = x2 * y1 - x1 * y2;  // { a1*x + b1*y + c1 = 0 is line 1 }477 478  a2 = y4 - y3;479  b2 = x3 - x4;480  c2 = x4 * y3 - x3 * y4;  // { a2*x + b2*y + c2 = 0 is line 2 }481 482  denom = a1 * b2 - a2 * b1;483 484  if (denom === 0)485  {486    return null;487  }488 489  x = (b1 * c2 - b2 * c1) / denom;490  y = (a2 * c1 - a1 * c2) / denom;491 492  return new Point(x, y);493};494 495/**496 * This method finds and returns the angle of the vector from the + x-axis497 * in clockwise direction (compatible w/ Java coordinate system!).498 */499IGeometry.angleOfVector = function(Cx, Cy, Nx, Ny)500{501  let C_angle;502 503  if (Cx !== Nx)504  {505    C_angle = Math.atan((Ny - Cy) / (Nx - Cx));506 507    if (Nx < Cx)508    {509      C_angle += Math.PI;510    }511    else if (Ny < Cy)512    {513      C_angle += this.TWO_PI;514    }515  }516  else if (Ny < Cy)517  {518    C_angle = this.ONE_AND_HALF_PI; // 270 degrees519  }520  else521  {522    C_angle = this.HALF_PI; // 90 degrees523  }524 525  return C_angle;526};527 528 529/**530 * This method checks whether the given two line segments (one with point531 * p1 and p2, the other with point p3 and p4) intersect at a point other532 * than these points.533 */534IGeometry.doIntersect = function(p1, p2, p3, p4){535  let a = p1.x;536  let b = p1.y;537  let c = p2.x;538  let d = p2.y;539  let p = p3.x;540  let q = p3.y;541  let r = p4.x;542  let s = p4.y;543  let det = (c - a) * (s - q) - (r - p) * (d - b);544 545  if (det === 0) {546    return false;547  } else {548    let lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;549    let gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;550    return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);551  }552};553 554 555// -----------------------------------------------------------------------------556// Section: Class Constants557// -----------------------------------------------------------------------------558/**559 * Some useful pre-calculated constants560 */561IGeometry.HALF_PI = 0.5 * Math.PI;562IGeometry.ONE_AND_HALF_PI = 1.5 * Math.PI;563IGeometry.TWO_PI = 2.0 * Math.PI;564IGeometry.THREE_PI = 3.0 * Math.PI;565 566 567module.exports = IGeometry;568