feat(grid-iterators): add floodFill(), update deps

thi-ng · Nov 1, 2021 · 4634cf1 · 4634cf1
1 parent c17a556
commit 4634cf1
Show file tree

Hide file tree

Showing 3 changed files with 82 additions and 0 deletions.
diff --git a/packages/grid-iterators/package.json b/packages/grid-iterators/package.json
@@ -35,8 +35,10 @@
         "test": "testament test"
     },
     "dependencies": {
+        "@thi.ng/api": "^8.0.6",
         "@thi.ng/arrays": "^2.0.6",
         "@thi.ng/binary": "^3.0.6",
+        "@thi.ng/bitfield": "^2.0.6",
         "@thi.ng/morton": "^3.0.6",
         "@thi.ng/random": "^3.1.2",
         "@thi.ng/transducers": "^8.0.6"
@@ -88,6 +90,9 @@
         "./diagonal": {
             "import": "./diagonal.js"
         },
+        "./flood-fill": {
+            "import": "./flood-fill.js"
+        },
         "./hilbert": {
             "import": "./hilbert.js"
         },

diff --git a/packages/grid-iterators/src/flood-fill.ts b/packages/grid-iterators/src/flood-fill.ts
@@ -0,0 +1,76 @@
+import type { Predicate } from "@thi.ng/api";
+import { BitField, defBitField } from "@thi.ng/bitfield";
+
+/**
+ * Yields an iterator of 2D coordinates which would flood fill the space in
+ * [0,0]..(width,height) interval, starting at given `x,y`. The given predicate
+ * function is used to select eligible grid indices (e.g. pixels of sorts)
+ *
+ * @param pred
+ * @param x
+ * @param y
+ * @param width
+ * @param height
+ */
+export function* floodFill(
+    pred: Predicate<number>,
+    x: number,
+    y: number,
+    width: number,
+    height: number
+) {
+    x |= 0;
+    y |= 0;
+    if (!pred(y * width + x)) return;
+    const queue: number[][] = [[x, y]];
+    const visited = defBitField(width * height);
+    height--;
+    while (queue.length) {
+        [x, y] = queue.pop()!;
+        yield* partialRow(pred, queue, visited, x, y, width, height, -1);
+        yield* partialRow(pred, queue, visited, x + 1, y, width, height, 1);
+    }
+}
+
+/** @internal */
+function* partialRow(
+    pred: Predicate<number>,
+    queue: number[][],
+    visited: BitField,
+    x: number,
+    y: number,
+    width: number,
+    height1: number,
+    dir: number
+) {
+    let idx = y * width + x;
+    if (visited.at(idx)) return;
+    let idxUp = idx - width;
+    let idxDown = idx + width;
+    let scanUp = false;
+    let scanDown = false;
+    while (x >= 0 && x < width && pred(idx)) {
+        visited.setAt(idx);
+        yield [x, y];
+        if (y > 0) {
+            if (pred(idxUp) && !scanUp) {
+                queue.push([x, y - 1]);
+                scanUp = true;
+            } else {
+                scanUp = false;
+            }
+            idxUp += dir;
+        }
+        if (y < height1) {
+            if (pred(idxDown) && !scanDown) {
+                queue.push([x, y + 1]);
+                scanDown = true;
+            } else {
+                scanDown = false;
+            }
+            idxDown += dir;
+        }
+        x += dir;
+        idx += dir;
+    }
+}
diff --git a/packages/grid-iterators/src/index.ts b/packages/grid-iterators/src/index.ts
@@ -3,6 +3,7 @@ export * from "./column-ends.js";
 export * from "./columns.js";
 export * from "./diagonal.js";
 export * from "./diagonal-ends.js";
+export * from "./flood-fill.js";
 export * from "./hilbert.js";
 export * from "./hvline.js";
 export * from "./interleave.js";