Repository: Toblerity/Shapely (python)

Issue:
Polylabel bug 
## Expected behavior and actual behavior.

Holes are not correctly accounted for in shapely's implementation of the polylabel algorithm. 

## Steps to reproduce the problem.

```
from shapely.geometry import Polygon
from shapely.algorithms.polylabel import polylabel
poly1=Polygon(shell=[(0,0),(10,0),(10,10),(0,10),(0,0)][::-1], holes=[[(2,2),(6,2),(6,6),(2,6),(2,2)]])
import geopandas
gdf2 = geopandas.GeoDataFrame(geometry=[poly1])
gdf2.plot()
label_location = polylabel(poly1, tolerance=0.05) 
print(label_location.x)
print(label_location.y)
```

The output of this script is: 

```
6.25
3.75
```

But the correct position is something close to 7.65625, 7.65625. This can be verified by looking at a plot of this polygon 

![image](https://user-images.githubusercontent.com/30300995/71988175-663d4600-31fd-11ea-9bbb-6f849f9f34a6.png)

Maybe I am doing something wrong in the definition of the polygon but I have tried many different ways of instantiating this polygon and I always get the same result.

## Operating system

Linux

## Shapely version and provenance

Tested with shapely version 1.6 and 1.7a3


Pull request:
Fix polylabel for polygons with holes
The existing implementation of `polylabel` does not properly account for interior holes in the polygon, as the original algorithm does.

 Closes #817.

Patch:
diff --git a/appveyor.yml b/appveyor.yml
index dd3816d..0e457a8 100644
--- a/appveyor.yml
+++ b/appveyor.yml
@@ -41,6 +41,19 @@ environment:
       ARCH: x64
       COMPILER: msvc2017
 
+
+install:
+  # If there is a newer build queued for the same PR, cancel this one.
+  # The AppVeyor 'rollout builds' option is supposed to serve the same
+  # purpose but it is problematic because it tends to cancel builds pushed
+  # directly to master instead of just PR builds (or the converse).
+  # credits: JuliaLang developers.
+  - ps: if ($env:APPVEYOR_PULL_REQUEST_NUMBER -and $env:APPVEYOR_BUILD_NUMBER -ne ((Invoke-RestMethod `
+        https://ci.appveyor.com/api/projects/$env:APPVEYOR_ACCOUNT_NAME/$env:APPVEYOR_PROJECT_SLUG/history?recordsNumber=50).builds | `
+        Where-Object pullRequestId -eq $env:APPVEYOR_PULL_REQUEST_NUMBER)[0].buildNumber) { `
+          throw "There are newer queued builds for this pull request, failing early." }
+
+
 build_script:
   - set _INITPATH=%PATH%
 
@@ -58,13 +71,13 @@ build_script:
   - set GEOSINSTALL=C:\projects\deps\geos-%GEOSVERSION%-%COMPILER%-%ARCH%
   - set CYTHONPF=C:\\projects\\deps\\geos-%GEOSVERSION%-%COMPILER%-%ARCH%
   - ps: 'Write-Host "Checking GEOS build $env:GEOSINSTALL" -ForegroundColor Magenta'
-  - call c:\projects\shapely\ci\appveyor\build_geos.cmd
+  - call %APPVEYOR_BUILD_FOLDER%\ci\appveyor\build_geos.cmd
 
   # - ps: 'Push-AppveyorArtifact $env:GEOSINSTALL\bin\geos.dll'
   # - ps: 'Push-AppveyorArtifact $env:GEOSINSTALL\bin\geos_c.dll'
 
   - ps: 'Write-Host "Copying and checking geos_c.dll" -ForegroundColor Magenta'
-  - cd C:\projects\shapely
+  - cd %APPVEYOR_BUILD_FOLDER%
   - dir
   - if %ARCH%==x86 ( set CPDIR=DLLs_x86_VC9 )
   - if %ARCH%==x64 ( set CPDIR=DLLs_AMD64_VC9 )
diff --git a/shapely/algorithms/polylabel.py b/shapely/algorithms/polylabel.py
index 08382f1..b4e7f4b 100644
--- a/shapely/algorithms/polylabel.py
+++ b/shapely/algorithms/polylabel.py
@@ -47,7 +47,9 @@ class Cell(object):
         boundary.
         """
         inside = polygon.contains(self.centroid)
-        distance = self.centroid.distance(LineString(polygon.exterior.coords))
+        distance = self.centroid.distance(polygon.exterior)
+        for interior in polygon.interiors:
+            distance = min(distance, self.centroid.distance(interior))
         if inside:
             return distance
         return -distance
diff --git a/shapely/ops.py b/shapely/ops.py
index 56e1ffb..953fcd9 100644
--- a/shapely/ops.py
+++ b/shapely/ops.py
@@ -576,7 +576,7 @@ def orient(geom, sign=1.0):
     """A properly oriented copy of the given geometry.
 
     The signed area of the result will have the given sign. A sign of
-    1.0 means that the coordinates of the product’s exterior rings will
+    1.0 means that the coordinates of the product's exterior rings will
     be oriented counter-clockwise.
 
     Parameters


Test patch:
diff --git a/tests/test_polylabel.py b/tests/test_polylabel.py
index 84eab12..fd89f66 100644
--- a/tests/test_polylabel.py
+++ b/tests/test_polylabel.py
@@ -70,6 +70,19 @@ class PolylabelTestCase(unittest.TestCase):
         label = polylabel(polygon)
         self.assertEqual(label.coords[:], [(32.722025, -117.201875)])
 
+    def test_polygon_with_hole(self):
+        """
+        Finds pole of inaccessibility for a polygon with a hole
+        https://github.com/Toblerity/Shapely/issues/817
+        """
+        polygon = Polygon(
+            shell=[(0, 0), (10, 0), (10, 10), (0, 10), (0, 0)],
+            holes=[[(2, 2), (6, 2), (6, 6), (2, 6), (2, 2)]],
+        )
+        label = polylabel(polygon, 0.05)
+        self.assertAlmostEqual(label.x, 7.65625)
+        self.assertAlmostEqual(label.y, 7.65625)
+
 
 def test_suite():
     return unittest.TestLoader().loadTestsFromTestCase(PolylabelTestCase)