polylabel
A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
Science Score: 44.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
○Academic publication links
-
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (9.5%) to scientific vocabulary
Repository
A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
Basic Info
Statistics
- Stars: 1,472
- Watchers: 153
- Forks: 153
- Open Issues: 16
- Releases: 0
Metadata Files
README.md
polylabel 
A fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon outline (not to be confused with centroid), implemented as a JavaScript library. Useful for optimal placement of a text label on a polygon.
It's an iterative grid algorithm, inspired by paper by Garcia-Castellanos & Lombardo, 2007. Unlike the one in the paper, this algorithm:
- guarantees finding global optimum within the given precision
- is many times faster (10-40x)
How the algorithm works
This is an iterative grid-based algorithm, which starts by covering the polygon with big square cells and then iteratively splitting them in the order of the most promising ones, while aggressively pruning uninteresting cells.
- Generate initial square cells that fully cover the polygon (with cell size equal to either width or height, whichever is lower). Calculate distance from the center of each cell to the outer polygon, using negative value if the point is outside the polygon (detected by ray-casting).
- Put the cells into a priority queue sorted by the maximum potential distance from a point inside a cell, defined as a sum of the distance from the center and the cell radius (equal to
cell_size * sqrt(2) / 2). - Calculate the distance from the centroid of the polygon and pick it as the first "best so far".
- Pull out cells from the priority queue one by one. If a cell's distance is better than the current best, save it as such.
Then, if the cell potentially contains a better solution that the current best (
cell_max - best_dist > precision), split it into 4 children cells and put them in the queue. - Stop the algorithm when we have exhausted the queue and return the best cell's center as the pole of inaccessibility. It will be guaranteed to be a global optimum within the given precision.
JavaScript Usage
Given polygon coordinates in
GeoJSON-like format (an array of arrays of [x, y] points)
and precision (1.0 by default),
Polylabel returns the pole of inaccessibility coordinate in [x, y] format. The distance to the closest polygon point (in input units) is included as a distance property.
js
const p = polylabel([[[0, 0], [1, 0], ...]], 1.0);
const distance = p.distance;
Be careful to pick precision appropriate for the input units. E.g. in case of geographic coordinates (longitude and latitude), 0.000001 is appropriate, while the default (1.0) would be too imprecise.
TypeScript
TypeScript type definitions
are available via npm install --save @types/polylabel.
C++ Usage
It is recommended to install polylabel via mason. You will also need to install its dependencies: geometry.hpp and variant.
```C++
include
int main() {
mapbox::geometry::polygon
Ports to other languages
- andrewharvey/geojson-polygon-labels (CLI)
- Twista/python-polylabel (Python)
- Shapely (Python)
- polylabelr (R)
- polylabel-rs (Rust)
- php-polylabel (PHP)
- dart_polylabel (Dart)
- ruby-polylabel (Ruby)
- Polylabel.jl (Julia)
- geobase (Dart)
Owner
- Name: Mapbox
- Login: mapbox
- Kind: organization
- Location: Washington DC
- Website: https://www.mapbox.com
- Twitter: mapbox
- Repositories: 855
- Profile: https://github.com/mapbox
Mapbox is the location data platform for mobile and web applications. We're changing the way people move around cities and explore our world.
Citation (CITATION.cff)
cff-version: 1.2.0
title: "Polylabel: a fast algorithm for finding the pole of inaccessibility of a polygon"
message: "Please cite this software using these metadata."
type: software
url: https://github.com/mapbox/polylabel
date-released: 2016-07-11
authors:
- given-names: Volodymyr
family-names: Agafonkin
email: agafonkin@gmail.com
affiliation: Mapbox
GitHub Events
Total
- Issues event: 2
- Watch event: 46
- Delete event: 1
- Issue comment event: 2
- Push event: 1
- Pull request review event: 1
- Pull request event: 1
- Fork event: 5
- Create event: 1
Last Year
- Issues event: 2
- Watch event: 46
- Delete event: 1
- Issue comment event: 2
- Push event: 1
- Pull request review event: 1
- Pull request event: 1
- Fork event: 5
- Create event: 1
Committers
Last synced: 10 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Vladimir Agafonkin | a****n@g****m | 49 |
| Denis | c****s@g****m | 3 |
| John Firebaugh | j****h@g****m | 2 |
| Thiago Marcos P. Santos | t****s@g****m | 2 |
| monst | 5****e | 2 |
| Andrew Harvey | a****4@g****m | 1 |
| André Sousa | a****a@g****m | 1 |
| Anshul Singhvi | a****i@g****m | 1 |
| Bruno de Oliveira Abinader | b****o@m****m | 1 |
| Curran Kelleher | c****r@g****m | 1 |
| Daniel Liebner | d****r@g****m | 1 |
| Evan Locke | e****e | 1 |
| Frédéric Planté | f****e | 1 |
| Jacques Kvam | j****m@g****m | 1 |
| Johan Larsson | 1****s | 1 |
| Lean Rada | g****0@g****m | 1 |
| Michal Haták | me@t****z | 1 |
| Microsoft Provenance Contributions | e****e@m****m | 1 |
| Steve Bennett | me@s****e | 1 |
| Steve Hollasch | s****e@h****t | 1 |
| Tom MacWright | t****m@m****g | 1 |
| Zachary Bennett | z****0@H****m | 1 |
| navispatial | 8****l | 1 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 9 months ago
All Time
- Total issues: 71
- Total pull requests: 39
- Average time to close issues: 6 months
- Average time to close pull requests: 2 months
- Total issue authors: 62
- Total pull request authors: 28
- Average comments per issue: 2.45
- Average comments per pull request: 1.44
- Merged pull requests: 28
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 3
- Pull requests: 2
- Average time to close issues: N/A
- Average time to close pull requests: about 23 hours
- Issue authors: 3
- Pull request authors: 2
- Average comments per issue: 0.0
- Average comments per pull request: 0.0
- Merged pull requests: 2
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- hollasch (6)
- jingsam (2)
- Falke-Design (2)
- iomturner (2)
- NMC92 (2)
- andrewharvey (1)
- inaferando (1)
- Kamilius (1)
- Fil (1)
- paomedia (1)
- DaniBarca (1)
- ecoinomist (1)
- MikkoSteerpath (1)
- zlavergne (1)
- mohammedX6 (1)
Pull Request Authors
- stevage (4)
- DenisCarriere (4)
- mourner (4)
- curran (3)
- yukulele (2)
- tmpsantos (2)
- FreshLlamanade (2)
- asinghvi17 (2)
- hollasch (2)
- brunoabinader (1)
- Kalabasa (1)
- andrewharvey (1)
- msftenhanceprovenance (1)
- tmcw (1)
- mapoor (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 2
-
Total downloads:
- npm 965,667 last-month
- Total docker downloads: 353,282
-
Total dependent packages: 77
(may contain duplicates) -
Total dependent repositories: 2,326
(may contain duplicates) - Total versions: 17
- Total maintainers: 29
npmjs.org: polylabel
A JS library for finding optimal label position inside a polygon
- Homepage: https://github.com/mapbox/polylabel#readme
- License: ISC
-
Latest release: 2.0.1
published over 1 year ago
Rankings
Maintainers (29)
proxy.golang.org: github.com/mapbox/polylabel
- Documentation: https://pkg.go.dev/github.com/mapbox/polylabel#section-documentation
- License: other
-
Latest release: v2.0.1+incompatible
published over 1 year ago
Rankings
Dependencies
- eslint ^7.0.0 development
- eslint-config-mourner ^2.0.1 development
- tape ^5.0.0 development
- tinyqueue ^2.0.3