from math import atan2, cos, pi, sinclass GetMinimumAreaRectangle(object): ''' functor to find length, width, and area of the smallest rectangulararea of the given convex hull ''' def __call__(self, hull):self.hull = hullmostfar = self._mostfar # local referencen = len(hull)min_area = 10**100 # huge valueiL = iR = iP = 1 # indexes left, right, opposite#print ’ {:>2s} {:>2s} {:>2s} {:>2s} {:>9s}’.format(# ’i’, ’iL’, ’iP’, ’iR’, ’area’)for i in xrange(n-1): dx = hull[i+1][0] - hull[i][0] # distance on x axis dy = hull[i+1][1] - hull[i][1] # distance on y axis theta = pi-atan2(dy, dx) # get orientation angle of the edge s, c = sin(theta), cos(theta) yC = hull[i][0]*s + hull[i][1]*c xP, yP, iP = mostfar(iP, n, s, c, 0, 1) if i==0: iR = iP xR, yR, iR = mostfar(iR, n, s, c, 1, 0) xL, yL, iL = mostfar(iL, n, s, c, -1, 0) l, w = (yP-yC), (xR-xL) area = l*w# print ’ {:2d} {:2d} {:2d} {:2d} {:9.3f}’.format(i, iL, iP, iR, area) if area < min_area:min_area, min_length, min_width = area, l, wreturn (min_length, min_width, min_area) def _mostfar(self, j, n, s, c, mx, my):''' advance j to extreme point '''hull = self.hull # local referencexn, yn = hull[j][0], hull[j][1]rx, ry = xn*c - yn*s, xn*s + yn*cbest = mx*rx + my*rywhile True: x, y = rx, ry xn, yn = hull[(j+1)%n][0], hull[(j+1)%n][1] rx, ry = xn*c - yn*s, xn*s + yn*c if mx*rx + my*ry >= best:j = (j+1)%nbest = mx*rx + my*ry else:return (x, y, j)if __name__ == ’__main__’: hull= [(560023.44957588764, 6362057.3904932579), (560023.44957588764, 6362060.3904932579), (560024.44957588764, 6362063.3904932579), (560026.94957588764, 6362068.3904932579), (560028.44957588764, 6362069.8904932579), (560034.94957588764, 6362071.8904932579), (560036.44957588764, 6362071.8904932579), (560037.44957588764, 6362070.3904932579), (560037.44957588764, 6362064.8904932579), (560036.44957588764, 6362063.3904932579), (560034.94957588764, 6362061.3904932579), (560026.94957588764, 6362057.8904932579), (560025.44957588764, 6362057.3904932579), (560023.44957588764, 6362057.3904932579)] gmar = GetMinimumAreaRectangle() # create functor object print 'dimensions and area of smallest enclosing rectangular area:' print ' {:.3f}(L) x {:.3f}(W) = {:.3f} area'.format(*gmar(hull)) # use it@H_301_0@输出：
dimensions and area of smallest enclosing rectangular area: 10.393(L) x 18.037(W) = 187.451 area解决方法
首先，我是Python（编程领域）的新手，但我希望学习和转换jwpat7开发的函数。给定一组从凸包得到的点
hull= [(560023.44957588764,6362057.3904932579),(560023.44957588764,6362060.3904932579),(560024.44957588764,6362063.3904932579),(560026.94957588764,6362068.3904932579),(560028.44957588764,6362069.8904932579),(560034.94957588764,6362071.8904932579),(560036.44957588764,(560037.44957588764,6362070.3904932579),6362064.8904932579),6362061.3904932579),6362057.8904932579),(560025.44957588764,6362057.3904932579)]
这个脚本返回这个问题之后的所有可能区域的打印。jwpat7开发的代码是：
import mathdef mostfar(j,n,s,c,mx,my): # advance j to extreme point xn,yn = hull[j][0],hull[j][1] rx,ry = xn*c - yn*s,xn*s + yn*c best = mx*rx + my*ry while True:x,y = rx,ryxn,yn = hull[(j+1)%n][0],hull[(j+1)%n][1]rx,xn*s + yn*cif mx*rx + my*ry >= best: j = (j+1)%n best = mx*rx + my*ryelse: return (x,y,j)n = len(hull)iL = iR = iP = 1# indexes left,right,oppositepi = 4*math.atan(1)for i in range(n-1): dx = hull[i+1][0] - hull[i][0] dy = hull[i+1][1] - hull[i][1] theta = pi-math.atan2(dy,dx) s,c = math.sin(theta),math.cos(theta) yC = hull[i][0]*s + hull[i][1]*cxP,yP,iP = mostfar(iP,1) if i==0: iR = iP xR,yR,iR = mostfar(iR,1,0) xL,yL,iL = mostfar(iL,-1,0) area = (yP-yC)*(xR-xL) print ’ {:2d} {:2d} {:2d} {:2d} {:9.3f}’.format(i,iL,iP,iR,area)
结果是：
i iL iP iR Area 0 6 8 0 203.000 1 6 8 0 211.875 2 6 8 0 205.800 3 6 10 0 206.250 4 7 12 0 190.362 5 8 0 1 203.000 6 10 0 4 201.385 7 0 1 6 203.000 8 0 3 6 205.827 9 0 3 6 205.64010 0 4 7 187.45111 0 4 7 189.75012 1 6 8 203.000
我希望创建一个单一函数，并返回最小矩形的长度，宽度和面积。例如：
Length,Width,Area = get_minimum_area_rectangle(hull)print Length,Area18.036,10.392,187.451
我的问题是：
我需要创建一个功能还是两个功能。例如：def最远和get_minimum_area_rectangle船体是值的列表。是最好的格式吗？ followingint一种功能的方法，我有一个问题，要整合到大多数提前致谢
1）解决方案：ScottHunter建议的第一个解决方案之后的一个函数，我在将mostfar（）集成到get_minimum_area_rectangle（）时遇到问题。任何建议或帮助都非常感谢，因为我可以学习。
#!/usr/bin/pythonimport mathdef get_minimum_area_rectangle(hull): # get pi greek pi = 4*math.atan(1) # number of points n = len(hull) # indexes left,opposite iL = iR = iP = 1 # work clockwise direction for i in range(n-1):# distance on x axisdx = hull[i+1][0] - hull[i][0]# distance on y axisdy = hull[i+1][1] - hull[i][1]# get orientation angle of the edgetheta = pi-math.atan2(dy,dx)s,math.cos(theta)yC = hull[i][0]*s + hull[i][1]*c
从上面的jwpat7示例开始，我需要使用mostfar（）。我有一个问题要了解在这一点上大多数情况下如何整合（抱歉，术语不正确）
