从点列表中查找可能的矩形最大面积（不一定平行）的函数

Question

输入：二维点数组 ((x, y), (x2, y2), ...) 输出：最大可能矩形的面积，其 4 个角作为给定点中的 4 个点。

注意：矩形不必平行于任何轴，至少可以用一组点制作一个矩形

---

示例1： 输入：[[1,2],[2,1],[1,0],[0,1]] 输出：2

说明： 矩形在二维平面上看起来像这样：

每条边长均为 sqrt(2)，因此面积为 2

示例2： 输入：[[0,1],[2,1],[1,1],[1,0],[2,0]] 输出：1

说明： 飞机：

唯一可能的矩形是边长为 1 的正方形，因此面积为 1

---

我将不胜感激解决这个问题的任何帮助，老实说，我不知道如何提高效率。还可能吗？

我尝试了暴力破解，即检查 4 个点的所有可能组合，看看它们是否构成一个矩形，然后比较它们的面积，但对于大输入来说太慢了......

Answer 1

O(n^2) 算法：

1. 生成所有点对

   (p1,p2)

   ，其中

   p1.x < p2.x

   且角度为 <= 45 degrees and > -45 度。每个矩形在此列表中都有一个“顶”和“底”边。
2. 按角度和距离将各对分开。每个矩形的顶部和底部都位于同一分区中。
3. 对于每个（角度、距离），用

   p1.x*(p2.x-p1.x) + p1.y*(p2.y-p1.y)

   划分对。每个矩形的顶边和底边都在同一个分区中，每个分区中的每一对都会形成一个矩形。
4. 对于每个结果分区，找到具有最小值和最大值

   p1.y

   的点。这些构成了分区中最大的矩形。

Answer 2

一些用伪 python 编写的按天真降序排列的算法。

我没有使用任何花哨的 python 概念，所以这应该读起来像伪代码。虽然我用过

for a,b,c,d in combinations(seq, 4):
    ...

而不是等效的嵌套循环

for a in seq:
    for b in seq after a:
        for c in seq after b:
            for d in seq after c:
                ...

我还假设点可以很容易地减去向量，即我写了

b - a

而不是

(bx - ax, by - ay)

；我还假设向量可以添加到点，即如果 a、b、d、c 是平行四边形，则

d == b + (c - a)

。

最后我假设你有一个

dotproduct

函数，因此

dotproduct(b - a, d - c) == 0

相当于“向量 ab 和 cd 是正交的”。

我很可能低估了不懂Python的人理解这些伪Python代码片段的难度，所以请毫不犹豫地在评论中要求澄清，我可以尝试重写算法更明确或添加更好的描述。

最简单的暴力破解：迭代四元组点，n^4

from itertools import combinations

examples = [
    [[1,2],[2,1],[1,0],[0,1]],
    [[0,1],[2,1],[1,1],[1,0],[2,0]]
]

def naive_quadruplets_n4(points):
    best_rectangle = None
    best_area = 0
    for a, b, c, d in combinations(points, 4):
        if is_rectangle(a, b, c, d):  # function is_rectangle should find how to correctly order the four points, maybe the rectangle is abdc or acbd or acdb or adbc or adcb
            abcd_area = area(a, b, c, d)
            if abcd_area > best_area:
                best_rectangle = (a, b, c, d)
                best_area = abcd_area
    return best_area, best_rectangle

稍微不那么幼稚的暴力破解：迭代三元组点，n^3

因为您的点都有整数坐标，所以计算是准确的。给定三个点a，b，c，您可以直接计算唯一点d的坐标，使得a，b，c，d是一个矩形，并检查d是否是输入点列表中的点之一。

为了有效地检查一个点是否在列表中，您应该首先从列表中构建一个哈希表，以便此成员资格检查的时间复杂度为 O(1)。在 python 中，这是使用

set()

完成的。

from itertools import combinations

def naive_triplets(points):
    points = set(points)
    best_rectangle = None
    best_area = 0
    for a, b, c in combinations(points, 3):
        if dotproduct((b - a), (c - a)) == 0:
            d = b + (c - a)
            if d in points:
                if best_area < area(a, b, c, d):
                    ...
        elif dotproduct((a - b), (c - b)) == 0:
            d = a + (c - b)
            ...
        elif dotproduct((a - c), (b - c)) == 0:
            d = a + (b - c)
            ...
    return best_area, best_rectangle

n^2 解决方案：通过构建向量表来搜索平行四边形

四边形 a,b,c,d 当且仅当两个向量 b-a 和 d-c 相等时才是平行四边形。

四边形 a,b,c,d 是菱形当且仅当两个向量 c-a 和 d-b 正交。

四边形是矩形当且仅当它既是平行四边形又是菱形。

这提出了一种伪 n^2 算法：构建一个哈希表，将向量映射到构成该向量的点对列表。然后迭代对应于至少两个不同点对的每个向量，并检查相应的平行四边形是否是菱形。

from itertools import combinations

def build_vector_table(points):
    table = {}
    for a, b in combinations(points, 2):
        if (b - a).x < 0 or (b - a).x <= 0 and (b - a).y <= 0:
            (a, b) = (b, a)  # Consider only vector ab or ba so that the vector is facing rightwards
        table[b - a].setdefault([]).append((a, b))
    return table

def parallelograms_rhombus_n2(points):
    table = build_vector_table(points)
    best_area = 0
    best_rectangle = None
    for v, l in table:
        if len(l) >= 2:
            for (a, b), (c, d) in combinations(l, 2)::
                if dotproduct(d - a, c - b) == 0:
                    if area(a, b, d, c) > best_area:
                        best_area = area(a, b, d, c)
                        best_rectangle = (a, b, d, c)
    return best_area, best_rectangle