@4bitlabs/quadtree - npm Package Compare versions

Comparing version 1.0.5 to 1.1.0

dist/factory.d.ts

@@ -1,5 +0,57 @@
-import { qTreeOptions } from './q-tree';
 import { Bounds } from './bounds';
 import { Quadtree } from './quadtree';
+import { qTreeOptions } from './q-tree-options';
+/**
+ * Create a quadtree for a given area.
+ *
+ * @param area The region-bounds of this quadtree.
+ * @param boundsFn Child bounds predicate.
+ * @param options
+ * @typeParam T The type of children of this quadtree contains.
+ *
+ * @example A simple quadtree
+ *
+ * ```ts
+ * interface Rectangle {
+ *   x: number;
+ *   y: number;
+ *   width: number;
+ *   height: number;
+ * }
+ *
+ * const rectBounds = ({ x, y, width, height }: Rectangle) =>
+ *   [x, y, x + width, r.y + height];
+ *
+ * const qt = quadtree([0,0,1000,1000], rectBounds);
+ *
+ * // Add a rectangle
+ * qt.insert([20, 20, 50, 50]);
+ *
+ * // Collect items
+ * const results = qt.collect([0, 0, 100, 100]);
+ * ```
+ *
+ * @example Using advanced options
+ *
+ * ```ts
+ * const qt = quadtree(
+ *   [0,0,1000,1000],
+ *   rectBounds,
+ *   {
+ *     maxDepth: 4,
+ *     maxChildren: 50
+ *   }
+ * );
+ * ```
+ *
+ * @example Using DOMRect with quadtree
+ *
+ * ```ts
+ * const qt = quadtree<DOMRect>(
+ *   [0, 0, 1000, 1000],
+ *   ({ left, top, right, bottom }) => [left, top, right, bottom],
+ * );
+ * ```
+ */
 export declare function quadtree<T extends object>(area: Readonly<Bounds>, boundsFn: (it: T) => Bounds, options?: qTreeOptions): Quadtree<T>;
 //# sourceMappingURL=factory.d.ts.map

dist/factory.js

@@ -5,2 +5,54 @@ "use strict";
 const q_tree_1 = require("./q-tree");
+/**
+ * Create a quadtree for a given area.
+ *
+ * @param area The region-bounds of this quadtree.
+ * @param boundsFn Child bounds predicate.
+ * @param options
+ * @typeParam T The type of children of this quadtree contains.
+ *
+ * @example A simple quadtree
+ *
+ * ```ts
+ * interface Rectangle {
+ *   x: number;
+ *   y: number;
+ *   width: number;
+ *   height: number;
+ * }
+ *
+ * const rectBounds = ({ x, y, width, height }: Rectangle) =>
+ *   [x, y, x + width, r.y + height];
+ *
+ * const qt = quadtree([0,0,1000,1000], rectBounds);
+ *
+ * // Add a rectangle
+ * qt.insert([20, 20, 50, 50]);
+ *
+ * // Collect items
+ * const results = qt.collect([0, 0, 100, 100]);
+ * ```
+ *
+ * @example Using advanced options
+ *
+ * ```ts
+ * const qt = quadtree(
+ *   [0,0,1000,1000],
+ *   rectBounds,
+ *   {
+ *     maxDepth: 4,
+ *     maxChildren: 50
+ *   }
+ * );
+ * ```
+ *
+ * @example Using DOMRect with quadtree
+ *
+ * ```ts
+ * const qt = quadtree<DOMRect>(
+ *   [0, 0, 1000, 1000],
+ *   ({ left, top, right, bottom }) => [left, top, right, bottom],
+ * );
+ * ```
+ */
 function quadtree(area, boundsFn, options = {}) {
@@ -7,0 +59,0 @@ const quadCache = new WeakMap();

dist/index.d.ts

@@ -0,4 +1,32 @@
+/**
+ * A simple 2D quadtree (2×2 spatial division) for fast, efficient spatial queries.
+ *
+ * ![Quadtree split illustration][quadtree-split-img]
+ *
+ * [quadtree-split-img]: https://github.com/32bitkid/4bitlabs.spatial/blob/main/quadtree-split.png?raw=true
+
+ *
+ * @example
+ *
+ * An _easy_ way to use this within a browser is to use the built-in {@link !DOMRect} class, consider:
+ *
+ * ```ts
+ * import { quadtree, type Bounds } from '@4bitlabs/quadtree';
+ *
+ * const rectBounds = (r: DOMRect) => [r.left, r.top, r.right, r.bottom];
+ *
+ * const space = quadtree<DOMRect>([0, 0, 1000, 1000], rectBounds);
+ * space.insert(new DOMRect(25, 25, 50, 50));
+ *
+ * const matches = space.search([20, 20, 80, 80]);
+ * ```
+ *
+ * @see {@link quadtree}
+ *
+ * @module
+ */
 export type { Quadtree } from './quadtree';
 export type { Bounds } from './bounds';
+export type { qTreeOptions } from './q-tree-options';
 export { quadtree } from './factory';
 //# sourceMappingURL=index.d.ts.map

dist/q-tree.d.ts

 import { Bounds } from './bounds';
 import { Quadtree } from './quadtree';
-export interface qTreeOptions {
-    maxDepth?: number;
-    maxChildren?: number;
-}
+import { qTreeOptions } from './q-tree-options';
 export declare class qTree<T extends object> implements Quadtree<T> {
+    private readonly _bounds;
     private readonly depth;
@@ -17,7 +15,7 @@ private readonly maxChildren;
     private isSplit;
-    constructor([x0, y0, x1, y1]: Readonly<Bounds>, options: qTreeOptions, boundFn: (item: T) => Bounds, quadCache: WeakMap<T, qTree<T>>, depth?: number);
-    clear(): void;
+    constructor(bounds: Readonly<Bounds>, options: qTreeOptions, boundFn: (item: T) => Bounds, quadCache: WeakMap<T, qTree<T>>, depth?: number);
+    get size(): number;
+    get bounds(): Readonly<Bounds>;
     insert(item: Readonly<T>): void;
     private tryChildInsert;
-    remove(item: Readonly<T>): boolean;
     collectAll(result?: Readonly<T>[]): Readonly<T>[];
@@ -27,4 +25,5 @@ collect(area: Readonly<Bounds>, result?: Readonly<T>[]): Readonly<T>[];
     search(area: Readonly<Bounds>): Generator<Readonly<T>, void, undefined>;
-    size(): number;
+    remove(item: Readonly<T>): boolean;
+    clear(): void;
 }
 //# sourceMappingURL=q-tree.d.ts.map

dist/q-tree.js

@@ -6,9 +6,11 @@ "use strict";
 class qTree {
-    constructor([x0, y0, x1, y1], options, boundFn, quadCache, depth = 0) {
+    constructor(bounds, options, boundFn, quadCache, depth = 0) {
         const { maxDepth = 7, maxChildren = 10 } = options;
         this.maxDepth = maxDepth;
         this.maxChildren = maxChildren;
+        this._bounds = bounds;
         this.boundsFn = boundFn;
         this.quadCache = quadCache;
         this.depth = depth;
+        const [x0, y0, x1, y1] = bounds;
         const midX = (x0 + x1) / 2;
@@ -26,12 +28,14 @@ const midY = (y0 + y1) / 2;
     }
-    clear() {
-        this.items.clear();
+    get size() {
+        let count = this.items.size;
         for (let i = 0; i < 4; i++) {
             const child = this.children[i];
-            if (!child)
-                continue;
-            child.clear();
-            this.children[i] = null;
+            if (child)
+                count += child.size;
         }
+        return count;
     }
+    get bounds() {
+        return this._bounds;
+    }
     insert(item) {
@@ -54,3 +58,3 @@ if (!this.isSplit && this.items.size + 1 > this.maxChildren) {
             const childRect = this.childAreas[i];
-            const rect = this.boundsFn(item);
+            const rect = this.boundsFn.call(item, item);
             if ((0, bounds_1.contains)(childRect, rect)) {
@@ -67,14 +71,2 @@ let child = this.children[i];
     }
-    remove(item) {
-        if (this.items.has(item)) {
-            this.items.delete(item);
-            this.quadCache.delete(item);
-            // TODO handle cleanup
-            return true;
-        }
-        const quad = this.quadCache.get(item);
-        if (!quad)
-            return false;
-        return quad.remove(item);
-    }
     collectAll(result = []) {
@@ -93,3 +85,3 @@ for (const r of this.items)
         for (const item of this.items) {
-            const rect = this.boundsFn(item);
+            const rect = this.boundsFn.call(item, item);
             if ((0, bounds_1.overlaps)(area, rect))
@@ -124,3 +116,3 @@ result.push(item);
         for (const item of this.items) {
-            const rect = this.boundsFn(item);
+            const rect = this.boundsFn.call(item, item);
             if ((0, bounds_1.overlaps)(area, rect))
@@ -143,10 +135,25 @@ yield item;
     }
-    size() {
-        let count = this.items.size;
+    remove(item) {
+        if (this.items.has(item)) {
+            this.items.delete(item);
+            this.quadCache.delete(item);
+            // TODO handle cleanup
+            return true;
+        }
+        const quad = this.quadCache.get(item);
+        if (!quad)
+            return false;
+        return quad.remove(item);
+    }
+    clear() {
+        for (const item of this.items)
+            this.quadCache.delete(item);
+        this.items.clear();
         for (let i = 0; i < 4; i++) {
             const child = this.children[i];
-            if (child)
-                count += child.size();
+            if (!child)
+                continue;
+            child.clear();
+            this.children[i] = null;
         }
-        return count;
     }
@@ -153,0 +160,0 @@ }

dist/quadtree.d.ts

 import { Bounds } from './bounds';
+/**
+ * @typeParam T The type of children of this {@link Quadtree} contains.
+ */
 export interface Quadtree<T> {
-    clear(): void;
+    /**
+     * Count the total number of items in the {@link Quadtree}.
+     */
+    readonly size: number;
+    /**
+     * The bounds of this {@link Quadtree}.
+     */
+    readonly bounds: Readonly<Bounds>;
+    /**
+     * Insert an item into the {@link Quadtree}.
+     *
+     * @param item The item to insert.
+     */
     insert(item: Readonly<T>): void;
-    remove(item: Readonly<T>): boolean;
-    size(): number;
-    all(): Generator<Readonly<T>, void, undefined>;
+    /**
+     * Search the {@link Quadtree} for all items that intersect with the search area.
+     *
+     * @param area The search area of the query.
+     * @returns An iterator of matched items.
+     */
+    search(area: Readonly<Bounds>): IterableIterator<Readonly<T>>;
+    /**
+     * Return all the items within the {@link Quadtree}.
+     *
+     * @returns An iterator of all items.
+     */
+    all(): IterableIterator<Readonly<T>>;
+    /**
+     * Collect items in the {@link Quadtree} that intersect with the search area into result.
+     *
+     * @param area The search area of the query.
+     * @param result An optional array to collect items. Defaults to an empty array.
+     * @returns A reference to the collection array.
+     */
     collect(area: Readonly<Bounds>, result?: Readonly<T>[]): Readonly<T>[];
+    /**
+     * Collect all items in the {@link Quadtree} into result.
+     *
+     * @param result An optional array to collect items. Defaults to an empty array.
+     * @returns A reference to the collection array.
+     */
     collectAll(result?: Readonly<T>[]): Readonly<T>[];
-    search(area: Readonly<Bounds>): Generator<Readonly<T>, void, undefined>;
+    /**
+     * Remove an item from the {@link Quadtree}.
+     *
+     * @param item The item to remove.
+     */
+    remove(item: Readonly<T>): boolean;
+    /**
+     * Clear all items from the {@link Quadtree} and reset the tree back to its initial state.
+     */
+    clear(): void;
 }
 //# sourceMappingURL=quadtree.d.ts.map

package.json

 {
   "name": "@4bitlabs/quadtree",
-  "version": "1.0.5",
-  "description": "A basic 2D quadtree (2×2 spatial division) for fast, efficient spatial queries",
+  "version": "1.1.0",
+  "description": "A simple 2D quadtree (2×2 spatial division) for fast, efficient spatial queries",
   "main": "./dist/index.js",
   "types": "./dist/index.d.ts",
-  "homepage": "https://github.com/32bitkid/4bitlabs.spatial/tree/main/libs/quadtree",
+  "homepage": "https://32bitkid.github.io/4bitlabs.spatial/modules/_4bitlabs_quadtree.html",
   "bugs": "https://github.com/32bitkid/4bitlabs.spatial/issues",
@@ -31,3 +31,3 @@ "repository": {
   ],
-  "gitHead": "93c6c7664155c825e0a3a89c86c539af69165d4e"
+  "gitHead": "508ef3fac55c3fe14078023b365c51e596177cdd"
 }

README.md

 # `@4bitlabs/quadtree` [![License][license]][npm] [![NPM Version][version]][npm] [![NPM Downloads][dl]][npm]
 
-![Quadtree split illustration](/docs/public/quadtree-split.png)
+A simple 2D quadtree (2×2 spatial division) for fast, efficient spatial queries.
 
+![Quadtree split illustration][quadtree-split-img]
+
 ## Installing
@@ -19,18 +21,36 @@
 
+## Documentation
+
+Full documentation for the library can be found [here](https://32bitkid.github.io/4bitlabs.spatial/modules/_4bitlabs_quadtree.html)
+
 ## Usage
 
+An _easy_ way to use this within a browser is to use the built-in `DOMRect` class, consider:
+
 ```ts
-import { quadtree } from '@4bitlabs/quadtree';
+import { quadtree, type Bounds } from '@4bitlabs/quadtree';
 
-interface Entity {
-  /* whatever you like */
-}
+const rectBounds = (r: DOMRect) => [r.left, r.top, r.right, r.bottom];
 
-type Bounds = [left: number, top: number, right: number, bottom: number];
+const space = quadtree<DOMRect>([0, 0, 1000, 1000], rectBounds);
+space.insert(new DOMRect(25, 25, 50, 50));
 
-function getBounds(it: Entity): Bounds {
-  /* determine bounds for entity, specified in  */
+const matches = space.search([20, 20, 80, 80]);
+```
+
+Or with custom objects:
+
+```ts
+import { quadtree, type Bounds } from '@4bitlabs/quadtree';
+
+class Shape {
+  bounds(): Bounds {
+    /* TODO implement return bounds */
+    return [0, 0, 0, 0];
+  }
 }
 
-const space = quadtree<Entity>([0, 0, 1000, 1000], Entity.prototype.getBounds);
+const space = quadtree<Shape>([0, 0, 1000, 1000], Shape.prototype.bounds);
+space.insert(new Shape());
+const matches = space.search([20, 20, 80, 80]);
 ```
@@ -48,3 +68,3 @@
 ```ts
-const space = quadtree<Entity>([0, 0, 1000, 1000], Entity.prototype.getBounds, {
+const space = quadtree<DOMRect>([0, 0, 1000, 1000], rectBounds, {
   maxDepth: 5,
@@ -55,2 +75,6 @@ maxChildren: 50,
 
+## License
+
+[ISC](https://github.com/32bitkid/4bitlabs.spatial/blob/HEAD/libs/vector/LICENSE.txt)
+
 [quadtree]: https://en.wikipedia.org/wiki/Quadtree
@@ -61,1 +85,2 @@ [npm]: https://www.npmjs.com/package/@4bitlabs/quadtree
 [dl]: https://img.shields.io/npm/dy/%404bitlabs%2Fquadtree
+[quadtree-split-img]: https://github.com/32bitkid/4bitlabs.spatial/blob/main/quadtree-split.png?raw=true

Fixed alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

28522

32.7%

Number of package files

27

17.39%

Lines of code

421

94.01%

Number of lines in readme file

83

43.1%

Number of medium supply chain risk alerts

0

-100%

No dependency changes