{"id":13393,"library":"js-quadtree","title":"js-quadtree","description":"js-quadtree is a JavaScript library providing a robust and configurable quadtree implementation, suitable for both Node.js environments and direct browser usage. Currently at stable version 3.3.6, the library appears to follow an infrequent release cadence, with recent updates primarily consisting of minor version bumps without significant feature changes or breaking modifications. Its key differentiators include the ability to specify maximum capacity per node, automatic removal of empty sub-nodes, configurable maximum depth to prevent excessive subdivision, and a customizable point equality comparison function crucial for accurate removal operations when dealing with custom data. It supports inserting plain objects with `x` and `y` properties in addition to its own `Point` objects, which can hold arbitrary custom data, making it flexible for various spatial indexing needs.","status":"active","version":"3.3.6","language":"javascript","source_language":"en","source_url":"https://github.com/CorentinTh/quadtree-js","tags":["javascript","quadtree","qt","quadtree.js","quadtree javascript"],"install":[{"cmd":"npm install js-quadtree","lang":"bash","label":"npm"},{"cmd":"yarn add js-quadtree","lang":"bash","label":"yarn"},{"cmd":"pnpm add js-quadtree","lang":"bash","label":"pnpm"}],"dependencies":[],"imports":[{"note":"js-quadtree uses named exports for all its core classes in ESM. There is no default export.","wrong":"import QuadTree from 'js-quadtree';","symbol":"QuadTree","correct":"import { QuadTree } from 'js-quadtree';"},{"note":"When using CommonJS, destructure the required module to access specific classes like Box, Point, or Circle.","wrong":"const Box = require('js-quadtree');","symbol":"Box","correct":"const { Box } = require('js-quadtree');"},{"note":"When using the library via CDN in a browser, all classes (QuadTree, Box, Point, Circle) are globally accessible under the 'QT' namespace.","wrong":"const point = new Point(x, y, data);","symbol":"Point","correct":"const point = new QT.Point(x, y, data);"}],"quickstart":{"code":"import { QuadTree, Box, Point, Circle } from 'js-quadtree';\n\n// 1. Define the bounding area for the quadtree\nconst boundingArea = new Box(0, 0, 1000, 1000); // x, y, width, height\n\n// 2. Configure the quadtree (optional parameters)\nconst config = {\n    capacity: 8,           // Max points per node before subdividing (default: 4)\n    removeEmptyNodes: true, // Automatically clean up empty sub-nodes (default: false)\n    maximumDepth: 10,      // Prevent infinite subdivision, -1 for no limit (default: -1)\n    // Custom comparison function for point removal if data is complex\n    arePointsEqual: (p1, p2) => p1.data && p2.data && p1.data.id === p2.data.id\n};\n\n// 3. Instantiate the quadtree with initial points (optional)\nconst initialPoints = [\n    new Point(100, 200, { id: 'a', type: 'player' }),\n    new Point(500, 700, { id: 'b', type: 'enemy' }),\n    { x: 150, y: 250, data: { id: 'c', type: 'item' } } // Custom object insert, requires x/y\n];\nconst quadtree = new QuadTree(boundingArea, config, initialPoints);\n\nconsole.log(`Initial quadtree has ${quadtree.length} points.`);\n\n// 4. Insert more points individually or as an array\nquadtree.insert(new Point(300, 400, { id: 'd', type: 'obstacle' }));\nquadtree.insert([\n    new Point(80, 120, { id: 'e', type: 'item' }),\n    { x: 900, y: 100, data: { id: 'f', type: 'effect' } }\n]);\n\n// 5. Query for objects within a specific area (e.g., a circle)\nconst searchArea = new Circle(150, 150, 100); // centerX, centerY, radius\nconst results = quadtree.query(searchArea);\n\nconsole.log(`Found ${results.length} items in the search area.`);\nresults.forEach(point => console.log(`  - Point at (${point.x}, ${point.y}) with data:`, point.data));\n\n// 6. Remove a point\nconst pointToRemove = new Point(100, 200, { id: 'a' });\nquadtree.remove(pointToRemove); // Requires arePointsEqual config if data matters for equality\nconsole.log('Attempted to remove point (100, 200). New total points:', quadtree.length);","lang":"typescript","description":"Demonstrates quadtree creation, configuration, insertion of various point types (including custom data and plain objects), querying with a circular region, and point removal, showcasing common API interactions."},"warnings":[{"fix":"Always prefix class constructors with `QT.` (e.g., `new QT.QuadTree()`, `new QT.Point()`) when using the CDN build in a browser environment.","message":"When consuming `js-quadtree` via a CDN in a browser, all core classes (QuadTree, Box, Point, Circle) are exposed under the global `QT` namespace. Attempting to use them without this prefix (e.g., `new QuadTree(...)` instead of `new QT.QuadTree(...)`) will result in a `ReferenceError`.","severity":"gotcha","affected_versions":">=1.0.0"},{"fix":"Pass a `config` object to the `QuadTree` constructor with a custom `arePointsEqual` property that implements your desired comparison logic (e.g., `(p1, p2) => p1.x === p2.x && p1.y === p2.y && p1.data.id === p2.data.id`).","message":"The default `arePointsEqual` comparison function used for `remove()` operations only checks `x` and `y` coordinates. If points contain custom data that should also be considered for equality (e.g., a unique ID in the `data` object), you must provide a custom `arePointsEqual` function in the QuadTree configuration. Otherwise, `remove()` might fail to find or incorrectly remove points.","severity":"gotcha","affected_versions":">=1.0.0"},{"fix":"Tune `capacity` and `maximumDepth` parameters based on your specific application's data distribution and performance requirements. For static or mostly additive data sets, consider disabling `removeEmptyNodes` if the overhead is noticeable. Profile your application to find optimal values.","message":"Enabling `removeEmptyNodes: true` and setting a very low `capacity` with a large `maximumDepth` can lead to increased computational overhead, especially during frequent insertions and removals, due to the constant re-evaluation and restructuring of the quadtree's internal nodes.","severity":"gotcha","affected_versions":">=1.0.0"}],"env_vars":null,"last_verified":"2026-04-19T00:00:00.000Z","next_check":"2026-07-18T00:00:00.000Z","problems":[{"fix":"In browser CDN usage, access classes via the global `QT` object: `new QT.QuadTree(...)`, `new QT.Box(...)`, etc. Ensure proper ESM/CJS imports in Node.js: `import { QuadTree } from 'js-quadtree';` or `const { QuadTree } = require('js-quadtree');`.","cause":"Attempting to use `QuadTree`, `Box`, `Point`, or `Circle` directly in a browser environment after loading via CDN, without the `QT` prefix.","error":"ReferenceError: QuadTree is not defined"},{"fix":"Ensure all objects inserted into or removed from the quadtree conform to the expected interface by having both `x` and `y` numeric properties, either as `Point` instances or custom objects.","cause":"An object passed to `quadtree.insert()` or `quadtree.remove()` does not have numeric `x` and `y` properties, which are fundamental for the quadtree's spatial indexing.","error":"TypeError: Cannot read properties of undefined (reading 'x') (or 'y')"},{"fix":"Verify that the `Point` object passed to `remove()` is identical to one previously inserted. If using custom data, implement a custom `arePointsEqual` function in the `QuadTree` configuration that accurately compares unique identifiers or relevant properties within your `data` objects.","cause":"The `remove()` method was called with a `Point` object that, according to the `arePointsEqual` configuration (or its default), does not exactly match any existing point in the quadtree.","error":"The point you are trying to remove is not in the quadtree."}],"ecosystem":"npm","meta_description":null,"install_score":null,"install_tag":null,"quickstart_score":null,"quickstart_tag":null,"pypi_latest":null,"cli_name":"","cli_version":null}