回答问题

我有一组点(地理坐标值中的黑点)来自多边形(红色)的凸包(蓝色)。见图:

[(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)]

我需要按照这些步骤计算长轴和短轴长度(形成这个后写在 R-project 和Java)或按照这个示例程序

1. 计算云的凸包。

2.对于凸包的每个边缘:2a。计算边缘方向,2b。使用此方向旋转凸包,以便轻松计算具有旋转凸包的 x/y 的 min/max 的边界矩形区域,2c。存储与找到的最小区域相对应的方向,

3. 返回找到的最小面积对应的矩形。

之后,我们知道了 角度 Theta(表示边界矩形相对于图像 y 轴的方向)。找到所有边界点上 a 和 b 的最小值和最大值:

赵文卓100007 啊(喜,一) u003d 喜*cost和他 + 意思呢θ

赵文卓100008 不(喜,一) u003d 喜*四年θ + 以cost和他

值 (a_max - a_min) 和 (b_max - b_min) 分别定义了方向 Theta 的边界矩形的长度和宽度。

Answers

给定一组点的凸包中的 n 个点的顺时针排序列表,找到最小面积的封闭矩形是一个 O(n) 操作。 (对于凸包查找,在 O(n log n) 时间内,请参阅activestate.com recipe 66527或在 tixxit.net](http://tixxit.net/2010/03/graham-scan/)上查看非常紧凑的[Graham 扫描代码。)

下面的 python 程序使用类似于通常 O(n) 算法的技术来计算凸多边形的最大直径。也就是说,它维护三个索引(iL、iP、iR)到相对于给定基线的最左边、对面和最右边的点。每个索引最多前进 n 个点。接下来显示程序的示例输出(带有添加的标题):

 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.640
10  0  4  7   187.451
11  0  4  7   189.750
12  1  6  8   203.000

例如,iu003d10 条目表示相对于从点 10 到 11 的基线,点 0 在最左边,点 4 相对,点 7 在最右边,产生的面积为 187.451 个单位。

请注意,代码使用mostfar()来推进每个索引。mostfar()的mx, my参数告诉它要测试什么极端;例如,对于mx,my = -1,0,mostfar()将尝试最大化 -rx(其中 rx 是一个点的旋转 x),从而找到最左边的点。请注意,当if mx*rx + my*ry >= best以不精确的算术完成时,可能应该使用 epsilon 余量:当外壳有许多点时,舍入误差可能是一个问题,并导致该方法错误地不推进索引。

代码如下所示。船体数据取自上述问题,忽略了不相关的大偏移量和相同的小数位。

#!/usr/bin/python
import math

hull = [(23.45, 57.39), (23.45, 60.39), (24.45, 63.39),
        (26.95, 68.39), (28.45, 69.89), (34.95, 71.89),
        (36.45, 71.89), (37.45, 70.39), (37.45, 64.89),
        (36.45, 63.39), (34.95, 61.39), (26.95, 57.89),
        (25.45, 57.39), (23.45, 57.39)]

def 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, 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)%n
            best = mx*rx + my*ry
        else:
            return (x, y, j)

n = len(hull)
iL = iR = iP = 1                # indexes left, right, opposite
pi = 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]*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)
    area = (yP-yC)*(xR-xL)

    print '    {:2d} {:2d} {:2d} {:2d} {:9.3f}'.format(i, iL, iP, iR, area)

_注意:_要得到最小面积包围矩形的长度和宽度,修改上面的代码如下所示。这将产生一个输出线,如

Min rectangle:  187.451   18.037   10.393   10    0    4    7

其中第二个和第三个数字表示矩形的长度和宽度,四个整数给出位于矩形边上的点的索引号。

# add after pi = ... line:
minRect = (1e33, 0, 0, 0, 0, 0, 0) # area, dx, dy, i, iL, iP, iR

# add after area = ... line:
    if area < minRect[0]:
        minRect = (area, xR-xL, yP-yC, i, iL, iP, iR)

# add after print ... line:
print 'Min rectangle:', minRect
# or instead of that print, add:
print 'Min rectangle: ',
for x in ['{:3d} '.format(x) if isinstance(x, int) else '{:7.3f} '.format(x) for x in minRect]:
    print x,
print