polylabel - npm Package Compare versions

Comparing version 1.1.0 to 2.0.0

package.json

 {
   "name": "polylabel",
-  "version": "1.1.0",
+  "version": "2.0.0",
   "description": "A JS library for finding optimal label position inside a polygon",
+  "keywords": [
+    "polygon",
+    "geometry",
+    "algorithm"
+  ],
   "main": "polylabel.js",
+  "type": "module",
+  "dependencies": {
+    "tinyqueue": "^2.0.3"
+  },
+  "devDependencies": {
+    "eslint": "^9.5.0",
+    "eslint-config-mourner": "^4.0.0"
+  },
   "scripts": {
     "pretest": "eslint *.js test/*.js",
-    "test": "tape test/test.js"
+    "test": "node test/test.js"
   },
-  "keywords": [],
-  "author": "Vladimir Agafonkin",
-  "license": "ISC",
   "files": [
@@ -17,13 +27,8 @@ "include",
   ],
-  "devDependencies": {
-    "eslint": "^7.0.0",
-    "eslint-config-mourner": "^2.0.1",
-    "tape": "^5.0.0"
+  "repository": {
+    "type": "git",
+    "url": "https://github.com/mapbox/polylabel.git"
   },
-  "eslintConfig": {
-    "extends": "mourner"
-  },
-  "dependencies": {
-    "tinyqueue": "^2.0.3"
-  }
+  "author": "Vladimir Agafonkin",
+  "license": "ISC"
 }

polylabel.js

@@ -1,30 +0,24 @@
-'use strict';
 
-var Queue = require('tinyqueue');
+import Queue from 'tinyqueue';
 
-if (Queue.default) Queue = Queue.default; // temporary webpack fix
+export default function polylabel(polygon, precision = 1.0, debug = false) {
+    // find the bounding box of the outer ring
+    let minX = Infinity;
+    let minY = Infinity;
+    let maxX = -Infinity;
+    let maxY = -Infinity;
 
-module.exports = polylabel;
-module.exports.default = polylabel;
-
-function polylabel(polygon, precision, debug) {
-    precision = precision || 1.0;
-
-    // find the bounding box of the outer ring
-    var minX, minY, maxX, maxY;
-    for (var i = 0; i < polygon[0].length; i++) {
-        var p = polygon[0][i];
-        if (!i || p[0] < minX) minX = p[0];
-        if (!i || p[1] < minY) minY = p[1];
-        if (!i || p[0] > maxX) maxX = p[0];
-        if (!i || p[1] > maxY) maxY = p[1];
+    for (const [x, y] of polygon[0]) {
+        if (x < minX) minX = x;
+        if (y < minY) minY = y;
+        if (x > maxX) maxX = x;
+        if (y > maxY) maxY = y;
     }
 
-    var width = maxX - minX;
-    var height = maxY - minY;
-    var cellSize = Math.min(width, height);
-    var h = cellSize / 2;
+    const width = maxX - minX;
+    const height = maxY - minY;
+    const cellSize = Math.max(precision, Math.min(width, height));
 
-    if (cellSize === 0) {
-        var degeneratePoleOfInaccessibility = [minX, minY];
+    if (cellSize === precision) {
+        const degeneratePoleOfInaccessibility = [minX, minY];
         degeneratePoleOfInaccessibility.distance = 0;
@@ -35,23 +29,17 @@ return degeneratePoleOfInaccessibility;
     // a priority queue of cells in order of their "potential" (max distance to polygon)
-    var cellQueue = new Queue(undefined, compareMax);
+    const cellQueue = new Queue(undefined, compareMax);
 
-    // cover polygon with initial cells
-    for (var x = minX; x < maxX; x += cellSize) {
-        for (var y = minY; y < maxY; y += cellSize) {
-            cellQueue.push(new Cell(x + h, y + h, h, polygon));
-        }
-    }
-
     // take centroid as the first best guess
-    var bestCell = getCentroidCell(polygon);
+    let bestCell = getCentroidCell(polygon);
 
-    // special case for rectangular polygons
-    var bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);
+    // second guess: bounding box centroid
+    const bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);
     if (bboxCell.d > bestCell.d) bestCell = bboxCell;
 
-    var numProbes = cellQueue.length;
+    let numProbes = 2;
 
-    while (cellQueue.length) {
-        // pick the most promising cell from the queue
-        var cell = cellQueue.pop();
+    function potentiallyQueue(x, y, h) {
+        const cell = new Cell(x, y, h, polygon);
+        numProbes++;
+        if (cell.max > bestCell.d + precision) cellQueue.push(cell);
 
@@ -61,23 +49,35 @@ // update the best cell if we found a better one
             bestCell = cell;
-            if (debug) console.log('found best %d after %d probes', Math.round(1e4 * cell.d) / 1e4, numProbes);
+            if (debug) console.log(`found best ${Math.round(1e4 * cell.d) / 1e4} after ${numProbes} probes`);
         }
+    }
 
+    // cover polygon with initial cells
+    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);
+        }
+    }
+
+    while (cellQueue.length) {
+        // pick the most promising cell from the queue
+        const cell = cellQueue.pop();
+
         // do not drill down further if there's no chance of a better solution
-        if (cell.max - bestCell.d <= precision) continue;
+        if (cell.max - bestCell.d <= precision) break;
 
         // split the cell into four cells
         h = cell.h / 2;
-        cellQueue.push(new Cell(cell.x - h, cell.y - h, h, polygon));
-        cellQueue.push(new Cell(cell.x + h, cell.y - h, h, polygon));
-        cellQueue.push(new Cell(cell.x - h, cell.y + h, h, polygon));
-        cellQueue.push(new Cell(cell.x + h, cell.y + h, h, polygon));
-        numProbes += 4;
+        potentiallyQueue(cell.x - h, cell.y - h, h);
+        potentiallyQueue(cell.x + h, cell.y - h, h);
+        potentiallyQueue(cell.x - h, cell.y + h, h);
+        potentiallyQueue(cell.x + h, cell.y + h, h);
     }
 
     if (debug) {
-        console.log('num probes: ' + numProbes);
-        console.log('best distance: ' + bestCell.d);
+        console.log(`num probes: ${numProbes}`);
+        console.log(`best distance: ${bestCell.d}`);
     }
 
-    var poleOfInaccessibility = [bestCell.x, bestCell.y];
+    const poleOfInaccessibility = [bestCell.x, bestCell.y];
     poleOfInaccessibility.distance = bestCell.d;
@@ -101,12 +101,10 @@ return poleOfInaccessibility;
 function pointToPolygonDist(x, y, polygon) {
-    var inside = false;
-    var minDistSq = Infinity;
+    let inside = false;
+    let minDistSq = Infinity;
 
-    for (var k = 0; k < polygon.length; k++) {
-        var ring = polygon[k];
+    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];
 
-        for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
-            var a = ring[i];
-            var b = ring[j];
-
             if ((a[1] > y !== b[1] > y) &&
@@ -124,11 +122,11 @@ (x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0])) inside = !inside;
 function getCentroidCell(polygon) {
-    var area = 0;
-    var x = 0;
-    var y = 0;
-    var points = polygon[0];
+    let area = 0;
+    let x = 0;
+    let y = 0;
+    const points = polygon[0];
 
-    for (var i = 0, len = points.length, j = len - 1; i < len; j = i++) {
-        var a = points[i];
-        var b = points[j];
-        var f = a[0] * b[1] - b[0] * a[1];
+    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;
@@ -138,4 +136,5 @@ y += (a[1] + b[1]) * f;
     }
-    if (area === 0) return new Cell(points[0][0], points[0][1], 0, polygon);
-    return new Cell(x / area, y / area, 0, polygon);
+    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);
+    return centroid;
 }
@@ -145,11 +144,10 @@
 function getSegDistSq(px, py, a, b) {
+    let x = a[0];
+    let y = a[1];
+    let dx = b[0] - x;
+    let dy = b[1] - y;
 
-    var x = a[0];
-    var y = a[1];
-    var dx = b[0] - x;
-    var dy = b[1] - y;
-
     if (dx !== 0 || dy !== 0) {
 
-        var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
+        const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
 
@@ -156,0 +154,0 @@ if (t > 1) {

README.md

@@ -1,2 +0,2 @@
-## polylabel [![Build Status](https://travis-ci.org/mapbox/polylabel.svg?branch=master)](https://travis-ci.org/mapbox/polylabel)
+## polylabel [![CI](https://github.com/mapbox/polylabel/actions/workflows/test.yml/badge.svg)](https://github.com/mapbox/polylabel/actions/workflows/test.yml) [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
@@ -45,3 +45,3 @@ A fast algorithm for finding polygon _pole of inaccessibility_,
 
-[TypeScript type definitions](https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/concaveman)
+[TypeScript type definitions](https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/types/polylabel)
 are available via `npm install --save @types/polylabel`.
@@ -70,1 +70,6 @@
 - [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)

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

No repository

Supply chain risk

Package does not have a linked source code repository. Without this field, a package will have no reference to the location of the source code use to generate the package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

15653

increased by3.57%

Dev dependency count

2

decreased by-33.33%

Lines of code

129

increased by0.78%

Number of lines in readme file

74

increased by7.25%

Number of low supply chain risk alerts

0

decreased by-100%

Is type module

Yes

No dependency changes