Line data Source code
1 6 : 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 6 : 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 0 : 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 0 : 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 0 : 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 0 : let points = [];
48 0 : let angle = [];
49 0 : pointCount = Math.round(pointCount);
50 :
51 0 : for (let i = 0; i < pointCount; ++i)
52 : {
53 0 : angle[i] = startAngle + maxAngle * i / Math.max(1, pointCount - 1);
54 0 : points[i] = Vector2D.add(center, new Vector2D(radius, 0).rotate(-angle[i]));
55 : }
56 :
57 0 : 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 0 : 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 0 : let start1end1 = Vector2D.sub(start1, end1);
79 0 : let start2end2 = Vector2D.sub(start2, end2);
80 0 : let start1start2 = Vector2D.sub(start1, start2);
81 :
82 0 : 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 4 : let min = points[0].clone();
97 4 : let max = points[0].clone();
98 :
99 4 : for (let point of points)
100 : {
101 8 : min.set(Math.min(min.x, point.x), Math.min(min.y, point.y));
102 8 : max.set(Math.max(max.x, point.x), Math.max(max.y, point.y));
103 : }
104 :
105 4 : return {
106 : "min": min,
107 : "max": max
108 : };
109 : }
110 :
111 : function getPointsInBoundingBox(boundingBox)
112 : {
113 4 : let points = [];
114 4 : for (let x = boundingBox.min.x; x <= boundingBox.max.x; ++x)
115 18 : for (let y = boundingBox.min.y; y <= boundingBox.max.y; ++y)
116 92 : points.push(new Vector2D(x, y));
117 4 : 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 0 : let order = [];
128 0 : let distances = [];
129 0 : if (points.length <= 3)
130 : {
131 0 : for (let i = 0; i < points.length; ++i)
132 0 : order.push(i);
133 :
134 0 : return order;
135 : }
136 :
137 : // Just add the first 3 points
138 0 : let pointsToAdd = points.map(p => p.clone());
139 0 : for (let i = 0; i < 3; ++i)
140 : {
141 0 : order.push(i);
142 0 : pointsToAdd.shift();
143 0 : if (i)
144 0 : distances.push(points[order[i]].distanceTo(points[order[i - 1]]));
145 : }
146 :
147 0 : distances.push(points[order[0]].distanceTo(points[order[order.length - 1]]));
148 :
149 : // Add remaining points so the path lengthens the least
150 0 : let numPointsToAdd = pointsToAdd.length;
151 0 : for (let i = 0; i < numPointsToAdd; ++i)
152 : {
153 : let indexToAddTo;
154 0 : let minEnlengthen = Infinity;
155 0 : let minDist1 = 0;
156 0 : let minDist2 = 0;
157 0 : for (let k = 0; k < order.length; ++k)
158 : {
159 0 : let dist1 = pointsToAdd[0].distanceTo(points[order[k]]);
160 0 : let dist2 = pointsToAdd[0].distanceTo(points[order[(k + 1) % order.length]]);
161 :
162 0 : let enlengthen = dist1 + dist2 - distances[k];
163 0 : if (enlengthen < minEnlengthen)
164 : {
165 0 : indexToAddTo = k;
166 0 : minEnlengthen = enlengthen;
167 0 : minDist1 = dist1;
168 0 : minDist2 = dist2;
169 : }
170 : }
171 0 : order.splice(indexToAddTo + 1, 0, i + 3);
172 0 : distances.splice(indexToAddTo, 1, minDist1, minDist2);
173 0 : pointsToAdd.shift();
174 : }
175 :
176 0 : return order;
177 : }
|
