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             : };