Algorithm generates wrong results due to limits on double type

Open
#119 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
55/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Quiet
Tech stack
javascript
Domain
computer-graphics

Research direction

Start by locating the polylabel implementation and its bounding-box calculation, then reproduce the issue with the four-point polygon in the report. Verify the coordinate normalization avoids loss of precision and that bounding boxes account for all rings, while preserving the expected returned point.

Written by the indexing model from the issue text.

Description

bug

If you try to find the polylabel for the following polygon, it fails to find a good point.

-111.1815838, 45.7768091
-111.1816944, 45.7766950
-111.1812484, 45.7764847
-111.1811378, 45.7765988

It does not matter what precision you use. It does drill down to a point, but it is not right.

This is due to limitations in the double type.

The solution is to subtract the min of the bounding box before doing the remaining calculations, and then add it back at the end. This does seem to fix the problem in my tests, and shouldn't add much in execution time.

Also, it would also be best to calculate the bounding box for all rings to better avoid this problem.

Dominant language
JavaScript
Stars
1.6k
Forks
163
No merged PRs in 30d

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from mapbox/polylabel

All issues in mapbox/polylabel

Similar issues

More JavaScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.