Repository: Toblerity/Shapely
Pull request #361 (2016-02-12 18:20:03)

Add minimum_rotated_rectangle function.
I tried adding the functionality requested in #354  to enhance the base geometry object. 
This function enables the computation of a minimum bounding rectangle that is not constrained to be parallel to the axes but can be rotated.
The solution is based on the algorithm proposed in this [link](http://gis.stackexchange.com/questions/22895/how-to-find-the-minimum-area-rectangle-for-given-points/22934#22934) that was provided by @snorfalorpagus


Patch:
diff --git a/shapely/geometry/base.py b/shapely/geometry/base.py
index 42d821f..4d4e922 100644
--- a/shapely/geometry/base.py
+++ b/shapely/geometry/base.py
@@ -2,15 +2,18 @@
 """
 
 import sys
+import math
 from warnings import warn
 from binascii import a2b_hex
 from ctypes import pointer, c_size_t, c_char_p, c_void_p
+from itertools import islice
 
 from shapely.coords import CoordinateSequence
 from shapely.ftools import wraps
 from shapely.geos import lgeos, ReadingError
 from shapely.geos import WKBWriter, WKTWriter
 from shapely.impl import DefaultImplementation, delegated
+from shapely.affinity import affine_transform
 
 if sys.version_info[0] < 3:
     range = xrange
@@ -472,6 +475,41 @@ class BaseGeometry(object):
         """A figure that envelopes the geometry"""
         return geom_factory(self.impl['envelope'](self))
 
+    @property
+    def minimum_rotated_rectangle(self):
+        """Returns the general minimum bounding rectangle of 
+        the geometry. Can possibly be rotated. If the convex hull
+        of the object is a degenerate (line or point) this same degenerate 
+        is returned.
+        """
+        # first compute the convex hull
+        hull = self.convex_hull
+        try:
+            coords = hull.exterior.coords
+        except AttributeError: # may be a Point or a LineString
+            return hull
+        # generate the edge vectors between the convex hull's coords
+        edges = ((pt2[0]-pt1[0], pt2[1]-pt1[1]) for pt1, pt2 in zip(coords, islice(coords, 1, None)))
+
+        def _transformed_rects():
+            for dx, dy in edges:
+                # compute the normalized direction vector of the edge vector
+                length = math.sqrt(dx**2 + dy**2)
+                ux, uy = dx/length, dy/length
+                # compute the normalized perpendicular vector
+                vx, vy = -uy, ux
+                # transform hull from the original coordinate system to the coordinate system 
+                # defined by the edge and compute the axes-parallel bounding rectangle
+                transf_rect = affine_transform(hull, (ux,uy,vx,vy,0,0)).envelope
+                # yield the transformed rectangle and a matrix to transform it back
+                # to the original coordinate system
+                yield (transf_rect, (ux,vx,uy,vy,0,0))
+
+        # check for the minimum area rectangle and return it
+        transf_rect, inv_matrix = min(_transformed_rects(), key=lambda r : r[0].area)
+        return affine_transform(transf_rect, inv_matrix)
+
+
     def buffer(self, distance, resolution=16, quadsegs=None,
                cap_style=CAP_STYLE.round, join_style=JOIN_STYLE.round,
                mitre_limit=5.0):


Test patch:
diff --git a/tests/test_minimum_rotated_rectangle.py b/tests/test_minimum_rotated_rectangle.py
new file mode 100644
index 0000000..137effe
--- /dev/null
+++ b/tests/test_minimum_rotated_rectangle.py
@@ -0,0 +1,33 @@
+from . import unittest
+from shapely import geometry
+
+class MinimumRotatedRectangleTestCase(unittest.TestCase):
+    
+    def test_minimum_rectangle(self):
+        poly = geometry.Polygon([(0,1), (1, 2), (2, 1), (1, 0), (0, 1)])
+        rect = poly.minimum_rotated_rectangle
+        self.assertIsInstance(rect, geometry.Polygon)
+        self.assertEqual(rect.area - poly.area < 0.1, True)
+        self.assertEqual(len(rect.exterior.coords), 5)
+        
+        ls = geometry.LineString([(0,1), (1, 2), (2, 1), (1, 0)])
+        rect = ls.minimum_rotated_rectangle
+        self.assertIsInstance(rect, geometry.Polygon)
+        self.assertIsInstance(rect, geometry.Polygon)
+        self.assertEqual(rect.area - ls.convex_hull.area < 0.1, True)
+        self.assertEqual(len(rect.exterior.coords), 5)
+
+    def test_digenerate(self):
+        rect = geometry.Point((0,1)).minimum_rotated_rectangle
+        self.assertIsInstance(rect, geometry.Point)
+        self.assertEqual(len(rect.coords), 1)
+        self.assertEqual(rect.coords[0], (0,1))
+
+        rect = geometry.LineString([(0,0),(2,2)]).minimum_rotated_rectangle
+        self.assertIsInstance(rect, geometry.LineString)
+        self.assertEqual(len(rect.coords), 2)
+        self.assertEqual(rect.coords[0], (0,0))
+        self.assertEqual(rect.coords[1], (2,2))
+
+def test_suite():
+    return unittest.TestLoader().loadTestsFromTestCase(MinimumRotatedRectangleTestCase)
\ No newline at end of file