Scanline fill - как обеспечить покрытие всего полигона?

Question

Я пытаюсь эффективно "разбить" объекты GeoJSON на выровненные квадратные плитки любого размера, например:

1. Покрыт весь многоугольник или многоугольник (в многоугольнике нет области)это не имеет плитки, покрывающей его).
2. Нет плитки, которая не покрывает какую-либо область многоугольника.

Я пытался использовать библиотеки, такие как квадратная сетка Turfjs (https://turfjs.org/docs/#squareGrid),, но операция маски неоправданно медленная - она ​​занимает минуты для больших областей с небольшим размером квадрата. Она также не охватывает всю область многоугольника - тольковнутреннее.

Я пытаюсь использовать алгоритм 1011 * scanline fill , чтобы сделать это, так как мое исследование показало, что оно невероятно быстро и решает эту проблему, но не всегда охватываетвся область - она ​​покрывает только внутреннюю часть и иногда оставляет углы:

или оставляет все горизонтальные области вне:

Мой сканлайн работаетЭто обычная заливка строки, но она работает на основе чисел с плавающей точкой, а не целых чисел.Он выделяет начальную позицию x так, что она будет находиться на линии сетки (Math.floor ((x - polygonLeftBoundary) / cellWidth) * cellWidth)

Вот моя реализация (с использованием TypeScript):

public partitionIntoGrid(polygon, cellSizeKm) {
    const bounds = this.getBoundingBox(polygon);
    const left = bounds[0];
    const cellDistance = this.distanceToDegrees(cellSizeKm);

    const grid = [];

    if (polygon.geometry.type === 'Polygon') {
      polygon = [polygon.geometry.coordinates];
    } else {
      polygon = polygon.geometry.coordinates;
    }

    polygon.forEach(poly => {
      poly = poly[0];

      const edges = poly.reduce((acc, vertex, vertexIndex) => {
        acc.push([vertex, poly[vertexIndex === poly.length - 1 ? 0 : vertexIndex + 1]]);
        return acc;
      }, []);

      let edgeTable = edges
        .map(edge => {
          const x = Math.floor((edge[0][1] < edge[1][1] ? edge[0][0] : edge[1][0]) / cellDistance) * cellDistance;
          return {
            yMin: Math.min(edge[0][1], edge[1][1]), // minumum y coordinate
            yMax: Math.max(edge[0][1], edge[1][1]), // maximum y coordinate
            originalX: x,
            x, // lower coordinate's x
            w: (edge[0][0] - edge[1][0]) / (edge[0][1] - edge[1][1]), // change of edge per y
          };
        })
        .filter(edge => !isNaN(edge.w))
        .sort((a, b) => a.yMax - b.yMax);

      let activeEdgeTable = [];

      let y = edgeTable[0].yMin;
      const originalY = y;

      while (edgeTable.length || activeEdgeTable.length) {
        // move edges from edge table under y into the active edge table
        edgeTable = edgeTable.filter(edge => {
          if (edge.yMin <= y) {
            activeEdgeTable.push(edge);
            return false;
          }
          return true;
        });

        // remove edges from the active edge table whose yMax is smaller than y
        activeEdgeTable = activeEdgeTable.filter(edge => edge.yMax >= y);
        // sort active edge table by x
        activeEdgeTable = activeEdgeTable.sort((a, b) => a.x - b.x);

        // fill pixels between even and odd adjacent pairs of intersections in active edge table
        const pairs = Array.from({ length: activeEdgeTable.length / 2 }, (v, k) => [
          activeEdgeTable[k * 2], activeEdgeTable[k * 2 + 1],
        ]);
        pairs.forEach(pair => {
          for (let x = pair[0].x; x <= pair[1].x; x += cellDistance) {
            grid.push(bboxPolygon([
              x, // minX
              y, // minY
              x + cellDistance, // maxX
              y + cellDistance, // maxY
            ]));
          }
        });

        // increment y
        y += cellDistance;

        // update x for all edges in active edge table
        activeEdgeTable.forEach(edge => edge.x += edge.w * cellDistance);
        // activeEdgeTable.forEach(edge => edge.x = edge.originalX + Math.floor((edge.w * (y - originalY) / cellDistance)) * cellDistance);
      }
    });

    return grid;
  }

Я пытался добавить градиент, но пока не добирался, поэтому строка прокомментирована:

activeEdgeTable.forEach(edge => edge.x = edge.originalX + Math.floor((edge.w * (y - originalY) / cellDistance)) * cellDistance);