求给定点最小面积矩形以计算长轴和短轴长度的算法

2024-05-15 03:33:22 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一组点(地理坐标值中的黑点)从多边形(红色)的凸面外壳(蓝色)中导出。见图:enter image description here

[(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中填写此post)或在this example procedure之后计算长轴和短轴长度

enter image description here

  1. 计算云的凸包。
  2. 对于凸面外壳的每个边缘: 2a.计算边缘方向, 2b.使用此方向旋转凸面外壳,以便于计算旋转凸面外壳的最小/最大x/y的边界矩形区域, 2c.存储与找到的最小区域相对应的方向
  3. 返回与找到的最小区域相对应的矩形。

然后我们知道角度θ(表示边框相对于图像y轴的方向)。所有边界点上ab的最小值和最大值为 找到:

  • a(xi,yi)=xi*cosθ+yi sinθ
  • b(xi,yi)=xi*sinθ+yi cosθ

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

enter image description here


Tags: 区域sincosmin方向外壳地理max
3条回答

我自己刚刚实现了这个,所以我想把我的版本放在这里让其他人看:

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

下面是四个不同的例子。对于每个示例,我生成4个随机点并找到边界框。

examples

(由@heltonbiker编辑) 绘图的简单代码:

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

(结束编辑)

对于4个点上的这些样本来说,速度也相对较快:

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

Link to the same answer over on gis.stackexchange供我参考。

github上已经有一个这样做的模块。 https://github.com/BebeSparkelSparkel/MinimumBoundingBox

你只需要把你的点云插入其中。

from MinimumBoundingBox import minimum_bounding_box
points = ( (1,2), (5,4), (-1,-3) )
bounding_box = minimum_bounding_box(points)  # returns namedtuple

您可以通过以下方法获得长轴和短轴长度:

minor = min(bounding_box.length_parallel, bounding_box.length_orthogonal)
major = max(bounding_box.length_parallel, bounding_box.length_orthogonal)

它还返回面积、矩形中心、矩形角度和角点。

给定一组点的凸包中n个点的顺时针顺序列表,找到包围矩形的最小面积是一个O(n)运算。(对于凸包查找,在O(n logn)时间内,请参见activestate.com recipe 66527或非常紧凑的Graham scan code at tixxit.net。)

下面的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

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

注意,代码使用mostfar()来推进每个索引。mx, my参数告诉它要测试什么极端;例如,使用mx,my = -1,0mostfar()将尝试最大化-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

相关问题 更多 >

    热门问题