Repository: Toblerity/Shapely
Pull request #644 (2018-10-03 22:11:18)

Avoid floating point error for rectangular polygons in polylabel.
This PR adds a special case for rectangular polygons to the polylabel algorithm, present in the original JavaScript version. See https://github.com/mapbox/polylabel/issues/3

coveralls: 
[![Coverage Status](https://coveralls.io/builds/19336372/badge)](https://coveralls.io/builds/19336372)

Coverage increased (+0.05%) to 81.127% when pulling **277b5bc95a06bb59621a276b9fdbeda1768a2e49 on snorfalorpagus:polylabel_special_case** into **5d18af283e485a427d121e05fbf8e9968db4a569 on Toblerity:master**.

coveralls: 
[![Coverage Status](https://coveralls.io/builds/19336372/badge)](https://coveralls.io/builds/19336372)

Coverage increased (+0.05%) to 81.127% when pulling **277b5bc95a06bb59621a276b9fdbeda1768a2e49 on snorfalorpagus:polylabel_special_case** into **5d18af283e485a427d121e05fbf8e9968db4a569 on Toblerity:master**.

coveralls: 
[![Coverage Status](https://coveralls.io/builds/19336372/badge)](https://coveralls.io/builds/19336372)

Coverage increased (+0.05%) to 81.127% when pulling **277b5bc95a06bb59621a276b9fdbeda1768a2e49 on snorfalorpagus:polylabel_special_case** into **5d18af283e485a427d121e05fbf8e9968db4a569 on Toblerity:master**.


Patch:
diff --git a/shapely/algorithms/polylabel.py b/shapely/algorithms/polylabel.py
index 67182e2..08382f1 100644
--- a/shapely/algorithms/polylabel.py
+++ b/shapely/algorithms/polylabel.py
@@ -87,7 +87,9 @@ def polylabel(polygon, tolerance=1.0):
     if not polygon.is_valid:
         raise TopologicalError('Invalid polygon')
     minx, miny, maxx, maxy = polygon.bounds
-    cell_size = min(maxx - minx, maxy - miny)
+    width = maxx - minx
+    height = maxy - miny
+    cell_size = min(width, height)
     h = cell_size / 2.0
     cell_queue = []
 
@@ -96,6 +98,11 @@ def polylabel(polygon, tolerance=1.0):
     x, y = polygon.centroid.coords[0]
     best_cell = Cell(x, y, 0, polygon)
 
+    # Special case for rectangular polygons avoiding floating point error
+    bbox_cell = Cell(minx + width / 2.0, miny + height / 2, 0, polygon)
+    if bbox_cell.distance > best_cell.distance:
+        best_cell = bbox_cell
+
     # build a regular square grid covering the polygon
     x = minx
     while x < maxx:


Test patch:
diff --git a/tests/test_polylabel.py b/tests/test_polylabel.py
index c644970..84eab12 100644
--- a/tests/test_polylabel.py
+++ b/tests/test_polylabel.py
@@ -58,6 +58,18 @@ class PolylabelTestCase(unittest.TestCase):
         label = polylabel(concave_polygon)
         self.assertTrue(concave_polygon.contains(label))
 
+    def test_rectangle_special_case(self):
+        """
+        The centroid algorithm used is vulnerable to floating point errors
+        and can give unexpected results for rectangular polygons. Test
+        that this special case is handled correctly.
+        https://github.com/mapbox/polylabel/issues/3
+        """
+        polygon = Polygon([(32.71997,-117.19310), (32.71997,-117.21065),
+                           (32.72408,-117.21065), (32.72408,-117.19310)])
+        label = polylabel(polygon)
+        self.assertEqual(label.coords[:], [(32.722025, -117.201875)])
+
 
 def test_suite():
     return unittest.TestLoader().loadTestsFromTestCase(PolylabelTestCase)