Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

polylabel hanging with degenerate case #51

Closed
RossRogers opened this issue Feb 15, 2019 · 5 comments
Closed

polylabel hanging with degenerate case #51

RossRogers opened this issue Feb 15, 2019 · 5 comments
Labels

Comments

@RossRogers
Copy link

A user added a polygon to my system that is a degenerate case. This causes function polylabel to spin forever. The polygon has almost no height at all, causing a minuscule height on this line:

var cellSize = Math.min(width, height);

height is 4.97e-14 and width is 0.0017.

This causes the following for loop to spin for a very long time:

for (var x = minX; x < maxX; x += cellSize) {
[...]

Precision is set to 1.0. Shouldn't cellSize be bounded in minimum size by the precision somehow?

@RossRogers
Copy link
Author

Would this work?

 var cellSize = Math.max( Math.min(width, height), precision/2);

@mourner mourner added the bug label Sep 10, 2019
@hollasch
Copy link
Contributor

hollasch commented Jan 29, 2021

See #81 for a suggestion to use an initial single cell that contains the entire polygon instead of tiling by cells sized by the shortest dimension of the bounding box. That would address this specific issue, as your cellSize above would use max instead of min.

However, you also raise a good point about selecting an appropriate precision. In my implementation, I set the precision to one thousandth of the shortest side of the bounding box. And that would bring us right back around to your bug in the face of degenerate polygons. :)

For bullet-proofing your code, it seems like it would make sense to intercept polygons with sides too short to proceed. In this case, perhaps just return the bounding box center. So how short is too short? I guess that would depend on how much exponent you have (that is, whether you use float vs. double). Or, it may depend on your situation, where you know the domain of "reasonable" polygons. For example, if your inputs will always be decimal latitude/longitude, then perhaps you can intercept polygons smaller than one millimeter (9×10⁻⁹ degrees), or the size of a water molecule (2.5×10⁻¹⁵ degrees).

My code has no such safeguards, but now I'm thinking it should.

@hollasch
Copy link
Contributor

See #83 for a follow-up discussion on automatically setting precision.

@TWiStErRob
Copy link

@mourner it's scary to see no tests added for these fixes 🫣

@mourner
Copy link
Member

mourner commented Jun 26, 2024

@TWiStErRob these are pretty trivial fixes and there were no test cases provided in the issues, so I didn't want to spend too much time on them, but if you want to add some tests, PRs are always welcome!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants