LCOV - code coverage report
 Current view: top level - maps/random/rmgen/placer/noncentered - ConvexPolygonPlacer.js (source / functions) Hit Total Coverage Test: lcov.info Lines: 2 31 6.5 % Date: 2023-04-02 12:52:40 Functions: 0 7 0.0 %
 ` Line data Source code` ``` 1 : /** 2 : * Returns all points on the tilegrid within the convex hull of the given positions. 3 : */ 4 : function ConvexPolygonPlacer(points, failFraction = 0) 5 : { 6 0 : this.polygonVertices = this.getConvexHull(points.map(point => point.clone().round())); 7 0 : this.failFraction = failFraction; 8 : } 9 : 10 6 : ConvexPolygonPlacer.prototype.place = function(constraint) 11 : { 12 0 : let points = []; 13 0 : let count = 0; 14 0 : let failed = 0; 15 : 16 0 : for (let point of getPointsInBoundingBox(getBoundingBox(this.polygonVertices))) 17 : { 18 0 : if (this.polygonVertices.some((vertex, i) => 19 0 : distanceOfPointFromLine(this.polygonVertices[i], this.polygonVertices[(i + 1) % this.polygonVertices.length], point) > 0)) 20 0 : continue; 21 : 22 0 : ++count; 23 : 24 0 : if (g_Map.inMapBounds(point) && constraint.allows(point)) 25 0 : points.push(point); 26 : else 27 0 : ++failed; 28 : } 29 : 30 0 : return failed <= this.failFraction * count ? points : undefined; 31 : }; 32 : 33 : /** 34 : * Applies the gift-wrapping algorithm. 35 : * Returns a sorted subset of the given points that are the vertices of the convex polygon containing all given points. 36 : */ 37 6 : ConvexPolygonPlacer.prototype.getConvexHull = function(points) 38 : { 39 0 : let uniquePoints = []; 40 0 : for (let point of points) 41 0 : if (uniquePoints.every(p => p.x != point.x || p.y != point.y)) 42 0 : uniquePoints.push(point); 43 : 44 : // Start with the leftmost point 45 0 : let result = [uniquePoints.reduce((leftMost, point) => point.x < leftMost.x ? point : leftMost, uniquePoints[0])]; 46 : 47 : // Add the vector most left of the most recently added point until a cycle is reached 48 0 : while (result.length < uniquePoints.length) 49 : { 50 : let nextLeftmostPoint; 51 : 52 : // Of all points, find the one that is leftmost 53 0 : for (let point of uniquePoints) 54 : { 55 0 : if (point == result[result.length - 1]) 56 0 : continue; 57 : 58 0 : if (!nextLeftmostPoint || distanceOfPointFromLine(nextLeftmostPoint, result[result.length - 1], point) <= 0) 59 0 : nextLeftmostPoint = point; 60 : } 61 : 62 : // If it was a known one, then the remaining points are inside this hull 63 0 : if (result.indexOf(nextLeftmostPoint) != -1) 64 0 : break; 65 : 66 0 : result.push(nextLeftmostPoint); 67 : } 68 : 69 0 : return result; 70 : }; ```

 Generated by: LCOV version 1.14