Algorithm taking way too long when precision is disproportionately small
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 38/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- javascript
- Domain
- performance
Research direction
Reproduce the issue with the geojson-polygon-labels command, --precision=0.000001, and the listed OpenStreetMap examples. Start by tracing the polylabel calculation and how rectangular GeoJSON features are processed; compare runtime and memory usage at different precisions. Done means the examples complete without exhausting memory and the performance behavior is covered by an appropriate regression check.
Written by the indexing model from the issue text.
Description
The algorithm either takes way too long to calculate the label of rectangular shapes or it runs out of memory while doing so.
I am using Polylabel to calculate the POI of GeoJSON features, from Openstreetmap.
Examples of such shapes include:
https://www.openstreetmap.org/relation/2730170
https://www.openstreetmap.org/relation/153548
https://www.openstreetmap.org/relation/12863380
https://www.openstreetmap.org/relation/7491995
https://www.openstreetmap.org/relation/7585771
https://www.openstreetmap.org/relation/7717839
The precision I'm using is 0.000001, since many times the shape is minuscule which requires high precision.
I also changed the code to change the precision according to the size of the shape(parseInt(inputFeature.properties.admin_level) <= 10 ? 0.0000475 : precision), but the fact there is an OOM error indicates a memory leak, which should be fixed.
I understand it taking longer due to the high precision, but when it runs out of memory to calculate the center of a square shape then it doesn't make sense.
The command I'm using is:
geojson-polygon-labels --precision=0.000001 --label=polylabel --style=largest example.geojson > labels.geojson
- Dominant language
- JavaScript
- Stars
- 1.6k
- Forks
- 163
- PR merge metrics
- No merged PRs in 30d
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from mapbox/polylabel
-
bug
Difficulty 3/5 1-2 days Newbie friendliness 55/100
-
question
Difficulty 3/5 1-2 days Newbie friendliness 20/100
-
question
Difficulty 2/5 1-3 hours Newbie friendliness 48/100
-
enhancement question
Difficulty 3/5 1-2 days Newbie friendliness 35/100
-
MultiPolygonOpenquestion
Difficulty 5/5 Over a week Newbie friendliness 25/100
All issues in mapbox/polylabel
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
resend/resend-skills#144 ·
Maintainers usually reply within 1 day
-
[BUG] Traffic chart tests are flaky: the page's startup load overwrites the test's stubbed dataOpenbug
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
ScottKirvan/Smokey#33 ·
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 86/100
Ryan-Millard/Img2Num#681 · 2 comments ·
Maintainers usually reply within 2 days
-
Difficulty 1/5 Under an hour Newbie friendliness 75/100
bigskysoftware/htmx#4117 ·
Maintainers usually reply within 2 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Maintainers usually reply within 1 day