binaries/data/mods/public/maps/random/rmgen/math.js

   1 const g_TileVertices = deepfreeze([
   2         new Vector2D(0, 0),
   3         new Vector2D(0, 1),
   4         new Vector2D(1, 0),
   5         new Vector2D(1, 1)
   6 ]);
   7
   8 const g_AdjacentCoordinates = deepfreeze([
   9         new Vector2D(1, 0),
  10         new Vector2D(1, 1),
  11         new Vector2D(0, 1),
  12         new Vector2D(-1, 1),
  13         new Vector2D(-1, 0),
  14         new Vector2D(-1, -1),
  15         new Vector2D(0, -1),
  16         new Vector2D(1, -1)
  17 ]);
  18
  19 function diskArea(radius)
  20 {
  21         return Math.PI * Math.square(radius);
  22 }
  23
  24 /**
  25  * Returns the angle of the vector between point 1 and point 2.
  26  * The angle is counterclockwise from the positive x axis.
  27  */
  28 function getAngle(x1, z1, x2, z2)
  29 {
  30         return Math.atan2(z2 - z1, x2 - x1);
  31 }
  32
  33 /**
  34  * Get pointCount points equidistantly located on a circle.
  35  * @param {Vector2D} center
  36  */
  37 function distributePointsOnCircle(pointCount, startAngle, radius, center)
  38 {
  39         return distributePointsOnCircularSegment(pointCount, 2 * Math.PI * (pointCount - 1) / pointCount, startAngle, radius, center);
  40 }
  41
  42 /**
  43  * Get pointCount points equidistantly located on a circular segment, including both endpoints.
  44  */
  45 function distributePointsOnCircularSegment(pointCount, maxAngle, startAngle, radius, center)
  46 {
  47         const points = [];
  48         const angle = [];
  49         pointCount = Math.round(pointCount);
  50
  51         for (let i = 0; i < pointCount; ++i)
  52         {
  53                 angle[i] = startAngle + maxAngle * i / Math.max(1, pointCount - 1);
  54                 points[i] = Vector2D.add(center, new Vector2D(radius, 0).rotate(-angle[i]));
  55         }
  56
  57         return [points, angle];
  58 }
  59
  60 /**
  61  * Returns the shortest distance from a point to a line.
  62  * The sign of the return value determines the direction!
  63  *
  64  * @param {Vector2D} - lineStart, lineEnd, point
  65  */
  66 function distanceOfPointFromLine(lineStart, lineEnd, point)
  67 {
  68         // Since the cross product is the area of the parallelogram with the vectors for sides and
  69         // one of the two vectors having length one, that area equals the distance between the points.
  70         return Vector2D.sub(lineStart, lineEnd).normalize().cross(Vector2D.sub(point, lineEnd));
  71 }
  72
  73 /**
  74  * Returns whether the two lines of the given width going through the given Vector2D intersect.
  75  */
  76 function testLineIntersection(start1, end1, start2, end2, width)
  77 {
  78         const start1end1 = Vector2D.sub(start1, end1);
  79         const start2end2 = Vector2D.sub(start2, end2);
  80         const start1start2 = Vector2D.sub(start1, start2);
  81
  82         return (
  83                 Math.abs(distanceOfPointFromLine(start1, end1, start2)) < width ||
  84                 Math.abs(distanceOfPointFromLine(start1, end1, end2)) < width ||
  85                 Math.abs(distanceOfPointFromLine(start2, end2, start1)) < width ||
  86                 Math.abs(distanceOfPointFromLine(start2, end2, end1)) < width ||
  87                 start1end1.cross(start1start2) * start1end1.cross(Vector2D.sub(start1, end2)) <= 0 &&
  88                 start2end2.cross(start1start2) * start2end2.cross(Vector2D.sub(start2, end1)) >= 0);
  89 }
  90
  91 /**
  92  * Returns the topleft and bottomright coordinate of the given two points.
  93  */
  94 function getBoundingBox(points)
  95 {
  96         const min = points[0].clone();
  97         const max = points[0].clone();
  98
  99         for (const point of points)
 100         {
 101                 min.set(Math.min(min.x, point.x), Math.min(min.y, point.y));
 102                 max.set(Math.max(max.x, point.x), Math.max(max.y, point.y));
 103         }
 104
 105         return {
 106                 "min": min,
 107                 "max": max
 108         };
 109 }
 110
 111 function getPointsInBoundingBox(boundingBox)
 112 {
 113         const points = [];
 114         for (let x = boundingBox.min.x; x <= boundingBox.max.x; ++x)
 115                 for (let y = boundingBox.min.y; y <= boundingBox.max.y; ++y)
 116                         points.push(new Vector2D(x, y));
 117         return points;
 118 }
 119
 120 /**
 121  * Get the order of the given points to get the shortest closed path (similar to the traveling salesman problem).
 122  * @param {Vectro2D[]} points - Points the path should go through
 123  * @returns {number[]} Ordered indices, same length as points
 124  */
 125 function sortPointsShortestCycle(points)
 126 {
 127         const order = [];
 128         const distances = [];
 129         if (points.length <= 3)
 130         {
 131                 for (let i = 0; i < points.length; ++i)
 132                         order.push(i);
 133
 134                 return order;
 135         }
 136
 137         // Just add the first 3 points
 138         const pointsToAdd = points.map(p => p.clone());
 139         for (let i = 0; i < 3; ++i)
 140         {
 141                 order.push(i);
 142                 pointsToAdd.shift();
 143                 if (i)
 144                         distances.push(points[order[i]].distanceTo(points[order[i - 1]]));
 145         }
 146
 147         distances.push(points[order[0]].distanceTo(points[order[order.length - 1]]));
 148
 149         // Add remaining points so the path lengthens the least
 150         const numPointsToAdd = pointsToAdd.length;
 151         for (let i = 0; i < numPointsToAdd; ++i)
 152         {
 153                 let indexToAddTo;
 154                 let minEnlengthen = Infinity;
 155                 let minDist1 = 0;
 156                 let minDist2 = 0;
 157                 for (let k = 0; k < order.length; ++k)
 158                 {
 159                         const dist1 = pointsToAdd[0].distanceTo(points[order[k]]);
 160                         const dist2 = pointsToAdd[0].distanceTo(points[order[(k + 1) % order.length]]);
 161
 162                         const enlengthen = dist1 + dist2 - distances[k];
 163                         if (enlengthen < minEnlengthen)
 164                         {
 165                                 indexToAddTo = k;
 166                                 minEnlengthen = enlengthen;
 167                                 minDist1 = dist1;
 168                                 minDist2 = dist2;
 169                         }
 170                 }
 171                 order.splice(indexToAddTo + 1, 0, i + 3);
 172                 distances.splice(indexToAddTo, 1, minDist1, minDist2);
 173                 pointsToAdd.shift();
 174         }
 175
 176         return order;
 177 }