如何有效检查笛卡尔坐标是否构成矩形？

Question

情况是这样的：

• 有 N 个数组。
• 每个数组（从 0 到 N-1）里存储了一些 (x,y) 坐标点。
• 每个数组的长度可以不同。

我想提取出一些坐标组合，这些组合能组成一个完整的大小为 N 的矩形。换句话说，所有的坐标点都是相邻的。

举个例子：

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

会得到以下结果：

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

没有两个点可以来自同一个数组。

我最开始只是计算了所有可能的坐标组合，但这很快就变得不现实（我现在的情况是有 18 个点数组，每个数组大约包含 10 个不同的坐标）。

Answer 1

你可以用哈希来提高效率：

hash each point (keeping track of which list it is in)
for each pair of points (a,b) and (c,d):
    if (a,d) exists in another list, and (c,b) exists in yet another list:
        yield rectangle(...)

当我说exists的时候，我是指做一些类似于：

hashesToPoints = {}
for p in points:
    hashesToPoints.setdefault(hash(p),set()).add(p)
for p1 in points:
    for p2 in points:
        p3,p4 = mixCoordinates(p1,p2)
        if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}:
            if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}:
                yield Rectangle(p1,p2)

这个计算的复杂度是O(#bins^2 * items_per_bin^2)，大约是30000，这在你有18个数组和每个数组10个项目的情况下，速度非常快——比起外积的方法要好得多，外积的方法复杂度是O(items_per_bin^#bins)，大约是3万亿。=)

---

小插曲：

你可以通过多次“修剪”来减少计算中的基数和指数。例如：

remove each point that is not corectilinear with another point in the X or Y direction
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

你可以先按照X坐标排序，然后再按照Y坐标排序，这样的时间复杂度是O(P log(P))，这里的P是点的数量。你可能还可以在进行哈希的同时完成这个排序。如果有坏人故意调整你的输入，可能会让这个优化失效。不过根据你的数据分布，可能会看到明显的速度提升。

Answer 2

假设XY是你的数组集合。我们要构建两个新集合X和Y，其中X是将XY中的所有数组按x坐标排序后的结果，而Y是将XY中的所有数组按y坐标排序后的结果。

• 对于X中的每个点(x0,y0)：找到所有在其他数组中与x0相同但y坐标不同的点(x0,y1)
• 对于每一对这样的点（如果存在的话）：在Y中查找点(x1,y0)和(x1,y1)

设C是最大的数组大小。那么对所有集合进行排序的时间复杂度是O(N*C*log(C))。在第一步中，找到一个匹配的点需要O(N*log(C))的时间，因为X中的所有数组都是排序好的。找到所有这样的点的时间复杂度是O(C*N)，因为总共有最多C*N个点。第二步的时间复杂度是O(N*log(C))，因为Y是排序好的。

因此，整体的渐进运行时间是O(C * N^2 * log(C)^2)。

当C等于10，N等于18时，大约会有10,000次操作。因为我在使用大O表示法时省略了这个因子，所以你需要乘以2。

这个解决方案还有一个好处，就是实现起来非常简单。你只需要数组、排序和二分查找，而前两个功能很可能已经内置在编程语言中了，二分查找也非常简单。

另外要注意的是，这个运行时间是针对最糟糕的情况，也就是所有矩形的x坐标都相同。在平均情况下，表现可能会好得多。