python: Aide à implémenter un algorithme pour trouver le minimum-area-rectangle pour des points donnés afin de calculer la longueur de l'axe majeur et mineur

J'ai juste mis en œuvre moi-même, alors j'ai pensé que je voudrais déposer ma version ici pour les autres à voir:

import numpy as np
from scipy.spatial import ConvexHull
def minimum_bounding_rectangle(points):
"""
Find the smallest bounding rectangle for a set of points.
Returns a set of points representing the corners of the bounding box.
:param points: an nx2 matrix of coordinates
:rval: an nx2 matrix of coordinates
"""
from scipy.ndimage.interpolation import rotate
pi2 = np.pi/2.
# get the convex hull for the points
hull_points = points[ConvexHull(points).vertices]
# calculate edge angles
edges = np.zeros((len(hull_points)-1, 2))
edges = hull_points[1:] - hull_points[:-1]
angles = np.zeros((len(edges)))
angles = np.arctan2(edges[:, 1], edges[:, 0])
angles = np.abs(np.mod(angles, pi2))
angles = np.unique(angles)
# find rotation matrices
# XXX both work
rotations = np.vstack([
np.cos(angles),
np.cos(angles-pi2),
np.cos(angles+pi2),
np.cos(angles)]).T
#     rotations = np.vstack([
#         np.cos(angles),
#         -np.sin(angles),
#         np.sin(angles),
#         np.cos(angles)]).T
rotations = rotations.reshape((-1, 2, 2))
# apply rotations to the hull
rot_points = np.dot(rotations, hull_points.T)
# find the bounding points
min_x = np.nanmin(rot_points[:, 0], axis=1)
max_x = np.nanmax(rot_points[:, 0], axis=1)
min_y = np.nanmin(rot_points[:, 1], axis=1)
max_y = np.nanmax(rot_points[:, 1], axis=1)
# find the box with the best area
areas = (max_x - min_x) * (max_y - min_y)
best_idx = np.argmin(areas)
# return the best box
x1 = max_x[best_idx]
x2 = min_x[best_idx]
y1 = max_y[best_idx]
y2 = min_y[best_idx]
r = rotations[best_idx]
rval = np.zeros((4, 2))
rval[0] = np.dot([x1, y2], r)
rval[1] = np.dot([x2, y2], r)
rval[2] = np.dot([x2, y1], r)
rval[3] = np.dot([x1, y1], r)
return rval

Voici quatre exemples dans l'action. Pour chaque exemple, j'ai généré 4 points aléatoires et trouvé la boîte englobante.

(modifier par @heltonbiker)
Un code simple pour le traçage:

import matplotlib.pyplot as plt
for n in range(10):
points = np.random.rand(4,2)
plt.scatter(points[:,0], points[:,1])
bbox = minimum_bounding_rectangle(points)
plt.fill(bbox[:,0], bbox[:,1], alpha=0.2)
plt.axis('equal')
plt.show()

(fin edit)

C'est relativement rapide, trop pour ces échantillons sur 4 points:

>>> %timeit minimum_bounding_rectangle(a)
1000 loops, best of 3: 245 µs per loop

Lien vers la même réponse sur les sig.stackexchange pour ma propre référence.

J'ai trouvé recette pour calculer convexe coques.

Si nous parlons de "solutions complètes" (une fonction pour faire tout genre de trucs), j'ai trouvé que arcpy qui fait partie de ArcGIS programme. Il fournit MinimumBoundingGeometry_management fonction qui ressemble à ce que vous recherchez. Mais il n'est pas open source. Malheureusement, il y a un manque de python bibliothèques SIG open source.