有没有什么快速的公式可以求出N个点给出的一般四边形（六面体）的最大面积？

Question

我正在使用 pythom 3.6，我遇到了一个问题。给定了n个点的x和y坐标(n是从4到200)，我需要从这n个点中找出4个点组成最大的一般四边形(由4个点组成的任何凸形)。

我可以想到一个解决方案，包括4个循环，计算循环中的点给出的四边形的面积，但它是极端缓慢的。你知道有什么更快的方法吗？

点是这样给的。

B = np.array([[ 1., 2.], [ 0., 0.], [ 1., 3.], [ -5., 6.], [ -6., 3.], [ 1., 5.], [ -1., 2.], [ 1., -3.], [ 4., 2.]])

下一个层次是当我得到N个由x、y和z坐标给出的点（N在8到500之间），我应该找到最大的（体积）六面体（由8个点定义的形状）--我不知道如何解决。

不需要直角，只需要由4（8）个点定义的形状。有什么建议吗？

---

背景:我有相当复杂的建筑3D模型，我需要将其简化到一个特定的程序中进行计算。建筑物的细节是不需要的。建筑物的所有信息都在从Blender导出的file.obj中。

Answer 1

构建 凸壳 的所有点。

然后找出面积最大的四边形，其顶点属于ull.如果ull数N小，可以直接检查所有对角线。

否则可以考虑使用更高级的算法，比如这样。"凸多边形中的最大面积四边形，重温

Answer 2

所以，2D和3D问题的答案是相似的。因为是建筑物，所以我们可以把三维模型分割成两个二维模型，分别是建筑物的底座和屋顶（中间的东西也算屋顶）。

然后我们要寻找四边形来近似于（近似）平面上的点。我们需要找到中心（不是从所有点的平均值，而是在两个直角上的(max+min)2）。我们通过计算点-中心，将原点移到中心。然后，这些点应该被象限划分（x>0 &y>0，x<0，&y>0，x<0，&y<0，x>0，&y<0），对于每个象限，我们计算出最远的点（如果有nan，我们取原点[0,0]）。

使用Shoelace公式，我们计算出这4个点从每个象限所占的面积，并保持该值，然后我们围绕原点旋转1度，直至90度。每次计算面积，我们都在寻找最大的面积。铲除最大面积的点就是所需的点.代码(我知道这不是流畅的代码,可以优化.但它工作!!):

def getCorners(points):
    maxPoint = np.max(points[:,0])
    mayPoint = np.max(points[:,1])
    minPoint = np.min(points[:,0])
    miyPoint = np.min(points[:,1])
    meanPoint = np.array([(maxPoint + minPoint)/2, (mayPoint + miyPoint)/2])
    normPoints = points[:,0:2] - meanPoint[0:2]
    areaMaximum = -1
    finID1 = 0
    finID2 = 1
    finID3 = 2
    finID4 = 3
    numrot = 360

    for alpha in range(0,numrot):
        topright = np.where((normPoints[:,0] > 0) & (normPoints[:,1] > 0))
        topleft = np.where((normPoints[:,0] < 0) & (normPoints[:,1] > 0))
        bottomleft = np.where((normPoints[:,0] < 0) & (normPoints[:,1] < 0))
        bottomright = np.where((normPoints[:,0] > 0) & (normPoints[:,1] < 0))

        q1 = normPoints[topright]
        q2 = normPoints[topleft]
        q3 = normPoints[bottomleft]
        q4 = normPoints[bottomright]

        if len(q1) == 0:
            q1 = np.array([[0,0],[0,0]])
        if len(q2) == 0:
            q2 = np.array([[0,0],[0,0]])
        if len(q3) == 0:
            q3 = np.array([[0,0],[0,0]])
        if len(q4) == 0:
            q4 = np.array([[0,0],[0,0]])

        D1 = q1[:,0]*q1[:,0] + q1[:,1]*q1[:,1]
        D2 = q2[:,0]*q2[:,0] + q2[:,1]*q2[:,1]
        D3 = q3[:,0]*q3[:,0] + q3[:,1]*q3[:,1]
        D4 = q4[:,0]*q4[:,0] + q4[:,1]*q4[:,1]

        ID1 = np.argmax(D1)
        ID2 = np.argmax(D2)
        ID3 = np.argmax(D3)
        ID4 = np.argmax(D4)
        vertices = [[q1[ID1,0],q1[ID1,1]],[q2[ID2,0],q2[ID2,1]],[q3[ID3,0],q3[ID3,1]],[q4[ID4,0],q4[ID4,1]]]
        area = polygonArea(vertices)

        if area > areaMaximum:
            areaMaximum = area
            if len(topright[0]) == 0:
                finID1 = 0
            else:
                finID1 = topright[0][ID1]
            if len(topleft[0]) == 0:
                finID2 = 0
            else:
                finID2 = topleft[0][ID2]
            if len(bottomleft[0]) == 0:
                finID3 = 0
            else:
                finID3 = bottomleft[0][ID3]
            if len(bottomright[0]) == 0:
                finID4 = 0
            else:
                finID4 = bottomright[0][ID4]

        # rotate
        for opi in range(0,len(normPoints)):
            normPoints[opi] = rotate_origin_only(normPoints[opi], 90/numrot/180*np.pi)

    return [finID1,finID2,finID3,finID4]

def rotate_origin_only(xy, radians):
    """Only rotate a point around the origin (0, 0)."""
    x, y = xy
    xx = x * math.cos(radians) + y * math.sin(radians)
    yy = -x * math.sin(radians) + y * math.cos(radians)

    return xx, yy

def polygonArea(vertices):
    #A function to apply the Shoelace algorithm
    numberOfVertices = len(vertices)
    sum1 = 0
    sum2 = 0

    for i in range(0,numberOfVertices-1):
        sum1 = sum1 + vertices[i][0] *  vertices[i+1][1]
        sum2 = sum2 + vertices[i][1] *  vertices[i+1][0]

    #Add xn.y1
    sum1 = sum1 + vertices[numberOfVertices-1][0]*vertices[0][1]   
    #Add x1.yn
    sum2 = sum2 + vertices[0][0]*vertices[numberOfVertices-1][1]   

    area = abs(sum1 - sum2) / 2
    return area