1.0.2 • Published 2 years ago
polyvisualcenter v1.0.2
polyvisualcenter
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)
It's better than polylabel(https://travis-ci.org/mapbox/polylabel), because it supports:
- any polygon geojson data, while polylabel just support polygon geojson's coordinates
- dynamic precision by geojson data(according to latitude and longitude range), while polylabel default precision is 1.0
- import tinyqueue,and rewritten tinyqueue with typescript
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. and the default value of precision is not 1.0,its default value is according to latitude and longitude range,whicherver is lower.
JavaScript/TypeScript Usage
- Given polygon coordinates in
GeoJSON-like format
and precision (
1.0by default, but actual default is ccording to latitude and longitude range,whicherver is lower):
[
[
[120.63265712299562, 27.766643695655603],
[120.63258859451867, 27.766727452683085],
[120.63253529459223, 27.76663608138034],
[120.63258098024346, 27.766582781453735],
[120.63251625890427, 27.766559938628177],
[120.63243250187679, 27.76658658859145],
[120.63234493771176, 27.766590395728997],
[120.63228402351012, 27.766537095802562],
[120.63222310930826, 27.766460953050398],
[120.63217361651937, 27.766403845986247],
[120.63212031659293, 27.766453338775136],
[120.63212031659293, 27.7665294815273],
[120.63207082380382, 27.766552324352915],
[120.63196422395083, 27.766476181600694],
[120.63195280253808, 27.76640003884853],
[120.63194518826276, 27.76627059616993],
[120.63189569547387, 27.766247753344146],
[120.63184239554732, 27.76626298189467],
[120.63177386707036, 27.766251560481862],
[120.63170914573095, 27.76617541772964],
[120.63168249576768, 27.76606501073894],
[120.63178148134557, 27.7660002893997],
[120.6318766597858, 27.766068817876658],
[120.63192234543703, 27.76606501073894],
[120.63195660967574, 27.766023132225257],
[120.63197564536358, 27.765966025161163],
[120.63197183822604, 27.765893689546488],
[120.63197183822604, 27.765798511106254],
[120.63199087391399, 27.765699525528476],
[120.63205940239106, 27.765699525528476],
[120.63213935228077, 27.765733789767012],
[120.63216219510662, 27.765672875565144],
[120.63216219510662, 27.76562718991397],
[120.63215838796884, 27.76546348299661],
[120.63223072358346, 27.76541018307023],
[120.63234493771176, 27.765398761657423],
[120.63240965905118, 27.765337847455555],
[120.63247057325282, 27.76528454752912],
[120.6326266658948, 27.76526551184105],
[120.63279417994966, 27.765250283290584],
[120.63299215110544, 27.765261704703335],
[120.6331177866465, 27.76530358321719],
[120.63323580791234, 27.765231247602514],
[120.63346423616895, 27.76521601905199],
[120.63360510026052, 27.76526551184105],
[120.63373835007678, 27.765337847455555],
[120.6339820068838, 27.76544064017105],
[120.63420282086508, 27.76537211169409],
[120.63424850651643, 27.76550916864801],
[120.63399342829655, 27.76572617549175],
[120.6338601784804, 27.765916532372273],
[120.6338182999666, 27.766045975050872],
[120.63371170011351, 27.766068817876658],
[120.63365459304941, 27.765973639436368],
[120.63354799319632, 27.765848003895314],
[120.63347946471947, 27.765733789767012],
[120.63335763631585, 27.765573889987365],
[120.63325865073796, 27.76550916864801],
[120.63304164389433, 27.765478711547132],
[120.63286651556416, 27.765482518684678],
[120.6326685444086, 27.765516782923214],
[120.63248960894089, 27.765611961363504],
[120.63240204477597, 27.76577566828064],
[120.63240204477597, 27.76590891809701],
[120.63236397339983, 27.766076432151692],
[120.63251625890427, 27.766099274977478],
[120.63261143734451, 27.766122117803036],
[120.63274468716065, 27.766125924940752],
[120.63280560136252, 27.766179224867187],
[120.63287032270193, 27.76629343899549],
[120.63286270842661, 27.766445724499874],
[120.6327827585369, 27.76661704569233],
[120.6327827585369, 27.76664750279315],
[120.63265712299562, 27.766643695655603]
]
]Polylabel returns the pole of inaccessibility result,the format is :
{
"polygon": [
[
[
120.63265712299562,
27.766643695655603
],
[
120.63258859451867,
27.766727452683085
],
[
120.63253529459223,
27.76663608138034
],
[
120.63258098024346,
27.766582781453735
],
[
120.63251625890427,
27.766559938628177
],
[
120.63243250187679,
27.76658658859145
],
[
120.63234493771176,
27.766590395728997
],
[
120.63228402351012,
27.766537095802562
],
[
120.63222310930826,
27.766460953050398
],
[
120.63217361651937,
27.766403845986247
],
[
120.63212031659293,
27.766453338775136
],
[
120.63212031659293,
27.7665294815273
],
[
120.63207082380382,
27.766552324352915
],
[
120.63196422395083,
27.766476181600694
],
[
120.63195280253808,
27.76640003884853
],
[
120.63194518826276,
27.76627059616993
],
[
120.63189569547387,
27.766247753344146
],
[
120.63184239554732,
27.76626298189467
],
[
120.63177386707036,
27.766251560481862
],
[
120.63170914573095,
27.76617541772964
],
[
120.63168249576768,
27.76606501073894
],
[
120.63178148134557,
27.7660002893997
],
[
120.6318766597858,
27.766068817876658
],
[
120.63192234543703,
27.76606501073894
],
[
120.63195660967574,
27.766023132225257
],
[
120.63197564536358,
27.765966025161163
],
[
120.63197183822604,
27.765893689546488
],
[
120.63197183822604,
27.765798511106254
],
[
120.63199087391399,
27.765699525528476
],
[
120.63205940239106,
27.765699525528476
],
[
120.63213935228077,
27.765733789767012
],
[
120.63216219510662,
27.765672875565144
],
[
120.63216219510662,
27.76562718991397
],
[
120.63215838796884,
27.76546348299661
],
[
120.63223072358346,
27.76541018307023
],
[
120.63234493771176,
27.765398761657423
],
[
120.63240965905118,
27.765337847455555
],
[
120.63247057325282,
27.76528454752912
],
[
120.6326266658948,
27.76526551184105
],
[
120.63279417994966,
27.765250283290584
],
[
120.63299215110544,
27.765261704703335
],
[
120.6331177866465,
27.76530358321719
],
[
120.63323580791234,
27.765231247602514
],
[
120.63346423616895,
27.76521601905199
],
[
120.63360510026052,
27.76526551184105
],
[
120.63373835007678,
27.765337847455555
],
[
120.6339820068838,
27.76544064017105
],
[
120.63420282086508,
27.76537211169409
],
[
120.63424850651643,
27.76550916864801
],
[
120.63399342829655,
27.76572617549175
],
[
120.6338601784804,
27.765916532372273
],
[
120.6338182999666,
27.766045975050872
],
[
120.63371170011351,
27.766068817876658
],
[
120.63365459304941,
27.765973639436368
],
[
120.63354799319632,
27.765848003895314
],
[
120.63347946471947,
27.765733789767012
],
[
120.63335763631585,
27.765573889987365
],
[
120.63325865073796,
27.76550916864801
],
[
120.63304164389433,
27.765478711547132
],
[
120.63286651556416,
27.765482518684678
],
[
120.6326685444086,
27.765516782923214
],
[
120.63248960894089,
27.765611961363504
],
[
120.63240204477597,
27.76577566828064
],
[
120.63240204477597,
27.76590891809701
],
[
120.63236397339983,
27.766076432151692
],
[
120.63251625890427,
27.766099274977478
],
[
120.63261143734451,
27.766122117803036
],
[
120.63274468716065,
27.766125924940752
],
[
120.63280560136252,
27.766179224867187
],
[
120.63287032270193,
27.76629343899549
],
[
120.63286270842661,
27.766445724499874
],
[
120.6327827585369,
27.76661704569233
],
[
120.6327827585369,
27.76664750279315
],
[
120.63265712299562,
27.766643695655603
]
]
],
"poles": [
{
"poleX": 120.63373193482704,
"poleY": 27.765628563680792,
"poleDistance": 0.0002702004952306794
}
]
}- Give polygon geojson data: polygon is polygon coordinates; poles is array of all poles results
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "Polygon",
"coordinates": [
[
[120.63265712299562, 27.766643695655603],
[120.63258859451867, 27.766727452683085],
[120.63253529459223, 27.76663608138034],
[120.63258098024346, 27.766582781453735],
[120.63251625890427, 27.766559938628177],
[120.63243250187679, 27.76658658859145],
[120.63234493771176, 27.766590395728997],
[120.63228402351012, 27.766537095802562],
[120.63222310930826, 27.766460953050398],
[120.63217361651937, 27.766403845986247],
[120.63212031659293, 27.766453338775136],
[120.63212031659293, 27.7665294815273],
[120.63207082380382, 27.766552324352915],
[120.63196422395083, 27.766476181600694],
[120.63195280253808, 27.76640003884853],
[120.63194518826276, 27.76627059616993],
[120.63189569547387, 27.766247753344146],
[120.63184239554732, 27.76626298189467],
[120.63177386707036, 27.766251560481862],
[120.63170914573095, 27.76617541772964],
[120.63168249576768, 27.76606501073894],
[120.63178148134557, 27.7660002893997],
[120.6318766597858, 27.766068817876658],
[120.63192234543703, 27.76606501073894],
[120.63195660967574, 27.766023132225257],
[120.63197564536358, 27.765966025161163],
[120.63197183822604, 27.765893689546488],
[120.63197183822604, 27.765798511106254],
[120.63199087391399, 27.765699525528476],
[120.63205940239106, 27.765699525528476],
[120.63213935228077, 27.765733789767012],
[120.63216219510662, 27.765672875565144],
[120.63216219510662, 27.76562718991397],
[120.63215838796884, 27.76546348299661],
[120.63223072358346, 27.76541018307023],
[120.63234493771176, 27.765398761657423],
[120.63240965905118, 27.765337847455555],
[120.63247057325282, 27.76528454752912],
[120.6326266658948, 27.76526551184105],
[120.63279417994966, 27.765250283290584],
[120.63299215110544, 27.765261704703335],
[120.6331177866465, 27.76530358321719],
[120.63323580791234, 27.765231247602514],
[120.63346423616895, 27.76521601905199],
[120.63360510026052, 27.76526551184105],
[120.63373835007678, 27.765337847455555],
[120.6339820068838, 27.76544064017105],
[120.63420282086508, 27.76537211169409],
[120.63424850651643, 27.76550916864801],
[120.63399342829655, 27.76572617549175],
[120.6338601784804, 27.765916532372273],
[120.6338182999666, 27.766045975050872],
[120.63371170011351, 27.766068817876658],
[120.63365459304941, 27.765973639436368],
[120.63354799319632, 27.765848003895314],
[120.63347946471947, 27.765733789767012],
[120.63335763631585, 27.765573889987365],
[120.63325865073796, 27.76550916864801],
[120.63304164389433, 27.765478711547132],
[120.63286651556416, 27.765482518684678],
[120.6326685444086, 27.765516782923214],
[120.63248960894089, 27.765611961363504],
[120.63240204477597, 27.76577566828064],
[120.63240204477597, 27.76590891809701],
[120.63236397339983, 27.766076432151692],
[120.63251625890427, 27.766099274977478],
[120.63261143734451, 27.766122117803036],
[120.63274468716065, 27.766125924940752],
[120.63280560136252, 27.766179224867187],
[120.63287032270193, 27.76629343899549],
[120.63286270842661, 27.766445724499874],
[120.6327827585369, 27.76661704569233],
[120.6327827585369, 27.76664750279315],
[120.63265712299562, 27.766643695655603]
]
]
},
"properties": {
"FID": 4,
"Center_X": 120.63296550114205,
"Center_Y": 27.765971735867538,
"IDCode": 5,
"Inner_X": 120.63218075490767,
"Inner_Y": 27.765971735867538,
"UserID": 0,
"X": 120.63283550325498,
"Y": 27.76583996976262
},
"id": 4
}
]
}Polylabel returns the pole of inaccessibility result, the format is : polygon is geojson, and its properties will add 3 new field properties, poleX、poleY、poleDistance; poles is array of all poles results
{
"polygon": {
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "Polygon",
"coordinates": [
[
[
120.63265712299562,
27.766643695655603
],
[
120.63258859451867,
27.766727452683085
],
[
120.63253529459223,
27.76663608138034
],
[
120.63258098024346,
27.766582781453735
],
[
120.63251625890427,
27.766559938628177
],
[
120.63243250187679,
27.76658658859145
],
[
120.63234493771176,
27.766590395728997
],
[
120.63228402351012,
27.766537095802562
],
[
120.63222310930826,
27.766460953050398
],
[
120.63217361651937,
27.766403845986247
],
[
120.63212031659293,
27.766453338775136
],
[
120.63212031659293,
27.7665294815273
],
[
120.63207082380382,
27.766552324352915
],
[
120.63196422395083,
27.766476181600694
],
[
120.63195280253808,
27.76640003884853
],
[
120.63194518826276,
27.76627059616993
],
[
120.63189569547387,
27.766247753344146
],
[
120.63184239554732,
27.76626298189467
],
[
120.63177386707036,
27.766251560481862
],
[
120.63170914573095,
27.76617541772964
],
[
120.63168249576768,
27.76606501073894
],
[
120.63178148134557,
27.7660002893997
],
[
120.6318766597858,
27.766068817876658
],
[
120.63192234543703,
27.76606501073894
],
[
120.63195660967574,
27.766023132225257
],
[
120.63197564536358,
27.765966025161163
],
[
120.63197183822604,
27.765893689546488
],
[
120.63197183822604,
27.765798511106254
],
[
120.63199087391399,
27.765699525528476
],
[
120.63205940239106,
27.765699525528476
],
[
120.63213935228077,
27.765733789767012
],
[
120.63216219510662,
27.765672875565144
],
[
120.63216219510662,
27.76562718991397
],
[
120.63215838796884,
27.76546348299661
],
[
120.63223072358346,
27.76541018307023
],
[
120.63234493771176,
27.765398761657423
],
[
120.63240965905118,
27.765337847455555
],
[
120.63247057325282,
27.76528454752912
],
[
120.6326266658948,
27.76526551184105
],
[
120.63279417994966,
27.765250283290584
],
[
120.63299215110544,
27.765261704703335
],
[
120.6331177866465,
27.76530358321719
],
[
120.63323580791234,
27.765231247602514
],
[
120.63346423616895,
27.76521601905199
],
[
120.63360510026052,
27.76526551184105
],
[
120.63373835007678,
27.765337847455555
],
[
120.6339820068838,
27.76544064017105
],
[
120.63420282086508,
27.76537211169409
],
[
120.63424850651643,
27.76550916864801
],
[
120.63399342829655,
27.76572617549175
],
[
120.6338601784804,
27.765916532372273
],
[
120.6338182999666,
27.766045975050872
],
[
120.63371170011351,
27.766068817876658
],
[
120.63365459304941,
27.765973639436368
],
[
120.63354799319632,
27.765848003895314
],
[
120.63347946471947,
27.765733789767012
],
[
120.63335763631585,
27.765573889987365
],
[
120.63325865073796,
27.76550916864801
],
[
120.63304164389433,
27.765478711547132
],
[
120.63286651556416,
27.765482518684678
],
[
120.6326685444086,
27.765516782923214
],
[
120.63248960894089,
27.765611961363504
],
[
120.63240204477597,
27.76577566828064
],
[
120.63240204477597,
27.76590891809701
],
[
120.63236397339983,
27.766076432151692
],
[
120.63251625890427,
27.766099274977478
],
[
120.63261143734451,
27.766122117803036
],
[
120.63274468716065,
27.766125924940752
],
[
120.63280560136252,
27.766179224867187
],
[
120.63287032270193,
27.76629343899549
],
[
120.63286270842661,
27.766445724499874
],
[
120.6327827585369,
27.76661704569233
],
[
120.6327827585369,
27.76664750279315
],
[
120.63265712299562,
27.766643695655603
]
]
]
},
"properties": {
"FID": 4,
"Center_X": 120.63296550114205,
"Center_Y": 27.765971735867538,
"IDCode": 5,
"Inner_X": 120.63218075490767,
"Inner_Y": 27.765971735867538,
"UserID": 0,
"X": 120.63283550325498,
"Y": 27.76583996976262,
"poleX": 120.63373193482704,
"poleY": 27.765628563680792,
"poleDistance": 0.0002702004952306794
},
"id": 4
}
]
},
"poles": [
{
"poleX": 120.63373193482704,
"poleY": 27.765628563680792,
"poleDistance": 0.0002702004952306794
}
]
}var p = PolyVisualCenter(polygon, 1.0);const p = PolyVisualCenter(polygon, 1.0);