feat(poisson): add stratifiedGrid(), restructure pkg

thi-ng · May 29, 2020 · 62cd31a · 62cd31a
1 parent 353baff
commit 62cd31a
Show file tree

Hide file tree

Showing 4 changed files with 169 additions and 124 deletions.
diff --git a/packages/poisson/src/api.ts b/packages/poisson/src/api.ts
@@ -0,0 +1,95 @@
+import type { ISpatialSet } from "@thi.ng/geom-api";
+import type { IRandom } from "@thi.ng/random";
+import type { ReadonlyVec, Vec } from "@thi.ng/vectors";
+
+export type PointGenerator = (rnd: IRandom) => Vec;
+export type DensityFunction = (pos: ReadonlyVec) => number;
+
+/**
+ * Options for {@link samplePoisson}.
+ */
+export interface PoissonOpts {
+    /**
+     * Point generator function. Responsible for producing a new
+     * candidate point within user defined bounds using provided RNG.
+     */
+    points: PointGenerator;
+    /**
+     * Density field function. Called for each new candidate point
+     * created by point generator and should return the poisson disc
+     * exclusion radius for the given point location. The related
+     * candidate point can only be placed if no other points are already
+     * existing within the given radius/distance. If this option is
+     * given as number, uses this value to create a uniform distance
+     * field.
+     */
+    density: DensityFunction | number;
+    /**
+     * Spatial indexing implementation for nearest neighbor searches of
+     * candidate points. Currently only {@link @thi.ng/geom-accel} types
+     * are supported and must be pre-initialized. The data structure is
+     * used to store all successful sample points.
+     *
+     * Pre-seeding the data structure allows already indexed points to
+     * participate in the sampling process and so can be used to define
+     * exclusion zones. It also can be used as mechanism for progressive
+     * sampling, i.e. generating a large number of samples and
+     * distributing the process over multiple invocations of smaller
+     * sample sizes (see `max` option) to avoid long delays.
+     */
+    index: ISpatialSet<ReadonlyVec>;
+    /**
+     * Max number of samples to produce. Must be given, no default.
+     */
+    max: number;
+    /**
+     * Step distance for the random walk each failed candidate point is
+     * undergoing. This distance should be adjusted depending on overall
+     * sampling area/bounds.
+     *
+     * @defaultValue 1
+     */
+    jitter?: number;
+    /**
+     * Number of random walk steps performed before giving up on a
+     * candidate point. Increasing this value improves overall quality.
+     *
+     * @defaultValue 1
+     */
+    iter?: number;
+    /**
+     * Number of allowed failed consecutive candidate points before
+     * stopping entire sampling process (most likely due to not being
+     * able to place any further points). As with the `iter` param,
+     * increasing this value improves overall quality, especially in
+     * dense regions with small radii.
+     *
+     * @defaultValue 500
+     */
+    quality?: number;
+    /**
+     * Random number generator instance.
+     *
+     * @defaultValue {@link @thi.ng/random#SYSTEM} (aka Math.random)
+     */
+    rnd?: IRandom;
+}
+
+export interface StratifiedGridOpts {
+    /**
+     * nD vector defining grid size (in cells)
+     */
+    dim: ReadonlyVec;
+    /**
+     * Number of samples per grid cell
+     *
+     * @defaultValue 1
+     */
+    samples?: number;
+    /**
+     * Random number generator instance.
+     *
+     * @defaultValue {@link @thi.ng/random#SYSTEM} (aka Math.random)
+     */
+    rnd?: IRandom;
+}
diff --git a/packages/poisson/src/index.ts b/packages/poisson/src/index.ts
@@ -1,124 +1,3 @@
-import { isNumber } from "@thi.ng/checks";
-import { IRandom, SYSTEM } from "@thi.ng/random";
-import { jitter as _jitter, ReadonlyVec, Vec } from "@thi.ng/vectors";
-import type { ISpatialSet } from "@thi.ng/geom-api";
-
-export type PointGenerator = (rnd: IRandom) => Vec;
-export type DensityFunction = (pos: ReadonlyVec) => number;
-
-/**
- * Options for {@link samplePoisson}.
- */
-export interface PoissonOpts {
-    /**
-     * Point generator function. Responsible for producing a new
-     * candidate point within user defined bounds using provided RNG.
-     */
-    points: PointGenerator;
-    /**
-     * Density field function. Called for each new candidate point
-     * created by point generator and should return the poisson disc
-     * exclusion radius for the given point location. The related
-     * candidate point can only be placed if no other points are already
-     * existing within the given radius/distance. If this option is
-     * given as number, uses this value to create a uniform distance
-     * field.
-     */
-    density: DensityFunction | number;
-    /**
-     * Spatial indexing implementation for nearest neighbor searches of
-     * candidate points. Currently only
-     * {@link @thi.ng/geom-accel#KdTree} is available and must be
-     * pre-initialized to given dimensions prior to calling
-     * {@link samplePoisson}.
-     *
-     * The data structure is used to store all successful sample points
-     * (as keys) incl. their exclusion radius (as value).
-     *
-     * Furthermore, pre-seeding the data structure allows already
-     * indexed points to participate in the sampling process and act as
-     * exclusion zones. It also can be used as mechanism for progressive
-     * sampling, i.e. generating a large number of samples and
-     * distributing the process over multiple invocations of smaller
-     * sample sizes (see `max` option) to avoid long delays.
-     */
-    index: ISpatialSet<ReadonlyVec>;
-    /**
-     * Max number of samples to produce. Must be given, no default.
-     */
-    max: number;
-    /**
-     * Step distance for the random walk each failed candidate point is
-     * undergoing. This distance should be adjusted depending on overall
-     * sampling area/bounds.
-     *
-     * @defaultValue 1
-     */
-    jitter?: number;
-    /**
-     * Number of random walk steps performed before giving up on a
-     * candidate point. Increasing this value improves overall quality.
-     *
-     * @defaultValue 1
-     */
-    iter?: number;
-    /**
-     * Number of allowed failed consecutive candidate points before
-     * stopping entire sampling process (most likely due to not being
-     * able to place any further points). As with the `iter` param,
-     * increasing this value improves overall quality, especially in
-     * dense regions with small radii.
-     *
-     * @defaultValue 500
-     */
-    quality?: number;
-    /**
-     * Random number generator instance.
-     *
-     * @defaultValue {@link @thi.ng/random#SYSTEM} (aka Math.random)
-     */
-    rnd?: IRandom;
-}
-
-/**
- *
- * @param opts -
- */
-export const samplePoisson = (_opts: PoissonOpts) => {
-    const opts = {
-        rnd: SYSTEM,
-        iter: 1,
-        jitter: 1,
-        quality: 500,
-        ..._opts
-    };
-    const { points, index, rnd, jitter, quality, density: _d } = opts;
-    const density = isNumber(_d) ? () => _d : _d;
-    const iter = Math.max(opts.iter, 1);
-    const samples: Vec[] = [];
-    let failed = 0;
-    let pos: Vec;
-    let d: number;
-    let i: number;
-
-    outer: for (let num = opts.max; num > 0; ) {
-        pos = points(rnd);
-        d = density(pos);
-        i = iter;
-        while (i-- > 0) {
-            if (!index.has(pos, d)) {
-                index.add(pos, 0);
-                samples.push(pos);
-                failed = 0;
-                num--;
-                continue outer;
-            }
-            _jitter(null, pos, jitter, rnd);
-        }
-        if (++failed > quality) {
-            break;
-        }
-    }
-
-    return samples;
-};
+export * from "./api";
+export * from "./poisson";
+export * from "./stratified";
diff --git a/packages/poisson/src/poisson.ts b/packages/poisson/src/poisson.ts
@@ -0,0 +1,49 @@
+import { isNumber } from "@thi.ng/checks";
+import { SYSTEM } from "@thi.ng/random";
+import { jitter as _jitter, Vec } from "@thi.ng/vectors";
+import { PoissonOpts } from "./api";
+
+/**
+ * Produces a number of Poisson-disk samples based on given
+ * configuration.
+ *
+ * @param opts -
+ */
+export const samplePoisson = (_opts: PoissonOpts) => {
+    const opts = {
+        rnd: SYSTEM,
+        iter: 1,
+        jitter: 1,
+        quality: 500,
+        ..._opts,
+    };
+    const { points, index, rnd, jitter, quality, density: _d } = opts;
+    const density = isNumber(_d) ? () => _d : _d;
+    const iter = Math.max(opts.iter, 1);
+    const samples: Vec[] = [];
+    let failed = 0;
+    let pos: Vec;
+    let d: number;
+    let i: number;
+
+    outer: for (let num = opts.max; num > 0; ) {
+        pos = points(rnd);
+        d = density(pos);
+        i = iter;
+        while (i-- > 0) {
+            if (!index.has(pos, d)) {
+                index.add(pos, 0);
+                samples.push(pos);
+                failed = 0;
+                num--;
+                continue outer;
+            }
+            _jitter(null, pos, jitter, rnd);
+        }
+        if (++failed > quality) {
+            break;
+        }
+    }
+
+    return samples;
+};
diff --git a/packages/poisson/src/stratified.ts b/packages/poisson/src/stratified.ts
@@ -0,0 +1,22 @@
+import { SYSTEM } from "@thi.ng/random";
+import { mapcat, rangeNd, repeatedly } from "@thi.ng/transducers";
+import { add, random } from "@thi.ng/vectors";
+import { StratifiedGridOpts } from "./api";
+
+/**
+ * Yields iterator of nD point samples of for given stratified grid
+ * config.
+ *
+ * @remarks
+ * All samples will be in `[[0,0,...] ...[dimx,dimy,...])` interval
+ *
+ * @param opts
+ */
+export const stratifiedGrid = (opts: StratifiedGridOpts) => {
+    const { rnd, samples } = { samples: 1, rnd: SYSTEM, ...opts };
+    const tmp = new Array<number>(opts.dim.length);
+    return mapcat(
+        (p) => repeatedly(() => add([], p, random(tmp, 0, 1, rnd)), samples),
+        rangeNd(opts.dim)
+    );
+};