1 const g_TileVertices = deepfreeze([
8 const g_AdjacentCoordinates = deepfreeze([
19 function diskArea(radius)
21 return Math.PI * Math.square(radius);
25 * Returns the angle of the vector between point 1 and point 2.
26 * The angle is counterclockwise from the positive x axis.
28 function getAngle(x1, z1, x2, z2)
30 return Math.atan2(z2 - z1, x2 - x1);
34 * Get pointCount points equidistantly located on a circle.
35 * @param {Vector2D} center
37 function distributePointsOnCircle(pointCount, startAngle, radius, center)
39 return distributePointsOnCircularSegment(pointCount, Math. PI * 2, startAngle, radius, center);
42 function distributePointsOnCircularSegment(pointCount, maxAngle, startAngle, radius, center)
47 for (let i = 0; i < pointCount; ++i)
49 angle[i] = startAngle + maxAngle * i / pointCount;
50 points[i] = Vector2D.add(center, new Vector2D(radius, 0).rotate(-angle[i]));
53 return [points, angle];
57 * Returns the shortest distance from a point to a line.
58 * The sign of the return value determines the direction!
60 * @param {Vector2D} - lineStart, lineEnd, point
62 function distanceOfPointFromLine(lineStart, lineEnd, point)
64 // Since the cross product is the area of the parallelogram with the vectors for sides and
65 // one of the two vectors having length one, that area equals the distance between the points.
66 return Vector2D.sub(lineStart, lineEnd).normalize().cross(Vector2D.sub(point, lineEnd));
70 * Returns whether the two lines of the given width going through the given Vector2D intersect.
72 function testLineIntersection(start1, end1, start2, end2, width)
74 let start1end1 = Vector2D.sub(start1, end1);
75 let start2end2 = Vector2D.sub(start2, end2);
76 let start1start2 = Vector2D.sub(start1, start2);
79 Math.abs(distanceOfPointFromLine(start1, end1, start2)) < width ||
80 Math.abs(distanceOfPointFromLine(start1, end1, end2)) < width ||
81 Math.abs(distanceOfPointFromLine(start2, end2, start1)) < width ||
82 Math.abs(distanceOfPointFromLine(start2, end2, end1)) < width ||
83 start1end1.cross(start1start2) * start1end1.cross(Vector2D.sub(start1, end2)) <= 0 &&
84 start2end2.cross(start1start2) * start2end2.cross(Vector2D.sub(start2, end1)) >= 0);
88 * Returns the topleft and bottomright coordinate of the given two points.
90 function getBoundingBox(points)
92 let min = points[0].clone();
93 let max = points[0].clone();
95 for (let point of points)
97 min.set(Math.min(min.x, point.x), Math.min(min.y, point.y));
98 max.set(Math.max(max.x, point.x), Math.max(max.y, point.y));
107 function getPointsInBoundingBox(boundingBox)
110 for (let x = boundingBox.min.x; x <= boundingBox.max.x; ++x)
111 for (let y = boundingBox.min.y; y <= boundingBox.max.y; ++y)
112 points.push(new Vector2D(x, y));
117 * Sorts the given (x, y) points so that the distance between neighboring points becomes minimal (similar to the traveling salesman problem).
119 function sortPointsShortestCycle(points)
123 if (points.length <= 3)
125 for (let i = 0; i < points.length; ++i)
131 // Just add the first 3 points
132 let pointsToAdd = points.map(p => p.clone());
133 for (let i = 0; i < 3; ++i)
136 pointsToAdd.shift(i);
138 distances.push(Math.euclidDistance2D(points[order[i]].x, points[order[i]].y, points[order[i - 1]].x, points[order[i - 1]].y));
141 distances.push(points[order[0]].distanceTo(points[order[order.length - 1]]));
143 // Add remaining points so the path lengthens the least
144 let numPointsToAdd = pointsToAdd.length;
145 for (let i = 0; i < numPointsToAdd; ++i)
148 let minEnlengthen = Infinity;
151 for (let k = 0; k < order.length; ++k)
153 let dist1 = pointsToAdd[0].distanceTo(points[order[k]]);
154 let dist2 = pointsToAdd[0].distanceTo(points[order[(k + 1) % order.length]]);
156 let enlengthen = dist1 + dist2 - distances[k];
157 if (enlengthen < minEnlengthen)
160 minEnlengthen = enlengthen;
165 order.splice(indexToAddTo + 1, 0, i + 3);
166 distances.splice(indexToAddTo, 1, minDist1, minDist2);