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

Question

情况如下:

• 有N个数组。
• 在每个数组(0..N-1)中存储了(x,y)个元组(笛卡尔坐标)
• 每个数组的长度可以不同

我想提取构成完整坐标组合的子集 大小为 N 的 retangle。换句话说；所有笛卡尔坐标系相邻。

例子:

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

当我说存在时，我的意思是做这样的事情:

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 个 items_per_bin 的情况来说非常快——比外积方法好得多...更糟糕的是 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 坐标进行排序，在 O(P log(P)) 时间内重复 Y 坐标，以点数表示。您也可以在散列的同时执行此操作。如果一个坏人在安排你的输入，他可以让这个优化根本不起作用。但根据您的分布，您可能会看到显着的加速。