mapbox / polylabel

A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
Other
1.44k stars 151 forks source link

polylabel hanging with degenerate case #51

Closed RossRogers closed 4 months ago

RossRogers commented 5 years ago

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 commented 5 years ago

Would this work?

 var cellSize = Math.max( Math.min(width, height), precision/2);
hollasch commented 3 years ago

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 commented 3 years ago

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

TWiStErRob commented 4 months ago

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

mourner commented 4 months ago

@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!