python四点坐标找最小外接矩形

可以通过旋转卡壳算法来找到最小外接矩形，具体步骤如下：

1. 找到四个点中最左边的点，记作P0。

2. 以P0为起点，找到在其左侧的点中最远的点，记作P1。

3. 以P1为起点，找到在其左侧的点中最远的点，记作P2。

4. 以P2为起点，找到在其左侧的点中最远的点，记作P3。

5. 对于每个点Pi，计算其与P(i-1)和P(i+1)的夹角θi。

6. 对于每个点Pi，计算其到P(i-1)和P(i+1)所确定的直线的距离di。

7. 对于每个点Pi，计算其到直线P(i-1)P(i+1)的距离ei。

8. 对于每个点Pi，计算其在θi+π/2方向上的投影长度fi。

9. 对于每个点Pi，计算其到以P(i-1)P(i+1)为对角线的矩形的最小距离gi。

10. 对于每个点Pi，计算其到以P(i-1)P(i+1)为对角线的矩形的最大距离hi。

11. 对于每个点Pi，计算其到以P(i-1)P(i+1)为对角线的矩形的面积Ai。

12. 对所有点的Ai求和，得到最小外接矩形的面积。

13. 最小外接矩形的长和宽可以通过P0P2和P1P3的长度计算得到。

示例代码：

import math

def distance(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def cross(p1, p2, p3):
return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p3[0] - p1[0]) * (p2[1] - p1[1])

def rotate_calipers(points):
n = len(points)
P = [i for i in range(n)]
hull = []
hull.append(min(P, key=lambda p: points[p][0]))
i, j = hull[0], (hull[0] + 1) % n
while True:
hull.append(j)
for k in range(n):
if cross(points[i], points[j], points[k]) < 0:
j = k
if j == hull[0]:
break
i = hull[-1]
m = len(hull)
p = 0
q = 1 if m > 1 else 0
r = 1 if m > 2 else 0
min_area = float('inf')
while True:
while True:
while distance(points[hull[p]], points[hull[q]]) <= distance(points[hull[q]], points[hull[(r + 1) % m]]):
r = (r + 1) % m
if distance(points[hull[p]], points[hull[q]]) <= distance(points[hull[q]], points[hull[r]]):
break
if p == 0 and q == 1 and r == m - 1:
break
q = (q + 1) % m
d = distance(points[hull[p]], points[hull[q]])
e = distance(points[hull[q]], points[hull[r]])
f = math.sqrt(d ** 2 + e ** 2)
area = d * e
if area < min_area:
min_area = area
len1 = d
len2 = e
angle = math.atan2(points[hull[q]][1] - points[hull[p]][1], points[hull[q]][0] - points[hull[p]][0])
rect_center = ((points[hull[p]][0] + points[hull[q]][0] + points[hull[r]][0]) / 3, (points[hull[p]][1] + points[hull[q]][1] + points[hull[r]][1]) / 3)
p = (p + 1) % m
if p == q:
q = (q + 1) % m
if q == r:
r = (r + 1) % m
if p == 0:
break
return rect_center, len1, len2, angle

points = [(0, 0), (2, 0), (2, 2), (0, 2)]
rect_center, len1, len2, angle = rotate_calipers(points)
print(rect_center, len1, len2, angle)