计算旋转矩形相交面积

2018-09-11

问题

对于两个旋转的矩形求相交的面积

输入: 矩形1的4个点 [(ax1, ay1), (ax2, ay2), (ax3, ay3), (ax4, ay4)]

矩形2的4个点 [(bx1, by1), (bx2, by2), (bx3, by3), (bx4, by4)]

输出: 矩形1和矩形2相交的面积

求解流程

将4个点按照时钟序排列(我实现的是逆时针)
(PS:这一步不重要，我只是为了利用python里给定的函数求交点必须要转成这个数据结构)得到矩形的数据结构表示 ((x,y), (w,h), angle) #(x,y)表示矩形的中心点, (w,h)表示边长，w不一定大于h，而是w表示y值最小的点(如果相等就x最小)右侧的边长，同理h表示左侧的边长。angle表示为度数(360度一圈)，是w对应的边长和x轴正方向的夹角。
求解出两个矩形相交的点以及某个矩形的顶点落在另一个矩形内的点集合S
对S求个凸包 hull
hull是个凸多边形，根据向量的叉积求解面积即可(如找到一个点p，将每一条边都和这个点相连的三角形通过叉积求面积进行加和)

利用的函数

scipy.spatial.ConvexHull 求凸包
cv2.rotatedRectangleIntersection(rect1, rect2) 求两个矩形的交点(就是我第三步所说)
cv2.contourArea 求多边形的面积

python代码实现

import cv2
import math
import numpy as np
from scipy.spatial import ConvexHull
class RotatedRect:
    def __init__(self, points):
        self.points = sort_rotatedrect_points(points)
        self.rect = rotate_rect(points)  # ((centerX, centerY), (width,height), angle)
    def intersection_area(self, rotated_rect):
        return intersect_area(self.rect, rotated_rect.rect)
    def union_area(self, rotated_rect):
        return self.rect[1][0]*self.rect[1][1] + \
               rotated_rect.rect[1][0]*rotated_rect.rect[1][1] - \
               self.intersection_area(rotated_rect)
    def iou(self, rotated_rect):
        return self.intersection_area(rotated_rect) / self.union_area(rotated_rect)
    pass
def distance(a, b): # 计算点对之间的距离
    return math.sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]))
def sort_rotatedrect_points(points):  # 将旋转矩形的四个点按照逆时针输出，且保证起始位置是y值最小的点
    print('before sort: ', points)
    points = sorted(points, key=lambda a: (a[1], a[0]))
    print('after sort: ', points)
    tmp1 = points[1].copy()
    tmp2 = points[2].copy()
    tmp3 = points[3].copy()
    if points[1][0] < points[0][0]:
        points[1] = tmp2
        points[2] = tmp3
        points[3] = tmp1
    else:
        points[2] = tmp3
        points[3] = tmp2
    print('after update sort: ', points)
    return points
def rotate_rect(points):
    '''
    :param points: points 表示旋转矩形的4个点  [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
    :return: (centerx,centery), (width,height), angle
    '''
    assert len(points) == 4, 'The points nums != 4'
    points = sort_rotatedrect_points(points)
    assert abs(points[0][0] + points[2][0] - points[1][0] - points[3][0]) < 1e-6, 'These points can\'t form a rectangle'
    assert ( abs(points[0][1] + points[2][1] - points[1][1] - points[3][1]) < 1e-6 ), 'These points can\'t form a rectangle'
    centerx = (points[0][0] + points[2][0]) / 2
    centery = (points[0][1] + points[2][1]) / 2
    center = (centerx, centery)
    width = distance(points[0], points[1])
    height = distance(points[0], points[3])
    angle = math.atan2(points[1][1]-points[0][1], points[1][0]-points[0][0])
    PI = math.acos(-1.0)
    return center, (width, height), angle/PI*180
def convexhull(points):
    '''
    :param unordered points: np.array([(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)])
    :return: ordered points of convex
    '''
    hull = ConvexHull(points)
    arg_index = hull.vertices  # 返回的是重新排序后的点坐标
    hull = points[arg_index]  # 重排后凸包后的顺序点
    return hull
def intersect_area(rect1, rect2):  # rect的数据格式要求((centerx,centery), (width,height), angle)(角度，以360作为一圈)
    r1 = cv2.rotatedRectangleIntersection(rect1, rect2)
    p = []
    len_p = r1[1].shape[0]
    for i in range(len_p):
        p.append((r1[1][i][0][0], r1[1][i][0][1]))
    p = np.array(p)
    hull = convexhull(p)
    r2 = cv2.contourArea(hull)     # 根据凸包顺序点求面积
    return r2
# 中心点 矩形的w h, 逆时针旋转的theta（角度，不是弧度）
rect1 = ((0,0),(1,1),30)
rect2 = ((1.5,0),(4,3),0)
r1 = cv2.rotatedRectangleIntersection(rect1, rect2)
print (r1)
points1 = [[1., 0], [-1., 0], [0, -1.], [0, 1.]]
rect1 = rotate_rect(points1)
points2 = [[-0.5, -0.5], [-0.5, 1.5], [1.5, -0.5], [1.5, 1.5]]
rect2 = rotate_rect(points2)
print(rect1)
print(rect2)
print(intersect_area(rect1, rect2))