[Git][debian-gis-team/mapbox-polylabel][upstream] New upstream version 2.1.0
Bas Couwenberg (@sebastic)
gitlab at salsa.debian.org
Thu Jun 25 13:06:08 BST 2026
Bas Couwenberg pushed to branch upstream at Debian GIS Project / mapbox-polylabel
Commits:
6b5982af by Bas Couwenberg at 2026-06-25T13:58:58+02:00
New upstream version 2.1.0
- - - - -
16 changed files:
- + .github/workflows/npm-release.yml
- .github/workflows/test.yml
- .gitignore
- − .gitmodules
- + CODEOWNERS
- LICENSE
- − Makefile
- README.md
- + bench.js
- − debug.js
- − include/mapbox/polylabel.hpp
- package-lock.json
- package.json
- polylabel.js
- − test/test.cpp
- test/test.js
Changes:
=====================================
.github/workflows/npm-release.yml
=====================================
@@ -0,0 +1,17 @@
+name: Publish
+on:
+ push:
+ tags: ['v*']
+permissions:
+ id-token: write
+jobs:
+ publish:
+ runs-on: ubuntu-latest
+ environment: npm-release
+ steps:
+ - uses: actions/checkout at v6
+ - uses: actions/setup-node at v6
+ with:
+ node-version: 24
+ - run: npm ci
+ - run: npm publish --access public
=====================================
.github/workflows/test.yml
=====================================
@@ -4,24 +4,10 @@ jobs:
node:
runs-on: ubuntu-latest
steps:
- - name: Checkout
- uses: actions/checkout at v2
-
- - name: Setup Node
- uses: actions/setup-node at v1
+ - uses: actions/checkout at v6
+ - uses: actions/setup-node at v6
with:
- node-version: 20
-
- - name: Install dependencies
- run: npm ci
-
- - name: Run tests
- run: npm test
- cpp:
- runs-on: ubuntu-latest
- steps:
- - name: Checkout
- uses: actions/checkout at v2
-
- - name: Test C++
- run: make test
+ node-version: 24
+ cache: npm
+ - run: npm ci
+ - run: npm test
=====================================
.gitignore
=====================================
@@ -1,3 +1 @@
-mason_packages
node_modules
-build
=====================================
.gitmodules deleted
=====================================
@@ -1,3 +0,0 @@
-[submodule ".mason"]
- path = .mason
- url = https://github.com/mapbox/mason
=====================================
CODEOWNERS
=====================================
@@ -0,0 +1 @@
+* @mapbox/gl-js
=====================================
LICENSE
=====================================
@@ -1,5 +1,5 @@
ISC License
-Copyright (c) 2016 Mapbox
+Copyright (c) 2026 Mapbox
Permission to use, copy, modify, and/or distribute this software for any purpose
with or without fee is hereby granted, provided that the above copyright notice
=====================================
Makefile deleted
=====================================
@@ -1,27 +0,0 @@
-CXXFLAGS += -Iinclude -std=c++14 -Wall -Wextra -Wshadow -Werror -Wno-class-memaccess -g -fPIC
-
-MASON ?= .mason/mason
-VARIANT = variant 1.1.4
-GEOMETRY = geometry 0.9.2
-RAPIDJSON = rapidjson 1.1.0
-
-$(MASON):
- git submodule update --init
-
-DEPS = `$(MASON) cflags $(VARIANT)` \
- `$(MASON) cflags $(GEOMETRY)` \
- `$(MASON) cflags $(RAPIDJSON)`
-
-mason_packages/headers/geometry: $(MASON)
- $(MASON) install $(VARIANT)
- $(MASON) install $(GEOMETRY)
- $(MASON) install $(RAPIDJSON)
-
-build:
- mkdir -p build
-
-build/test: test/test.cpp include/mapbox/polylabel.hpp build mason_packages/headers/geometry
- $(CXX) $(CFLAGS) $(CXXFLAGS) $(DEPS) $< -o $@
-
-test: build/test
- ./build/test
=====================================
README.md
=====================================
@@ -48,20 +48,6 @@ Be careful to pick precision appropriate for the input units. E.g. in case of ge
[TypeScript type definitions](https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/types/polylabel)
are available via `npm install --save @types/polylabel`.
-### C++ Usage
-
-It is recommended to install polylabel via [mason](https://github.com/mapbox/mason). You will also need to install its dependencies: [geometry.hpp](https://github.com/mapbox/geometry.hpp) and [variant](https://github.com/mapbox/variant).
-
-```C++
-#include <mapbox/polylabel.hpp>
-
-int main() {
- mapbox::geometry::polygon<double> polygon = readPolygon(); // Get polygon data from somewhere.
- mapbox::geometry::point<double> p = mapbox::polylabel(polygon, 1.0);
- return 0;
-}
-```
-
#### Ports to other languages
- [andrewharvey/geojson-polygon-labels](https://github.com/andrewharvey/geojson-polygon-labels) (CLI)
@@ -69,8 +55,10 @@ int main() {
- [Shapely](https://github.com/Toblerity/Shapely/blob/master/shapely/algorithms/polylabel.py) (Python)
- [polylabelr](https://CRAN.R-project.org/package=polylabelr) (R)
- [polylabel-rs](https://github.com/urschrei/polylabel-rs) (Rust)
-- [polylabel-java](https://github.com/FreshLlamanade/polylabel-java) (Java)
- [php-polylabel](https://github.com/dliebner/php-polylabel) (PHP)
- [dart_polylabel](https://github.com/beroso/dart_polylabel) (Dart)
- [ruby-polylabel](https://github.com/fredplante/ruby-polylabel) (Ruby)
- [Polylabel.jl](https://github.com/asinghvi17/Polylabel.jl) (Julia)
+- [geobase](https://github.com/navibyte/geospatial/blob/main/dart/geobase/lib/src/geometric/cartesian/areal/polylabel.dart) (Dart)
+- [PolylabelNet](https://github.com/oberbichler/PolylabelNet) (C#)
+- [polylabel-geometrynodes](https://github.com/farukahmet/polylabel-geometrynodes) (Blender)
=====================================
bench.js
=====================================
@@ -0,0 +1,24 @@
+import polylabel from './polylabel.js';
+import water1 from './test/fixtures/water1.json' with {type: 'json'};
+import water2 from './test/fixtures/water2.json' with {type: 'json'};
+
+const cases = [
+ ['water1 precision 1', water1, 1],
+ ['water1 precision 50', water1, 50],
+ ['water2 precision 1', water2, 1],
+];
+
+const RUNS = 100;
+
+for (const [name, polygon, precision] of cases) {
+ const times = [];
+ for (let r = 0; r < RUNS; r++) {
+ const t = performance.now();
+ polylabel(polygon, precision);
+ times.push(performance.now() - t);
+ }
+ times.sort((a, b) => a - b);
+ const min = times[0];
+ const median = times[times.length >> 1];
+ console.log(`${name}: min ${min.toFixed(2)}ms, median ${median.toFixed(2)}ms`);
+}
=====================================
debug.js deleted
=====================================
@@ -1,13 +0,0 @@
-
-import polylabel from './polylabel.js';
-import {readFileSync} from 'fs';
-
-const polygon = JSON.parse(readFileSync(new URL('./test/fixtures/water1.json', import.meta.url)));
-
-console.log(`num points: ${[].concat(...polygon).length}`);
-
-console.time('find point');
-const result = polylabel(polygon, 1, true);
-console.timeEnd('find point');
-
-console.log(result);
=====================================
include/mapbox/polylabel.hpp deleted
=====================================
@@ -1,178 +0,0 @@
-#pragma once
-
-#include <mapbox/geometry/polygon.hpp>
-#include <mapbox/geometry/envelope.hpp>
-#include <mapbox/geometry/point.hpp>
-#include <mapbox/geometry/point_arithmetic.hpp>
-
-#include <algorithm>
-#include <cmath>
-#include <iostream>
-#include <queue>
-
-namespace mapbox {
-
-namespace detail {
-
-// get squared distance from a point to a segment
-template <class T>
-T getSegDistSq(const geometry::point<T>& p,
- const geometry::point<T>& a,
- const geometry::point<T>& b) {
- auto x = a.x;
- auto y = a.y;
- auto dx = b.x - x;
- auto dy = b.y - y;
-
- if (dx != 0 || dy != 0) {
-
- auto t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy);
-
- if (t > 1) {
- x = b.x;
- y = b.y;
-
- } else if (t > 0) {
- x += dx * t;
- y += dy * t;
- }
- }
-
- dx = p.x - x;
- dy = p.y - y;
-
- return dx * dx + dy * dy;
-}
-
-// signed distance from point to polygon outline (negative if point is outside)
-template <class T>
-auto pointToPolygonDist(const geometry::point<T>& point, const geometry::polygon<T>& polygon) {
- bool inside = false;
- auto minDistSq = std::numeric_limits<double>::infinity();
-
- for (const auto& ring : polygon) {
- for (std::size_t i = 0, len = ring.size(), j = len - 1; i < len; j = i++) {
- const auto& a = ring[i];
- const auto& b = ring[j];
-
- if ((a.y > point.y) != (b.y > point.y) &&
- (point.x < (b.x - a.x) * (point.y - a.y) / (b.y - a.y) + a.x)) inside = !inside;
-
- minDistSq = std::min(minDistSq, getSegDistSq(point, a, b));
- }
- }
-
- return (inside ? 1 : -1) * std::sqrt(minDistSq);
-}
-
-template <class T>
-struct Cell {
- Cell(const geometry::point<T>& c_, T h_, const geometry::polygon<T>& polygon)
- : c(c_),
- h(h_),
- d(pointToPolygonDist(c, polygon)),
- max(d + h * std::sqrt(2))
- {}
-
- geometry::point<T> c; // cell center
- T h; // half the cell size
- T d; // distance from cell center to polygon
- T max; // max distance to polygon within a cell
-};
-
-// get polygon centroid
-template <class T>
-Cell<T> getCentroidCell(const geometry::polygon<T>& polygon) {
- T area = 0;
- geometry::point<T> c { 0, 0 };
- const auto& ring = polygon.at(0);
-
- for (std::size_t i = 0, len = ring.size(), j = len - 1; i < len; j = i++) {
- const geometry::point<T>& a = ring[i];
- const geometry::point<T>& b = ring[j];
- auto f = a.x * b.y - b.x * a.y;
- c.x += (a.x + b.x) * f;
- c.y += (a.y + b.y) * f;
- area += f * 3;
- }
-
- return Cell<T>(area == 0 ? ring.at(0) : c / area, 0, polygon);
-}
-
-} // namespace detail
-
-template <class T>
-geometry::point<T> polylabel(const geometry::polygon<T>& polygon, T precision = 1, bool debug = false) {
- using namespace detail;
-
- // find the bounding box of the outer ring
- const geometry::box<T> envelope = geometry::envelope(polygon.at(0));
-
- const geometry::point<T> size {
- envelope.max.x - envelope.min.x,
- envelope.max.y - envelope.min.y
- };
-
- const T cellSize = std::min(size.x, size.y);
- T h = cellSize / 2;
-
- // a priority queue of cells in order of their "potential" (max distance to polygon)
- auto compareMax = [] (const Cell<T>& a, const Cell<T>& b) {
- return a.max < b.max;
- };
- using Queue = std::priority_queue<Cell<T>, std::vector<Cell<T>>, decltype(compareMax)>;
- Queue cellQueue(compareMax);
-
- if (cellSize == 0) {
- return envelope.min;
- }
-
- // cover polygon with initial cells
- for (T x = envelope.min.x; x < envelope.max.x; x += cellSize) {
- for (T y = envelope.min.y; y < envelope.max.y; y += cellSize) {
- cellQueue.push(Cell<T>({x + h, y + h}, h, polygon));
- }
- }
-
- // take centroid as the first best guess
- auto bestCell = getCentroidCell(polygon);
-
- // second guess: bounding box centroid
- Cell<T> bboxCell(envelope.min + size / 2.0, 0, polygon);
- if (bboxCell.d > bestCell.d) {
- bestCell = bboxCell;
- }
-
- auto numProbes = cellQueue.size();
- while (!cellQueue.empty()) {
- // pick the most promising cell from the queue
- auto cell = cellQueue.top();
- cellQueue.pop();
-
- // update the best cell if we found a better one
- if (cell.d > bestCell.d) {
- bestCell = cell;
- if (debug) std::cout << "found best " << ::round(1e4 * cell.d) / 1e4 << " after " << numProbes << " probes" << std::endl;
- }
-
- // do not drill down further if there's no chance of a better solution
- if (cell.max - bestCell.d <= precision) continue;
-
- // split the cell into four cells
- h = cell.h / 2;
- cellQueue.push(Cell<T>({cell.c.x - h, cell.c.y - h}, h, polygon));
- cellQueue.push(Cell<T>({cell.c.x + h, cell.c.y - h}, h, polygon));
- cellQueue.push(Cell<T>({cell.c.x - h, cell.c.y + h}, h, polygon));
- cellQueue.push(Cell<T>({cell.c.x + h, cell.c.y + h}, h, polygon));
- numProbes += 4;
- }
-
- if (debug) {
- std::cout << "num probes: " << numProbes << std::endl;
- std::cout << "best distance: " << bestCell.d << std::endl;
- }
-
- return bestCell.c;
-}
-
-} // namespace mapbox
=====================================
package-lock.json
=====================================
@@ -1,33 +1,36 @@
{
"name": "polylabel",
- "version": "2.0.1",
+ "version": "2.1.0",
"lockfileVersion": 3,
"requires": true,
"packages": {
"": {
"name": "polylabel",
- "version": "2.0.1",
+ "version": "2.1.0",
"license": "ISC",
"dependencies": {
"tinyqueue": "^3.0.0"
},
"devDependencies": {
- "eslint": "^9.6.0",
- "eslint-config-mourner": "^4.0.1"
+ "eslint": "^10.5.0",
+ "eslint-config-mourner": "^5.0.1"
}
},
"node_modules/@eslint-community/eslint-utils": {
- "version": "4.4.0",
- "resolved": "https://registry.npmjs.org/@eslint-community/eslint-utils/-/eslint-utils-4.4.0.tgz",
- "integrity": "sha512-1/sA4dwrzBAyeUoQ6oxahHKmrZvsnLCg4RfxW3ZFGGmQkSNQPFNLV9CUEFQP1x9EYXHTo5p6xdhZM1Ne9p/AfA==",
+ "version": "4.9.1",
+ "resolved": "https://registry.npmjs.org/@eslint-community/eslint-utils/-/eslint-utils-4.9.1.tgz",
+ "integrity": "sha512-phrYmNiYppR7znFEdqgfWHXR6NCkZEK7hwWDHZUjit/2/U0r6XvkDl0SYnoM51Hq7FhCGdLDT6zxCCOY1hexsQ==",
"dev": true,
"license": "MIT",
"dependencies": {
- "eslint-visitor-keys": "^3.3.0"
+ "eslint-visitor-keys": "^3.4.3"
},
"engines": {
"node": "^12.22.0 || ^14.17.0 || >=16.0.0"
},
+ "funding": {
+ "url": "https://opencollective.com/eslint"
+ },
"peerDependencies": {
"eslint": "^6.0.0 || ^7.0.0 || >=8.0.0"
}
@@ -46,9 +49,9 @@
}
},
"node_modules/@eslint-community/regexpp": {
- "version": "4.10.1",
- "resolved": "https://registry.npmjs.org/@eslint-community/regexpp/-/regexpp-4.10.1.tgz",
- "integrity": "sha512-Zm2NGpWELsQAD1xsJzGQpYfvICSsFkEpU0jxBjfdC6uNEWXcHnfs9hScFWtXVDVl+rBQJGrl4g1vcKIejpH9dA==",
+ "version": "4.12.2",
+ "resolved": "https://registry.npmjs.org/@eslint-community/regexpp/-/regexpp-4.12.2.tgz",
+ "integrity": "sha512-EriSTlt5OC9/7SXkRSCAhfSxxoSUgBm33OH+IkwbdpgoqsSsUg7y3uh+IICI/Qg4BBWr3U2i39RpmycbxMq4ew==",
"dev": true,
"license": "MIT",
"engines": {
@@ -56,62 +59,127 @@
}
},
"node_modules/@eslint/config-array": {
- "version": "0.17.0",
- "resolved": "https://registry.npmjs.org/@eslint/config-array/-/config-array-0.17.0.tgz",
- "integrity": "sha512-A68TBu6/1mHHuc5YJL0U0VVeGNiklLAL6rRmhTCP2B5XjWLMnrX+HkO+IAXyHvks5cyyY1jjK5ITPQ1HGS2EVA==",
+ "version": "0.23.5",
+ "resolved": "https://registry.npmjs.org/@eslint/config-array/-/config-array-0.23.5.tgz",
+ "integrity": "sha512-Y3kKLvC1dvTOT+oGlqNQ1XLqK6D1HU2YXPc52NmAlJZbMMWDzGYXMiPRJ8TYD39muD/OTjlZmNJ4ib7dvSrMBA==",
"dev": true,
"license": "Apache-2.0",
"dependencies": {
- "@eslint/object-schema": "^2.1.4",
+ "@eslint/object-schema": "^3.0.5",
"debug": "^4.3.1",
- "minimatch": "^3.1.2"
+ "minimatch": "^10.2.4"
},
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
}
},
- "node_modules/@eslint/eslintrc": {
- "version": "3.1.0",
- "resolved": "https://registry.npmjs.org/@eslint/eslintrc/-/eslintrc-3.1.0.tgz",
- "integrity": "sha512-4Bfj15dVJdoy3RfZmmo86RK1Fwzn6SstsvK9JS+BaVKqC6QQQQyXekNaC+g+LKNgkQ+2VhGAzm6hO40AhMR3zQ==",
+ "node_modules/@eslint/config-helpers": {
+ "version": "0.6.0",
+ "resolved": "https://registry.npmjs.org/@eslint/config-helpers/-/config-helpers-0.6.0.tgz",
+ "integrity": "sha512-ii6Bw9jJ2zi2cWA2Z+9/QZ/+3DX6kwaV5Q986D/CdP3Lap3w/pgQZ373FV7byY/i7L4IRH/G43I5dz1ClsCbpA==",
"dev": true,
- "license": "MIT",
+ "license": "Apache-2.0",
"dependencies": {
- "ajv": "^6.12.4",
- "debug": "^4.3.2",
- "espree": "^10.0.1",
- "globals": "^14.0.0",
- "ignore": "^5.2.0",
- "import-fresh": "^3.2.1",
- "js-yaml": "^4.1.0",
- "minimatch": "^3.1.2",
- "strip-json-comments": "^3.1.1"
+ "@eslint/core": "^1.2.1"
},
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
+ }
+ },
+ "node_modules/@eslint/core": {
+ "version": "1.2.1",
+ "resolved": "https://registry.npmjs.org/@eslint/core/-/core-1.2.1.tgz",
+ "integrity": "sha512-MwcE1P+AZ4C6DWlpin/OmOA54mmIZ/+xZuJiQd4SyB29oAJjN30UW9wkKNptW2ctp4cEsvhlLY/CsQ1uoHDloQ==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "dependencies": {
+ "@types/json-schema": "^7.0.15"
},
- "funding": {
- "url": "https://opencollective.com/eslint"
+ "engines": {
+ "node": "^20.19.0 || ^22.13.0 || >=24"
}
},
"node_modules/@eslint/js": {
- "version": "9.6.0",
- "resolved": "https://registry.npmjs.org/@eslint/js/-/js-9.6.0.tgz",
- "integrity": "sha512-D9B0/3vNg44ZeWbYMpBoXqNP4j6eQD5vNwIlGAuFRRzK/WtT/jvDQW3Bi9kkf3PMDMlM7Yi+73VLUsn5bJcl8A==",
+ "version": "10.0.1",
+ "resolved": "https://registry.npmjs.org/@eslint/js/-/js-10.0.1.tgz",
+ "integrity": "sha512-zeR9k5pd4gxjZ0abRoIaxdc7I3nDktoXZk2qOv9gCNWx3mVwEn32VRhyLaRsDiJjTs0xq/T8mfPtyuXu7GWBcA==",
"dev": true,
"license": "MIT",
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
+ },
+ "funding": {
+ "url": "https://eslint.org/donate"
+ },
+ "peerDependencies": {
+ "eslint": "^10.0.0"
+ },
+ "peerDependenciesMeta": {
+ "eslint": {
+ "optional": true
+ }
}
},
"node_modules/@eslint/object-schema": {
- "version": "2.1.4",
- "resolved": "https://registry.npmjs.org/@eslint/object-schema/-/object-schema-2.1.4.tgz",
- "integrity": "sha512-BsWiH1yFGjXXS2yvrf5LyuoSIIbPrGUWob917o+BTKuZ7qJdxX8aJLRxs1fS9n6r7vESrq1OUqb68dANcFXuQQ==",
+ "version": "3.0.5",
+ "resolved": "https://registry.npmjs.org/@eslint/object-schema/-/object-schema-3.0.5.tgz",
+ "integrity": "sha512-vqTaUEgxzm+YDSdElad6PiRoX4t8VGDjCtt05zn4nU810UIx/uNEV7/lZJ6KwFThKZOzOxzXy48da+No7HZaMw==",
"dev": true,
"license": "Apache-2.0",
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
+ }
+ },
+ "node_modules/@eslint/plugin-kit": {
+ "version": "0.7.2",
+ "resolved": "https://registry.npmjs.org/@eslint/plugin-kit/-/plugin-kit-0.7.2.tgz",
+ "integrity": "sha512-+CNAzxglkrpNf/kKywqQfk74QjtceuOE7Qm+AF8miRvPF/wmmK5+OJOgVh3AVTT3RP2mH3+FOaxlE5v72owk0A==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "dependencies": {
+ "@eslint/core": "^1.2.1",
+ "levn": "^0.4.1"
+ },
+ "engines": {
+ "node": "^20.19.0 || ^22.13.0 || >=24"
+ }
+ },
+ "node_modules/@humanfs/core": {
+ "version": "0.19.2",
+ "resolved": "https://registry.npmjs.org/@humanfs/core/-/core-0.19.2.tgz",
+ "integrity": "sha512-UhXNm+CFMWcbChXywFwkmhqjs3PRCmcSa/hfBgLIb7oQ5HNb1wS0icWsGtSAUNgefHeI+eBrA8I1fxmbHsGdvA==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "dependencies": {
+ "@humanfs/types": "^0.15.0"
+ },
+ "engines": {
+ "node": ">=18.18.0"
+ }
+ },
+ "node_modules/@humanfs/node": {
+ "version": "0.16.8",
+ "resolved": "https://registry.npmjs.org/@humanfs/node/-/node-0.16.8.tgz",
+ "integrity": "sha512-gE1eQNZ3R++kTzFUpdGlpmy8kDZD/MLyHqDwqjkVQI0JMdI1D51sy1H958PNXYkM2rAac7e5/CnIKZrHtPh3BQ==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "dependencies": {
+ "@humanfs/core": "^0.19.2",
+ "@humanfs/types": "^0.15.0",
+ "@humanwhocodes/retry": "^0.4.0"
+ },
+ "engines": {
+ "node": ">=18.18.0"
+ }
+ },
+ "node_modules/@humanfs/types": {
+ "version": "0.15.0",
+ "resolved": "https://registry.npmjs.org/@humanfs/types/-/types-0.15.0.tgz",
+ "integrity": "sha512-ZZ1w0aoQkwuUuC7Yf+7sdeaNfqQiiLcSRbfI08oAxqLtpXQr9AIVX7Ay7HLDuiLYAaFPu8oBYNq/QIi9URHJ3Q==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "engines": {
+ "node": ">=18.18.0"
}
},
"node_modules/@humanwhocodes/module-importer": {
@@ -129,9 +197,9 @@
}
},
"node_modules/@humanwhocodes/retry": {
- "version": "0.3.0",
- "resolved": "https://registry.npmjs.org/@humanwhocodes/retry/-/retry-0.3.0.tgz",
- "integrity": "sha512-d2CGZR2o7fS6sWB7DG/3a95bGKQyHMACZ5aW8qGkkqQpUoZV6C0X7Pc7l4ZNMZkfNBf4VWNe9E1jRsf0G146Ew==",
+ "version": "0.4.3",
+ "resolved": "https://registry.npmjs.org/@humanwhocodes/retry/-/retry-0.4.3.tgz",
+ "integrity": "sha512-bV0Tgo9K4hfPCek+aMAn81RppFKv2ySDQeMoSZuvTASywNTnVJCArCZE2FWqpvIatKu7VMRLWlR1EazvVhDyhQ==",
"dev": true,
"license": "Apache-2.0",
"engines": {
@@ -142,78 +210,69 @@
"url": "https://github.com/sponsors/nzakas"
}
},
- "node_modules/@nodelib/fs.scandir": {
- "version": "2.1.5",
- "resolved": "https://registry.npmjs.org/@nodelib/fs.scandir/-/fs.scandir-2.1.5.tgz",
- "integrity": "sha512-vq24Bq3ym5HEQm2NKCr3yXDwjc7vTsEThRDnkp2DK9p1uqLR+DHurm/NOTo0KG7HYHU7eppKZj3MyqYuMBf62g==",
+ "node_modules/@stylistic/eslint-plugin": {
+ "version": "5.10.0",
+ "resolved": "https://registry.npmjs.org/@stylistic/eslint-plugin/-/eslint-plugin-5.10.0.tgz",
+ "integrity": "sha512-nPK52ZHvot8Ju/0A4ucSX1dcPV2/1clx0kLcH5wDmrE4naKso7TUC/voUyU1O9OTKTrR6MYip6LP0ogEMQ9jPQ==",
"dev": true,
"license": "MIT",
"dependencies": {
- "@nodelib/fs.stat": "2.0.5",
- "run-parallel": "^1.1.9"
+ "@eslint-community/eslint-utils": "^4.9.1",
+ "@typescript-eslint/types": "^8.56.0",
+ "eslint-visitor-keys": "^4.2.1",
+ "espree": "^10.4.0",
+ "estraverse": "^5.3.0",
+ "picomatch": "^4.0.3"
},
"engines": {
- "node": ">= 8"
+ "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ },
+ "peerDependencies": {
+ "eslint": "^9.0.0 || ^10.0.0"
}
},
- "node_modules/@nodelib/fs.stat": {
- "version": "2.0.5",
- "resolved": "https://registry.npmjs.org/@nodelib/fs.stat/-/fs.stat-2.0.5.tgz",
- "integrity": "sha512-RkhPPp2zrqDAQA/2jNhnztcPAlv64XdhIp7a7454A5ovI7Bukxgt7MX7udwAu3zg1DcpPU0rz3VV1SeaqvY4+A==",
+ "node_modules/@stylistic/eslint-plugin/node_modules/eslint-visitor-keys": {
+ "version": "4.2.1",
+ "resolved": "https://registry.npmjs.org/eslint-visitor-keys/-/eslint-visitor-keys-4.2.1.tgz",
+ "integrity": "sha512-Uhdk5sfqcee/9H/rCOJikYz67o0a2Tw2hGRPOG2Y1R2dg7brRe1uG0yaNQDHu+TO/uQPF/5eCapvYSmHUjt7JQ==",
"dev": true,
- "license": "MIT",
+ "license": "Apache-2.0",
"engines": {
- "node": ">= 8"
- }
- },
- "node_modules/@nodelib/fs.walk": {
- "version": "1.2.8",
- "resolved": "https://registry.npmjs.org/@nodelib/fs.walk/-/fs.walk-1.2.8.tgz",
- "integrity": "sha512-oGB+UxlgWcgQkgwo8GcEGwemoTFt3FIO9ababBmaGwXIoBKZ+GTy0pP185beGg7Llih/NSHSV2XAs1lnznocSg==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "@nodelib/fs.scandir": "2.1.5",
- "fastq": "^1.6.0"
+ "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
},
- "engines": {
- "node": ">= 8"
+ "funding": {
+ "url": "https://opencollective.com/eslint"
}
},
- "node_modules/@stylistic/eslint-plugin-js": {
- "version": "2.3.0",
- "resolved": "https://registry.npmjs.org/@stylistic/eslint-plugin-js/-/eslint-plugin-js-2.3.0.tgz",
- "integrity": "sha512-lQwoiYb0Fs6Yc5QS3uT8+T9CPKK2Eoxc3H8EnYJgM26v/DgtW+1lvy2WNgyBflU+ThShZaHm3a6CdD9QeKx23w==",
+ "node_modules/@stylistic/eslint-plugin/node_modules/espree": {
+ "version": "10.4.0",
+ "resolved": "https://registry.npmjs.org/espree/-/espree-10.4.0.tgz",
+ "integrity": "sha512-j6PAQ2uUr79PZhBjP5C5fhl8e39FmRnOjsD5lGnWrFU8i2G776tBK7+nP8KuQUTTyAZUwfQqXAgrVH5MbH9CYQ==",
"dev": true,
- "license": "MIT",
+ "license": "BSD-2-Clause",
"dependencies": {
- "@types/eslint": "^8.56.10",
- "acorn": "^8.11.3",
- "eslint-visitor-keys": "^4.0.0",
- "espree": "^10.0.1"
+ "acorn": "^8.15.0",
+ "acorn-jsx": "^5.3.2",
+ "eslint-visitor-keys": "^4.2.1"
},
"engines": {
"node": "^18.18.0 || ^20.9.0 || >=21.1.0"
},
- "peerDependencies": {
- "eslint": ">=8.40.0"
+ "funding": {
+ "url": "https://opencollective.com/eslint"
}
},
- "node_modules/@types/eslint": {
- "version": "8.56.10",
- "resolved": "https://registry.npmjs.org/@types/eslint/-/eslint-8.56.10.tgz",
- "integrity": "sha512-Shavhk87gCtY2fhXDctcfS3e6FdxWkCx1iUZ9eEUbh7rTqlZT0/IzOkCOVt0fCjcFuZ9FPYfuezTBImfHCDBGQ==",
+ "node_modules/@types/esrecurse": {
+ "version": "4.3.1",
+ "resolved": "https://registry.npmjs.org/@types/esrecurse/-/esrecurse-4.3.1.tgz",
+ "integrity": "sha512-xJBAbDifo5hpffDBuHl0Y8ywswbiAp/Wi7Y/GtAgSlZyIABppyurxVueOPE8LUQOxdlgi6Zqce7uoEpqNTeiUw==",
"dev": true,
- "license": "MIT",
- "dependencies": {
- "@types/estree": "*",
- "@types/json-schema": "*"
- }
+ "license": "MIT"
},
"node_modules/@types/estree": {
- "version": "1.0.5",
- "resolved": "https://registry.npmjs.org/@types/estree/-/estree-1.0.5.tgz",
- "integrity": "sha512-/kYRxGDLWzHOB7q+wtSUQlFrtcdUccpfy+X+9iMBpHK8QLLhx2wIPYuS5DYtR9Wa/YlZAbIovy7qVdB1Aq6Lyw==",
+ "version": "1.0.9",
+ "resolved": "https://registry.npmjs.org/@types/estree/-/estree-1.0.9.tgz",
+ "integrity": "sha512-GhdPgy1el4/ImP05X05Uw4cw2/M93BCUmnEvWZNStlCzEKME4Fkk+YpoA5OiHNQmoS7Cafb8Xa3Pya8m1Qrzeg==",
"dev": true,
"license": "MIT"
},
@@ -224,10 +283,24 @@
"dev": true,
"license": "MIT"
},
+ "node_modules/@typescript-eslint/types": {
+ "version": "8.62.0",
+ "resolved": "https://registry.npmjs.org/@typescript-eslint/types/-/types-8.62.0.tgz",
+ "integrity": "sha512-KvAclkktORPvM54TgLgA4z9HIV1M8zOgw9ZVNXl9f/8dLYfXYX1wkMXP7qmabpijQRV5bHJLOmoyGQbLMaUYeg==",
+ "dev": true,
+ "license": "MIT",
+ "engines": {
+ "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ },
+ "funding": {
+ "type": "opencollective",
+ "url": "https://opencollective.com/typescript-eslint"
+ }
+ },
"node_modules/acorn": {
- "version": "8.12.0",
- "resolved": "https://registry.npmjs.org/acorn/-/acorn-8.12.0.tgz",
- "integrity": "sha512-RTvkC4w+KNXrM39/lWCUaG0IbRkWdCv7W/IOW9oU6SawyxulvkQy5HQPVTKxEjczcUvapcrw3cFx/60VN/NRNw==",
+ "version": "8.17.0",
+ "resolved": "https://registry.npmjs.org/acorn/-/acorn-8.17.0.tgz",
+ "integrity": "sha512-xRQbDb9BnwDafYNn6Vwl839DYVjqXYb1XVGtWAZ1kcDc6iwAL4hg3B1dZlRiuENFeO2H53gFG3in621AdERVAg==",
"dev": true,
"license": "MIT",
"bin": {
@@ -248,9 +321,9 @@
}
},
"node_modules/ajv": {
- "version": "6.12.6",
- "resolved": "https://registry.npmjs.org/ajv/-/ajv-6.12.6.tgz",
- "integrity": "sha512-j3fVLgvTo527anyYyJOGTYJbG+vnnQYvE0m5mmkc1TK+nxAppkCLMIL0aZ4dblVCNoGShhm+kzE4ZUykBoMg4g==",
+ "version": "6.15.0",
+ "resolved": "https://registry.npmjs.org/ajv/-/ajv-6.15.0.tgz",
+ "integrity": "sha512-fgFx7Hfoq60ytK2c7DhnF8jIvzYgOMxfugjLOSMHjLIPgenqa7S7oaagATUq99mV6IYvN2tRmC0wnTYX6iPbMw==",
"dev": true,
"license": "MIT",
"dependencies": {
@@ -264,115 +337,33 @@
"url": "https://github.com/sponsors/epoberezkin"
}
},
- "node_modules/ansi-regex": {
- "version": "5.0.1",
- "resolved": "https://registry.npmjs.org/ansi-regex/-/ansi-regex-5.0.1.tgz",
- "integrity": "sha512-quJQXlTSUGL2LH9SUXo8VwsY4soanhgo6LNSm84E1LBcE8s3O0wpdiRzyR9z/ZZJMlMWv37qOOb9pdJlMUEKFQ==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=8"
- }
- },
- "node_modules/ansi-styles": {
- "version": "4.3.0",
- "resolved": "https://registry.npmjs.org/ansi-styles/-/ansi-styles-4.3.0.tgz",
- "integrity": "sha512-zbB9rCJAT1rbjiVDb2hqKFHNYLxgtk8NURxZ3IZwD3F6NtxbXZQCnnSi1Lkx+IDohdPlFp222wVALIheZJQSEg==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "color-convert": "^2.0.1"
- },
- "engines": {
- "node": ">=8"
- },
- "funding": {
- "url": "https://github.com/chalk/ansi-styles?sponsor=1"
- }
- },
- "node_modules/argparse": {
- "version": "2.0.1",
- "resolved": "https://registry.npmjs.org/argparse/-/argparse-2.0.1.tgz",
- "integrity": "sha512-8+9WqebbFzpX9OR+Wa6O29asIogeRMzcGtAINdpMHHyAg10f05aSFVBbcEqGf/PXw1EjAZ+q2/bEBg3DvurK3Q==",
- "dev": true,
- "license": "Python-2.0"
- },
"node_modules/balanced-match": {
- "version": "1.0.2",
- "resolved": "https://registry.npmjs.org/balanced-match/-/balanced-match-1.0.2.tgz",
- "integrity": "sha512-3oSeUO0TMV67hN1AmbXsK4yaqU7tjiHlbxRDZOpH0KW9+CeX4bRAaX0Anxt0tx2MrpRpWwQaPwIlISEJhYU5Pw==",
- "dev": true,
- "license": "MIT"
- },
- "node_modules/brace-expansion": {
- "version": "1.1.11",
- "resolved": "https://registry.npmjs.org/brace-expansion/-/brace-expansion-1.1.11.tgz",
- "integrity": "sha512-iCuPHDFgrHX7H2vEI/5xpz07zSHB00TpugqhmYtVmMO6518mCuRMoOYFldEBl0g187ufozdaHgWKcYFb61qGiA==",
+ "version": "4.0.4",
+ "resolved": "https://registry.npmjs.org/balanced-match/-/balanced-match-4.0.4.tgz",
+ "integrity": "sha512-BLrgEcRTwX2o6gGxGOCNyMvGSp35YofuYzw9h1IMTRmKqttAZZVU67bdb9Pr2vUHA8+j3i2tJfjO6C6+4myGTA==",
"dev": true,
"license": "MIT",
- "dependencies": {
- "balanced-match": "^1.0.0",
- "concat-map": "0.0.1"
- }
- },
- "node_modules/callsites": {
- "version": "3.1.0",
- "resolved": "https://registry.npmjs.org/callsites/-/callsites-3.1.0.tgz",
- "integrity": "sha512-P8BjAsXvZS+VIDUI11hHCQEv74YT67YUi5JJFNWIqL235sBmjX4+qx9Muvls5ivyNENctx46xQLQ3aTuE7ssaQ==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=6"
- }
- },
- "node_modules/chalk": {
- "version": "4.1.2",
- "resolved": "https://registry.npmjs.org/chalk/-/chalk-4.1.2.tgz",
- "integrity": "sha512-oKnbhFyRIXpUuez8iBMmyEa4nbj4IOQyuhc/wy9kY7/WVPcwIO9VA668Pu8RkO7+0G76SLROeyw9CpQ061i4mA==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "ansi-styles": "^4.1.0",
- "supports-color": "^7.1.0"
- },
"engines": {
- "node": ">=10"
- },
- "funding": {
- "url": "https://github.com/chalk/chalk?sponsor=1"
+ "node": "18 || 20 || >=22"
}
},
- "node_modules/color-convert": {
- "version": "2.0.1",
- "resolved": "https://registry.npmjs.org/color-convert/-/color-convert-2.0.1.tgz",
- "integrity": "sha512-RRECPsj7iu/xb5oKYcsFHSppFNnsj/52OVTRKb4zP5onXwVF3zVmmToNcOfGC+CRDpfK/U584fMg38ZHCaElKQ==",
+ "node_modules/brace-expansion": {
+ "version": "5.0.6",
+ "resolved": "https://registry.npmjs.org/brace-expansion/-/brace-expansion-5.0.6.tgz",
+ "integrity": "sha512-kLpxurY4Z4r9sgMsyG0Z9uzsBlgiU/EFKhj/h91/8yHu0edo7XuixOIH3VcJ8kkxs6/jPzoI6U9Vj3WqbMQ94g==",
"dev": true,
"license": "MIT",
"dependencies": {
- "color-name": "~1.1.4"
+ "balanced-match": "^4.0.2"
},
"engines": {
- "node": ">=7.0.0"
+ "node": "18 || 20 || >=22"
}
},
- "node_modules/color-name": {
- "version": "1.1.4",
- "resolved": "https://registry.npmjs.org/color-name/-/color-name-1.1.4.tgz",
- "integrity": "sha512-dOy+3AuW3a2wNbZHIuMZpTcgjGuLU/uBL/ubcZF9OXbDo8ff4O8yVp5Bf0efS8uEoYo5q4Fx7dY9OgQGXgAsQA==",
- "dev": true,
- "license": "MIT"
- },
- "node_modules/concat-map": {
- "version": "0.0.1",
- "resolved": "https://registry.npmjs.org/concat-map/-/concat-map-0.0.1.tgz",
- "integrity": "sha512-/Srv4dswyQNBfohGpz9o6Yb3Gz3SrUDqBH5rTuhGR7ahtlbYKnVxw2bCFMRljaA7EXHaXZ8wsHdodFvbkhKmqg==",
- "dev": true,
- "license": "MIT"
- },
"node_modules/cross-spawn": {
- "version": "7.0.3",
- "resolved": "https://registry.npmjs.org/cross-spawn/-/cross-spawn-7.0.3.tgz",
- "integrity": "sha512-iRDPJKUPVEND7dHPO8rkbOnPpyDygcDFtWjpeWNCgy8WP2rXcxXL8TskReQl6OrB2G7+UJrags1q15Fudc7G6w==",
+ "version": "7.0.6",
+ "resolved": "https://registry.npmjs.org/cross-spawn/-/cross-spawn-7.0.6.tgz",
+ "integrity": "sha512-uV2QOWP2nWzsy2aMp8aRibhi9dlzF5Hgh5SHaB9OiTGEyDTiJJyx0uy51QXdyWbtAHNua4XJzUKca3OzKUd3vA==",
"dev": true,
"license": "MIT",
"dependencies": {
@@ -385,13 +376,13 @@
}
},
"node_modules/debug": {
- "version": "4.3.5",
- "resolved": "https://registry.npmjs.org/debug/-/debug-4.3.5.tgz",
- "integrity": "sha512-pt0bNEmneDIvdL1Xsd9oDQ/wrQRkXDT4AUWlNZNPKvW5x/jyO9VFXkJUP07vQ2upmw5PlaITaPKc31jK13V+jg==",
+ "version": "4.4.3",
+ "resolved": "https://registry.npmjs.org/debug/-/debug-4.4.3.tgz",
+ "integrity": "sha512-RGwwWnwQvkVfavKVt22FGLw+xYSdzARwm0ru6DhTVA3umU5hZc28V3kO4stgYryrTlLpuvgI9GiijltAjNbcqA==",
"dev": true,
"license": "MIT",
"dependencies": {
- "ms": "2.1.2"
+ "ms": "^2.1.3"
},
"engines": {
"node": ">=6.0"
@@ -423,29 +414,33 @@
}
},
"node_modules/eslint": {
- "version": "9.6.0",
- "resolved": "https://registry.npmjs.org/eslint/-/eslint-9.6.0.tgz",
- "integrity": "sha512-ElQkdLMEEqQNM9Njff+2Y4q2afHk7JpkPvrd7Xh7xefwgQynqPxwf55J7di9+MEibWUGdNjFF9ITG9Pck5M84w==",
+ "version": "10.5.0",
+ "resolved": "https://registry.npmjs.org/eslint/-/eslint-10.5.0.tgz",
+ "integrity": "sha512-1y+7C+vi12bUK1IpZeaV3gsH9fHLBmPvYmPx42pvT/E9yG0IC8g3PUZZgp0+JLJl7ZDK0flc2gc+Aw9dpCvIsQ==",
"dev": true,
"license": "MIT",
+ "workspaces": [
+ "packages/*"
+ ],
"dependencies": {
- "@eslint-community/eslint-utils": "^4.2.0",
- "@eslint-community/regexpp": "^4.6.1",
- "@eslint/config-array": "^0.17.0",
- "@eslint/eslintrc": "^3.1.0",
- "@eslint/js": "9.6.0",
+ "@eslint-community/eslint-utils": "^4.8.0",
+ "@eslint-community/regexpp": "^4.12.2",
+ "@eslint/config-array": "^0.23.5",
+ "@eslint/config-helpers": "^0.6.0",
+ "@eslint/core": "^1.2.1",
+ "@eslint/plugin-kit": "^0.7.2",
+ "@humanfs/node": "^0.16.6",
"@humanwhocodes/module-importer": "^1.0.1",
- "@humanwhocodes/retry": "^0.3.0",
- "@nodelib/fs.walk": "^1.2.8",
- "ajv": "^6.12.4",
- "chalk": "^4.0.0",
- "cross-spawn": "^7.0.2",
+ "@humanwhocodes/retry": "^0.4.2",
+ "@types/estree": "^1.0.6",
+ "ajv": "^6.14.0",
+ "cross-spawn": "^7.0.6",
"debug": "^4.3.2",
"escape-string-regexp": "^4.0.0",
- "eslint-scope": "^8.0.1",
- "eslint-visitor-keys": "^4.0.0",
- "espree": "^10.1.0",
- "esquery": "^1.5.0",
+ "eslint-scope": "^9.1.2",
+ "eslint-visitor-keys": "^5.0.1",
+ "espree": "^11.2.0",
+ "esquery": "^1.7.0",
"esutils": "^2.0.2",
"fast-deep-equal": "^3.1.3",
"file-entry-cache": "^8.0.0",
@@ -454,89 +449,95 @@
"ignore": "^5.2.0",
"imurmurhash": "^0.1.4",
"is-glob": "^4.0.0",
- "is-path-inside": "^3.0.3",
"json-stable-stringify-without-jsonify": "^1.0.1",
- "levn": "^0.4.1",
- "lodash.merge": "^4.6.2",
- "minimatch": "^3.1.2",
+ "minimatch": "^10.2.4",
"natural-compare": "^1.4.0",
- "optionator": "^0.9.3",
- "strip-ansi": "^6.0.1",
- "text-table": "^0.2.0"
+ "optionator": "^0.9.3"
},
"bin": {
"eslint": "bin/eslint.js"
},
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
},
"funding": {
"url": "https://eslint.org/donate"
+ },
+ "peerDependencies": {
+ "jiti": "*"
+ },
+ "peerDependenciesMeta": {
+ "jiti": {
+ "optional": true
+ }
}
},
"node_modules/eslint-config-mourner": {
- "version": "4.0.1",
- "resolved": "https://registry.npmjs.org/eslint-config-mourner/-/eslint-config-mourner-4.0.1.tgz",
- "integrity": "sha512-seylu4qdUc7kabx42zEedJiCyRDYqwsZLFPPnMRntmOFOQv6cKoM+FqhYpLKZ5dF7A7wW6mCympQSkg6RVxGlg==",
+ "version": "5.0.1",
+ "resolved": "https://registry.npmjs.org/eslint-config-mourner/-/eslint-config-mourner-5.0.1.tgz",
+ "integrity": "sha512-+bJjgJanAP1Nk0HIO1aV7CJZLa7zl/ymaFSff+HeSLHr9ifuHc8nX9dNdrjO7GnGdrgRMrmrAq3TCqfwj6NHiQ==",
"dev": true,
"license": "ISC",
"dependencies": {
- "@eslint/js": "^9.5.0",
- "@stylistic/eslint-plugin-js": "^2.2.2"
+ "@eslint/js": "^10.0.1",
+ "@stylistic/eslint-plugin": "^5.10.0",
+ "globals": "^17.6.0"
}
},
"node_modules/eslint-scope": {
- "version": "8.0.1",
- "resolved": "https://registry.npmjs.org/eslint-scope/-/eslint-scope-8.0.1.tgz",
- "integrity": "sha512-pL8XjgP4ZOmmwfFE8mEhSxA7ZY4C+LWyqjQ3o4yWkkmD0qcMT9kkW3zWHOczhWcjTSgqycYAgwSlXvZltv65og==",
+ "version": "9.1.2",
+ "resolved": "https://registry.npmjs.org/eslint-scope/-/eslint-scope-9.1.2.tgz",
+ "integrity": "sha512-xS90H51cKw0jltxmvmHy2Iai1LIqrfbw57b79w/J7MfvDfkIkFZ+kj6zC3BjtUwh150HsSSdxXZcsuv72miDFQ==",
"dev": true,
"license": "BSD-2-Clause",
"dependencies": {
+ "@types/esrecurse": "^4.3.1",
+ "@types/estree": "^1.0.8",
"esrecurse": "^4.3.0",
"estraverse": "^5.2.0"
},
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
},
"funding": {
"url": "https://opencollective.com/eslint"
}
},
"node_modules/eslint-visitor-keys": {
- "version": "4.0.0",
- "resolved": "https://registry.npmjs.org/eslint-visitor-keys/-/eslint-visitor-keys-4.0.0.tgz",
- "integrity": "sha512-OtIRv/2GyiF6o/d8K7MYKKbXrOUBIK6SfkIRM4Z0dY3w+LiQ0vy3F57m0Z71bjbyeiWFiHJ8brqnmE6H6/jEuw==",
+ "version": "5.0.1",
+ "resolved": "https://registry.npmjs.org/eslint-visitor-keys/-/eslint-visitor-keys-5.0.1.tgz",
+ "integrity": "sha512-tD40eHxA35h0PEIZNeIjkHoDR4YjjJp34biM0mDvplBe//mB+IHCqHDGV7pxF+7MklTvighcCPPZC7ynWyjdTA==",
"dev": true,
"license": "Apache-2.0",
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
},
"funding": {
"url": "https://opencollective.com/eslint"
}
},
"node_modules/espree": {
- "version": "10.1.0",
- "resolved": "https://registry.npmjs.org/espree/-/espree-10.1.0.tgz",
- "integrity": "sha512-M1M6CpiE6ffoigIOWYO9UDP8TMUw9kqb21tf+08IgDYjCsOvCuDt4jQcZmoYxx+w7zlKw9/N0KXfto+I8/FrXA==",
+ "version": "11.2.0",
+ "resolved": "https://registry.npmjs.org/espree/-/espree-11.2.0.tgz",
+ "integrity": "sha512-7p3DrVEIopW1B1avAGLuCSh1jubc01H2JHc8B4qqGblmg5gI9yumBgACjWo4JlIc04ufug4xJ3SQI8HkS/Rgzw==",
"dev": true,
"license": "BSD-2-Clause",
"dependencies": {
- "acorn": "^8.12.0",
+ "acorn": "^8.16.0",
"acorn-jsx": "^5.3.2",
- "eslint-visitor-keys": "^4.0.0"
+ "eslint-visitor-keys": "^5.0.1"
},
"engines": {
- "node": "^18.18.0 || ^20.9.0 || >=21.1.0"
+ "node": "^20.19.0 || ^22.13.0 || >=24"
},
"funding": {
"url": "https://opencollective.com/eslint"
}
},
"node_modules/esquery": {
- "version": "1.5.0",
- "resolved": "https://registry.npmjs.org/esquery/-/esquery-1.5.0.tgz",
- "integrity": "sha512-YQLXUplAwJgCydQ78IMJywZCceoqk1oH01OERdSAJc/7U2AylwjhSCLDEtqwg811idIS/9fIU5GjG73IgjKMVg==",
+ "version": "1.7.0",
+ "resolved": "https://registry.npmjs.org/esquery/-/esquery-1.7.0.tgz",
+ "integrity": "sha512-Ap6G0WQwcU/LHsvLwON1fAQX9Zp0A2Y6Y/cJBl9r/JbW90Zyg4/zbG6zzKa2OTALELarYHmKu0GhpM5EO+7T0g==",
"dev": true,
"license": "BSD-3-Clause",
"dependencies": {
@@ -600,16 +601,6 @@
"dev": true,
"license": "MIT"
},
- "node_modules/fastq": {
- "version": "1.17.1",
- "resolved": "https://registry.npmjs.org/fastq/-/fastq-1.17.1.tgz",
- "integrity": "sha512-sRVD3lWVIXWg6By68ZN7vho9a1pQcN/WBFaAAsDDFzlJjvoGx0P8z7V1t72grFJfJhu3YPZBuu25f7Kaw2jN1w==",
- "dev": true,
- "license": "ISC",
- "dependencies": {
- "reusify": "^1.0.4"
- }
- },
"node_modules/file-entry-cache": {
"version": "8.0.0",
"resolved": "https://registry.npmjs.org/file-entry-cache/-/file-entry-cache-8.0.0.tgz",
@@ -655,9 +646,9 @@
}
},
"node_modules/flatted": {
- "version": "3.3.1",
- "resolved": "https://registry.npmjs.org/flatted/-/flatted-3.3.1.tgz",
- "integrity": "sha512-X8cqMLLie7KsNUDSdzeN8FYK9rEt4Dt67OsG/DNGnYTSDBG4uFAJFBnUeiV+zCVAvwFy56IjM9sH51jVaEhNxw==",
+ "version": "3.4.2",
+ "resolved": "https://registry.npmjs.org/flatted/-/flatted-3.4.2.tgz",
+ "integrity": "sha512-PjDse7RzhcPkIJwy5t7KPWQSZ9cAbzQXcafsetQoD7sOJRQlGikNbx7yZp2OotDnJyrDcbyRq3Ttb18iYOqkxA==",
"dev": true,
"license": "ISC"
},
@@ -675,9 +666,9 @@
}
},
"node_modules/globals": {
- "version": "14.0.0",
- "resolved": "https://registry.npmjs.org/globals/-/globals-14.0.0.tgz",
- "integrity": "sha512-oahGvuMGQlPw/ivIYBjVSrWAfWLBeku5tpPE2fOPLi+WHffIWbuh2tCjhyQhTBPMf5E9jDEH4FOmTYgYwbKwtQ==",
+ "version": "17.7.0",
+ "resolved": "https://registry.npmjs.org/globals/-/globals-17.7.0.tgz",
+ "integrity": "sha512-Czmyns5dUsq4seFBR/Kdydhmo8y9kC79hiSkPn0YcGtNnYWnrgt0vjrSjx9tspoDGWm2CMarffRuLjM4xUz8xg==",
"dev": true,
"license": "MIT",
"engines": {
@@ -687,43 +678,16 @@
"url": "https://github.com/sponsors/sindresorhus"
}
},
- "node_modules/has-flag": {
- "version": "4.0.0",
- "resolved": "https://registry.npmjs.org/has-flag/-/has-flag-4.0.0.tgz",
- "integrity": "sha512-EykJT/Q1KjTWctppgIAgfSO0tKVuZUjhgMr17kqTumMl6Afv3EISleU7qZUzoXDFTAHTDC4NOoG/ZxU3EvlMPQ==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=8"
- }
- },
"node_modules/ignore": {
- "version": "5.3.1",
- "resolved": "https://registry.npmjs.org/ignore/-/ignore-5.3.1.tgz",
- "integrity": "sha512-5Fytz/IraMjqpwfd34ke28PTVMjZjJG2MPn5t7OE4eUCUNf8BAa7b5WUS9/Qvr6mwOQS7Mk6vdsMno5he+T8Xw==",
+ "version": "5.3.2",
+ "resolved": "https://registry.npmjs.org/ignore/-/ignore-5.3.2.tgz",
+ "integrity": "sha512-hsBTNUqQTDwkWtcdYI2i06Y/nUBEsNEDJKjWdigLvegy8kDuJAS8uRlpkkcQpyEXL0Z/pjDy5HBmMjRCJ2gq+g==",
"dev": true,
"license": "MIT",
"engines": {
"node": ">= 4"
}
},
- "node_modules/import-fresh": {
- "version": "3.3.0",
- "resolved": "https://registry.npmjs.org/import-fresh/-/import-fresh-3.3.0.tgz",
- "integrity": "sha512-veYYhQa+D1QBKznvhUHxb8faxlrwUnxseDAbAp457E0wLNio2bOSKnjYDhMj+YiAq61xrMGhQk9iXVk5FzgQMw==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "parent-module": "^1.0.0",
- "resolve-from": "^4.0.0"
- },
- "engines": {
- "node": ">=6"
- },
- "funding": {
- "url": "https://github.com/sponsors/sindresorhus"
- }
- },
"node_modules/imurmurhash": {
"version": "0.1.4",
"resolved": "https://registry.npmjs.org/imurmurhash/-/imurmurhash-0.1.4.tgz",
@@ -757,16 +721,6 @@
"node": ">=0.10.0"
}
},
- "node_modules/is-path-inside": {
- "version": "3.0.3",
- "resolved": "https://registry.npmjs.org/is-path-inside/-/is-path-inside-3.0.3.tgz",
- "integrity": "sha512-Fd4gABb+ycGAmKou8eMftCupSir5lRxqf4aD/vd0cD2qc4HL07OjCeuHMr8Ro4CoMaeCKDB0/ECBOVWjTwUvPQ==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=8"
- }
- },
"node_modules/isexe": {
"version": "2.0.0",
"resolved": "https://registry.npmjs.org/isexe/-/isexe-2.0.0.tgz",
@@ -774,19 +728,6 @@
"dev": true,
"license": "ISC"
},
- "node_modules/js-yaml": {
- "version": "4.1.0",
- "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.1.0.tgz",
- "integrity": "sha512-wpxZs9NoxZaJESJGIZTyDEaYpl0FKSA+FB9aJiyemKhMwkxQg63h4T1KJgUGHpTqPDNRcmmYLugrRjJlBtWvRA==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "argparse": "^2.0.1"
- },
- "bin": {
- "js-yaml": "bin/js-yaml.js"
- }
- },
"node_modules/json-buffer": {
"version": "3.0.1",
"resolved": "https://registry.npmjs.org/json-buffer/-/json-buffer-3.0.1.tgz",
@@ -848,30 +789,26 @@
"url": "https://github.com/sponsors/sindresorhus"
}
},
- "node_modules/lodash.merge": {
- "version": "4.6.2",
- "resolved": "https://registry.npmjs.org/lodash.merge/-/lodash.merge-4.6.2.tgz",
- "integrity": "sha512-0KpjqXRVvrYyCsX1swR/XTK0va6VQkQM6MNo7PqW77ByjAhoARA8EfrP1N4+KlKj8YS0ZUCtRT/YUuhyYDujIQ==",
- "dev": true,
- "license": "MIT"
- },
"node_modules/minimatch": {
- "version": "3.1.2",
- "resolved": "https://registry.npmjs.org/minimatch/-/minimatch-3.1.2.tgz",
- "integrity": "sha512-J7p63hRiAjw1NDEww1W7i37+ByIrOWO5XQQAzZ3VOcL0PNybwpfmV/N05zFAzwQ9USyEcX6t3UO+K5aqBQOIHw==",
+ "version": "10.2.5",
+ "resolved": "https://registry.npmjs.org/minimatch/-/minimatch-10.2.5.tgz",
+ "integrity": "sha512-MULkVLfKGYDFYejP07QOurDLLQpcjk7Fw+7jXS2R2czRQzR56yHRveU5NDJEOviH+hETZKSkIk5c+T23GjFUMg==",
"dev": true,
- "license": "ISC",
+ "license": "BlueOak-1.0.0",
"dependencies": {
- "brace-expansion": "^1.1.7"
+ "brace-expansion": "^5.0.5"
},
"engines": {
- "node": "*"
+ "node": "18 || 20 || >=22"
+ },
+ "funding": {
+ "url": "https://github.com/sponsors/isaacs"
}
},
"node_modules/ms": {
- "version": "2.1.2",
- "resolved": "https://registry.npmjs.org/ms/-/ms-2.1.2.tgz",
- "integrity": "sha512-sGkPx+VjMtmA6MX27oA4FBFELFCZZ4S4XqeGOXCv68tT+jb3vk/RyaKWP0PTKyWtmLSM0b+adUTEvbs1PEaH2w==",
+ "version": "2.1.3",
+ "resolved": "https://registry.npmjs.org/ms/-/ms-2.1.3.tgz",
+ "integrity": "sha512-6FlzubTLZG3J2a/NVCAleEhjzq5oxgHyaCU9yYXvcLsvoVaHJq/s5xXI6/XXP6tz7R9xAOtHnSO/tXtF3WRTlA==",
"dev": true,
"license": "MIT"
},
@@ -932,19 +869,6 @@
"url": "https://github.com/sponsors/sindresorhus"
}
},
- "node_modules/parent-module": {
- "version": "1.0.1",
- "resolved": "https://registry.npmjs.org/parent-module/-/parent-module-1.0.1.tgz",
- "integrity": "sha512-GQ2EWRpQV8/o+Aw8YqtfZZPfNRWZYkbidE9k5rpl/hC3vtHHBfGm2Ifi6qWV+coDGkrUKZAxE3Lot5kcsRlh+g==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "callsites": "^3.0.0"
- },
- "engines": {
- "node": ">=6"
- }
- },
"node_modules/path-exists": {
"version": "4.0.0",
"resolved": "https://registry.npmjs.org/path-exists/-/path-exists-4.0.0.tgz",
@@ -965,6 +889,19 @@
"node": ">=8"
}
},
+ "node_modules/picomatch": {
+ "version": "4.0.4",
+ "resolved": "https://registry.npmjs.org/picomatch/-/picomatch-4.0.4.tgz",
+ "integrity": "sha512-QP88BAKvMam/3NxH6vj2o21R6MjxZUAd6nlwAS/pnGvN9IVLocLHxGYIzFhg6fUQ+5th6P4dv4eW9jX3DSIj7A==",
+ "dev": true,
+ "license": "MIT",
+ "engines": {
+ "node": ">=12"
+ },
+ "funding": {
+ "url": "https://github.com/sponsors/jonschlinkert"
+ }
+ },
"node_modules/prelude-ls": {
"version": "1.2.1",
"resolved": "https://registry.npmjs.org/prelude-ls/-/prelude-ls-1.2.1.tgz",
@@ -985,72 +922,6 @@
"node": ">=6"
}
},
- "node_modules/queue-microtask": {
- "version": "1.2.3",
- "resolved": "https://registry.npmjs.org/queue-microtask/-/queue-microtask-1.2.3.tgz",
- "integrity": "sha512-NuaNSa6flKT5JaSYQzJok04JzTL1CA6aGhv5rfLW3PgqA+M2ChpZQnAC8h8i4ZFkBS8X5RqkDBHA7r4hej3K9A==",
- "dev": true,
- "funding": [
- {
- "type": "github",
- "url": "https://github.com/sponsors/feross"
- },
- {
- "type": "patreon",
- "url": "https://www.patreon.com/feross"
- },
- {
- "type": "consulting",
- "url": "https://feross.org/support"
- }
- ],
- "license": "MIT"
- },
- "node_modules/resolve-from": {
- "version": "4.0.0",
- "resolved": "https://registry.npmjs.org/resolve-from/-/resolve-from-4.0.0.tgz",
- "integrity": "sha512-pb/MYmXstAkysRFx8piNI1tGFNQIFA3vkE3Gq4EuA1dF6gHp/+vgZqsCGJapvy8N3Q+4o7FwvquPJcnZ7RYy4g==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=4"
- }
- },
- "node_modules/reusify": {
- "version": "1.0.4",
- "resolved": "https://registry.npmjs.org/reusify/-/reusify-1.0.4.tgz",
- "integrity": "sha512-U9nH88a3fc/ekCF1l0/UP1IosiuIjyTh7hBvXVMHYgVcfGvt897Xguj2UOLDeI5BG2m7/uwyaLVT6fbtCwTyzw==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "iojs": ">=1.0.0",
- "node": ">=0.10.0"
- }
- },
- "node_modules/run-parallel": {
- "version": "1.2.0",
- "resolved": "https://registry.npmjs.org/run-parallel/-/run-parallel-1.2.0.tgz",
- "integrity": "sha512-5l4VyZR86LZ/lDxZTR6jqL8AFE2S0IFLMP26AbjsLVADxHdhB/c0GUsH+y39UfCi3dzz8OlQuPmnaJOMoDHQBA==",
- "dev": true,
- "funding": [
- {
- "type": "github",
- "url": "https://github.com/sponsors/feross"
- },
- {
- "type": "patreon",
- "url": "https://www.patreon.com/feross"
- },
- {
- "type": "consulting",
- "url": "https://feross.org/support"
- }
- ],
- "license": "MIT",
- "dependencies": {
- "queue-microtask": "^1.2.2"
- }
- },
"node_modules/shebang-command": {
"version": "2.0.0",
"resolved": "https://registry.npmjs.org/shebang-command/-/shebang-command-2.0.0.tgz",
@@ -1074,52 +945,6 @@
"node": ">=8"
}
},
- "node_modules/strip-ansi": {
- "version": "6.0.1",
- "resolved": "https://registry.npmjs.org/strip-ansi/-/strip-ansi-6.0.1.tgz",
- "integrity": "sha512-Y38VPSHcqkFrCpFnQ9vuSXmquuv5oXOKpGeT6aGrr3o3Gc9AlVa6JBfUSOCnbxGGZF+/0ooI7KrPuUSztUdU5A==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "ansi-regex": "^5.0.1"
- },
- "engines": {
- "node": ">=8"
- }
- },
- "node_modules/strip-json-comments": {
- "version": "3.1.1",
- "resolved": "https://registry.npmjs.org/strip-json-comments/-/strip-json-comments-3.1.1.tgz",
- "integrity": "sha512-6fPc+R4ihwqP6N/aIv2f1gMH8lOVtWQHoqC4yK6oSDVVocumAsfCqjkXnqiYMhmMwS/mEHLp7Vehlt3ql6lEig==",
- "dev": true,
- "license": "MIT",
- "engines": {
- "node": ">=8"
- },
- "funding": {
- "url": "https://github.com/sponsors/sindresorhus"
- }
- },
- "node_modules/supports-color": {
- "version": "7.2.0",
- "resolved": "https://registry.npmjs.org/supports-color/-/supports-color-7.2.0.tgz",
- "integrity": "sha512-qpCAvRl9stuOHveKsn7HncJRvv501qIacKzQlO/+Lwxc9+0q2wLyv4Dfvt80/DPn2pqOBsJdDiogXGR9+OvwRw==",
- "dev": true,
- "license": "MIT",
- "dependencies": {
- "has-flag": "^4.0.0"
- },
- "engines": {
- "node": ">=8"
- }
- },
- "node_modules/text-table": {
- "version": "0.2.0",
- "resolved": "https://registry.npmjs.org/text-table/-/text-table-0.2.0.tgz",
- "integrity": "sha512-N+8UisAXDGk8PFXP4HAzVR9nbfmVJ3zYLAWiTIoqC5v5isinhr+r5uaO8+7r3BMfuNIufIsA7RdpVgacC2cSpw==",
- "dev": true,
- "license": "MIT"
- },
"node_modules/tinyqueue": {
"version": "3.0.0",
"resolved": "https://registry.npmjs.org/tinyqueue/-/tinyqueue-3.0.0.tgz",
=====================================
package.json
=====================================
@@ -1,6 +1,6 @@
{
"name": "polylabel",
- "version": "2.0.1",
+ "version": "2.1.0",
"description": "A JS library for finding optimal label position inside a polygon",
"keywords": [
"polygon",
@@ -14,12 +14,13 @@
"tinyqueue": "^3.0.0"
},
"devDependencies": {
- "eslint": "^9.6.0",
- "eslint-config-mourner": "^4.0.1"
+ "eslint": "^10.5.0",
+ "eslint-config-mourner": "^5.0.1"
},
"scripts": {
"pretest": "eslint *.js test/*.js",
- "test": "node test/test.js"
+ "test": "node test/test.js",
+ "prepublishOnly": "npm test"
},
"files": [
"include",
@@ -29,6 +30,6 @@
"type": "git",
"url": "https://github.com/mapbox/polylabel.git"
},
- "author": "Vladimir Agafonkin",
+ "author": "Volodymyr Agafonkin",
"license": "ISC"
}
=====================================
polylabel.js
=====================================
@@ -1,6 +1,9 @@
import Queue from 'tinyqueue';
+// number of consecutive edges grouped under a single bounding box for block-skip
+const K = 32;
+
export default function polylabel(polygon, precision = 1.0, debug = false) {
// find the bounding box of the outer ring
let minX = Infinity;
@@ -25,20 +28,41 @@ export default function polylabel(polygon, precision = 1.0, debug = false) {
return result;
}
+ // flatten the polygon rings into a single contiguous coordinate buffer for
+ // cache-friendly, pointer-chase-free access in the hot distance loop
+ let numPoints = 0;
+ for (const ring of polygon) numPoints += ring.length;
+ const coords = new Float64Array(numPoints * 2);
+ const ringEnds = []; // end offset into coords for each ring (start = previous end, or 0)
+ let c = 0;
+ for (const ring of polygon) {
+ for (let i = 0; i < ring.length; i++) {
+ coords[c++] = ring[i][0];
+ coords[c++] = ring[i][1];
+ }
+ ringEnds.push(c);
+ }
+
+ const blocks = buildBlocks(coords, ringEnds);
+
// a priority queue of cells in order of their "potential" (max distance to polygon)
const cellQueue = new Queue([], (a, b) => b.max - a.max);
// take centroid as the first best guess
- let bestCell = getCentroidCell(polygon);
+ let bestCell = getCentroidCell(coords, ringEnds, blocks);
// second guess: bounding box centroid
- const bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);
+ const bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, coords, ringEnds, blocks, -Infinity, null);
if (bboxCell.d > bestCell.d) bestCell = bboxCell;
let numProbes = 2;
- function potentiallyQueue(x, y, h) {
- const cell = new Cell(x, y, h, polygon);
+ function potentiallyQueue(x, y, h, seed) {
+ // a cell is only useful if it can beat the best (d > bestCell.d) or is
+ // worth subdividing (max = d + h·√2 > bestCell.d + precision). Both fail
+ // once d ≤ threshold, so the distance scan can bail there early.
+ const threshold = bestCell.d - Math.max(0, h * Math.SQRT2 - precision);
+ const cell = new Cell(x, y, h, coords, ringEnds, blocks, threshold, seed);
numProbes++;
if (cell.max > bestCell.d + precision) cellQueue.push(cell);
@@ -53,23 +77,23 @@ export default function polylabel(polygon, precision = 1.0, debug = false) {
let h = cellSize / 2;
for (let x = minX; x < maxX; x += cellSize) {
for (let y = minY; y < maxY; y += cellSize) {
- potentiallyQueue(x + h, y + h, h);
+ potentiallyQueue(x + h, y + h, h, null);
}
}
while (cellQueue.length) {
// pick the most promising cell from the queue
- const {max, x, y, h: ch} = cellQueue.pop();
+ const cell = cellQueue.pop();
// do not drill down further if there's no chance of a better solution
- if (max - bestCell.d <= precision) break;
-
- // split the cell into four cells
- h = ch / 2;
- potentiallyQueue(x - h, y - h, h);
- potentiallyQueue(x + h, y - h, h);
- potentiallyQueue(x - h, y + h, h);
- potentiallyQueue(x + h, y + h, h);
+ if (cell.max - bestCell.d <= precision) break;
+
+ // split the cell into four cells, seeding each with the parent's nearest segment
+ h = cell.h / 2;
+ potentiallyQueue(cell.x - h, cell.y - h, h, cell);
+ potentiallyQueue(cell.x + h, cell.y - h, h, cell);
+ potentiallyQueue(cell.x - h, cell.y + h, h, cell);
+ potentiallyQueue(cell.x + h, cell.y + h, h, cell);
}
if (debug) {
@@ -81,67 +105,170 @@ export default function polylabel(polygon, precision = 1.0, debug = false) {
return result;
}
-function Cell(x, y, h, polygon) {
+function Cell(x, y, h, coords, ringEnds, blocks, maxD, seed) {
this.x = x; // cell center x
this.y = y; // cell center y
this.h = h; // half the cell size
- this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon
- this.max = this.d + this.h * Math.SQRT2; // max distance to polygon within a cell
+ // nsx1..nsy2 hold the nearest segment found below, so child cells can seed
+ // their scan with it (a child is almost always nearest to the same segment)
+ this.nsx1 = 0; this.nsy1 = 0; this.nsx2 = 0; this.nsy2 = 0;
+ this.d = pointToPolygonDist(this, coords, ringEnds, blocks, maxD, seed); // distance from cell center to polygon
+ this.max = this.d + h * Math.SQRT2; // max distance to polygon within a cell
}
-// signed distance from point to polygon outline (negative if point is outside)
-function pointToPolygonDist(x, y, polygon) {
+// signed distance from cell center to polygon outline (negative if outside),
+// also recording the nearest segment on the cell. maxD is a distance threshold:
+// if a partial result proves the center is no farther than maxD from the outline,
+// the scan bails out early and returns maxD, since the caller has already
+// determined such a cell can't beat the best. seed is the parent cell (or null);
+// its nearest segment is checked first so boundary cells reach the early-out
+// threshold without scanning the whole outline.
+function pointToPolygonDist(cell, coords, ringEnds, blocks, maxD, seed) {
+ const x = cell.x;
+ const y = cell.y;
let inside = false;
let minDistSq = Infinity;
+ const thresholdSq = maxD > 0 ? maxD * maxD : -1;
- for (const ring of polygon) {
- for (let i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
- const a = ring[i];
- const b = ring[j];
+ if (seed !== null) {
+ cell.nsx1 = seed.nsx1; cell.nsy1 = seed.nsy1; cell.nsx2 = seed.nsx2; cell.nsy2 = seed.nsy2;
+ minDistSq = getSegDistSq(x, y, seed.nsx1, seed.nsy1, seed.nsx2, seed.nsy2);
+ if (minDistSq <= thresholdSq) return maxD;
+ }
+
+ const stride = K * 2;
+ const numRings = ringEnds.length;
+ let g = 0; // running block index into bboxes
+ let ringStart = 0;
+
+ for (let r = 0; r < numRings; r++) {
+ const ringEnd = ringEnds[r];
+
+ // previous vertex (b), starting from the last point in the ring; carried
+ // across blocks so each block's first edge connects to the prior vertex
+ let bx = coords[ringEnd - 2];
+ let by = coords[ringEnd - 1];
+
+ for (let s = ringStart; s < ringEnd; s += stride, g += 4) {
+ let end = s + stride;
+ if (end > ringEnd) end = ringEnd;
+ const bminX = blocks[g], bminY = blocks[g + 1], bmaxX = blocks[g + 2], bmaxY = blocks[g + 3];
+
+ // lower bound on the distance from (x, y) to any edge in this block
+ const dx = x < bminX ? bminX - x : x > bmaxX ? x - bmaxX : 0;
+ const dy = y < bminY ? bminY - y : y > bmaxY ? y - bmaxY : 0;
+ const skipDist = dx * dx + dy * dy >= minDistSq;
- if ((a[1] > y !== b[1] > y) &&
- (x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0])) inside = !inside;
+ // this block's edges can only flip ray-cast parity if its bbox straddles
+ // y and extends right of x; else no edge crosses the rightward ray
+ const skipCross = y < bminY || y >= bmaxY || x > bmaxX;
- minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));
+ if (skipDist && skipCross) {
+ bx = coords[end - 2];
+ by = coords[end - 1];
+ continue;
+ }
+
+ for (let i = s; i < end; i += 2) {
+ const ax = coords[i];
+ const ay = coords[i + 1];
+
+ if (!skipCross && (ay > y !== by > y) &&
+ (x < (bx - ax) * (y - ay) / (by - ay) + ax)) inside = !inside;
+
+ if (!skipDist) {
+ const distSq = getSegDistSq(x, y, ax, ay, bx, by);
+ if (distSq < minDistSq) {
+ minDistSq = distSq;
+ cell.nsx1 = ax; cell.nsy1 = ay; cell.nsx2 = bx; cell.nsy2 = by;
+
+ // the point is already close enough to the outline that this cell
+ // can't possibly contain a better label position — stop scanning
+ if (minDistSq <= thresholdSq) return maxD;
+ }
+ }
+
+ bx = ax;
+ by = ay;
+ }
}
+ ringStart = ringEnd;
}
return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq);
}
-// get polygon centroid
-function getCentroidCell(polygon) {
+// precompute one bounding box per block of K consecutive edges (over both
+// endpoints of every edge in it) so the distance scan can skip whole blocks in
+// O(1). The block layout mirrors the flattened coords/ringEnds and is re-derived
+// in the scan, so only the bboxes need storing: a flat [minX,minY,maxX,maxY] run
+// per block, sized upfront from the ring lengths.
+function buildBlocks(coords, ringEnds) {
+ const stride = K * 2;
+ let numBlocks = 0;
+ let ringStart = 0;
+ for (let r = 0; r < ringEnds.length; r++) {
+ numBlocks += Math.ceil((ringEnds[r] - ringStart) / stride);
+ ringStart = ringEnds[r];
+ }
+
+ const blocks = new Float64Array(numBlocks * 4);
+ let g = 0;
+ ringStart = 0;
+ for (let r = 0; r < ringEnds.length; r++) {
+ const ringEnd = ringEnds[r];
+ for (let s = ringStart; s < ringEnd; s += stride, g += 4) {
+ const end = s + stride < ringEnd ? s + stride : ringEnd;
+ const prev = s === ringStart ? ringEnd - 2 : s - 2;
+
+ let minX = coords[prev], minY = coords[prev + 1];
+ let maxX = minX, maxY = minY;
+ for (let i = s; i < end; i += 2) {
+ const px = coords[i], py = coords[i + 1];
+ if (px < minX) minX = px; else if (px > maxX) maxX = px;
+ if (py < minY) minY = py; else if (py > maxY) maxY = py;
+ }
+ blocks[g] = minX; blocks[g + 1] = minY; blocks[g + 2] = maxX; blocks[g + 3] = maxY;
+ }
+ ringStart = ringEnd;
+ }
+
+ return blocks;
+}
+
+// get polygon centroid (over the outer ring, coords[0..ringEnds[0]))
+function getCentroidCell(coords, ringEnds, blocks) {
let area = 0;
let x = 0;
let y = 0;
- const points = polygon[0];
-
- for (let i = 0, len = points.length, j = len - 1; i < len; j = i++) {
- const a = points[i];
- const b = points[j];
- const f = a[0] * b[1] - b[0] * a[1];
- x += (a[0] + b[0]) * f;
- y += (a[1] + b[1]) * f;
+ const end = ringEnds[0];
+
+ for (let i = 0, j = end - 2; i < end; j = i, i += 2) {
+ const ax = coords[i];
+ const ay = coords[i + 1];
+ const bx = coords[j];
+ const by = coords[j + 1];
+ const f = ax * by - bx * ay;
+ x += (ax + bx) * f;
+ y += (ay + by) * f;
area += f * 3;
}
- const centroid = new Cell(x / area, y / area, 0, polygon);
- if (area === 0 || centroid.d < 0) return new Cell(points[0][0], points[0][1], 0, polygon);
+ const centroid = new Cell(x / area, y / area, 0, coords, ringEnds, blocks, -Infinity, null);
+ if (area === 0 || centroid.d < 0) return new Cell(coords[0], coords[1], 0, coords, ringEnds, blocks, -Infinity, null);
return centroid;
}
// get squared distance from a point to a segment
-function getSegDistSq(px, py, a, b) {
- let x = a[0];
- let y = a[1];
- let dx = b[0] - x;
- let dy = b[1] - y;
+function getSegDistSq(px, py, x, y, bx, by) {
+ let dx = bx - x;
+ let dy = by - y;
if (dx !== 0 || dy !== 0) {
const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
if (t > 1) {
- x = b[0];
- y = b[1];
+ x = bx;
+ y = by;
} else if (t > 0) {
x += dx * t;
=====================================
test/test.cpp deleted
=====================================
@@ -1,64 +0,0 @@
-#include <mapbox/polylabel.hpp>
-
-#include <rapidjson/document.h>
-#include <rapidjson/writer.h>
-#include <rapidjson/stringbuffer.h>
-
-#include <cassert>
-#include <fstream>
-#include <sstream>
-#include <iostream>
-
-using namespace mapbox;
-
-// Use the CrtAllocator, because the MemoryPoolAllocator is broken on ARM
-// https://github.com/miloyip/rapidjson/issues/200, 301, 388
-using rapidjson_allocator = rapidjson::CrtAllocator;
-using rapidjson_document = rapidjson::GenericDocument<rapidjson::UTF8<>, rapidjson_allocator>;
-using rapidjson_value = rapidjson::GenericValue<rapidjson::UTF8<>, rapidjson_allocator>;
-
-geometry::polygon<double> fixture(const std::string& path) {
- std::ifstream t(path.c_str());
- std::stringstream buffer;
- buffer << t.rdbuf();
-
- rapidjson_document d;
- d.Parse(buffer.str().c_str());
-
- geometry::polygon<double> result;
-
- for (const auto& ringArray : d.GetArray()) {
- geometry::linear_ring<double> ring;
- for (const auto& point : ringArray.GetArray()) {
- ring.push_back({
- point[0].GetDouble(),
- point[1].GetDouble()
- });
- }
- result.push_back(std::move(ring));
- }
-
- return result;
-}
-
-int main() {
- geometry::polygon<double> water1 = fixture("./test/fixtures/water1.json");
- geometry::polygon<double> water2 = fixture("./test/fixtures/water2.json");
-
- // finds pole of inaccessibility for water1 and precision 1
- assert(polylabel(water1, 1.0) == geometry::point<double>(3865.85009765625, 2124.87841796875));
-
- // finds pole of inaccessibility for water1 and precision 50
- assert(polylabel(water1, 50.0) == geometry::point<double>(3854.296875, 2123.828125));
-
- // finds pole of inaccessibility for water2 and default precision 1
- assert(polylabel(water2) == geometry::point<double>(3263.5, 3263.5));
-
- // works on degenerate polygons
- assert(polylabel(geometry::polygon<double>({{{0, 0}, {1, 0}, {2, 0}, {0, 0}}}))
- == geometry::point<double>(0, 0));
- assert(polylabel(geometry::polygon<double>({{{0, 0}, {1, 0}, {1, 1}, {1, 0}, {0, 0}}}))
- == geometry::point<double>(0, 0));
-
- return 0;
-}
=====================================
test/test.js
=====================================
@@ -1,10 +1,8 @@
import polylabel from '../polylabel.js';
import test from 'node:test';
import assert from 'node:assert/strict';
-import {readFileSync} from 'fs';
-
-const water1 = JSON.parse(readFileSync(new URL('fixtures/water1.json', import.meta.url)));
-const water2 = JSON.parse(readFileSync(new URL('fixtures/water2.json', import.meta.url)));
+import water1 from './fixtures/water1.json' with {type: 'json'};
+import water2 from './fixtures/water2.json' with {type: 'json'};
test('finds pole of inaccessibility for water1 and precision 1', () => {
const p = polylabel(water1, 1);
View it on GitLab: https://salsa.debian.org/debian-gis-team/mapbox-polylabel/-/commit/6b5982af2b69a28724aa2cf9fa5796d149385f00
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/mapbox-polylabel/-/commit/6b5982af2b69a28724aa2cf9fa5796d149385f00
You're receiving this email because of your account on salsa.debian.org. Manage all notifications: https://salsa.debian.org/-/profile/notifications | Help: https://salsa.debian.org/help
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://alioth-lists.debian.net/pipermail/pkg-grass-devel/attachments/20260625/994569ac/attachment-0001.htm>
More information about the Pkg-grass-devel
mailing list