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

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个不同的坐标）。

- bojangles

---

你的示例中可能有错别字：“(2,1)”在哪里？你可以从任何数组中选择任何点吗？你不能从同一个数组中选择两个点？ - ninjagecko

修正了拼写错误；不，你不能从同一个数组中选择两个点。 - bojangles

只考虑与坐标轴对齐的矩形，还是任何矩形都可以？ - Ignacio Vazquez-Abrams

仅限于与坐标轴对齐的矩形。 - bojangles

你的编辑并不完全正确，在你给出的例子中，由于第三个映射只包含(5,1)，它与4个星号结果不匹配，因此不会产生任何结果。 - bojangles

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)，在你的情况下，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))的时间完成。您可能也可以在哈希的同时进行此操作。如果一个坏人正在安排您的输入，则他可能会使此优化完全无效。但根据您的分布情况，您可能会看到显著的加速。

- ninjagecko

Answer 2

假设XY是您的数组集。构建两个新集合X和Y，其中X等于将所有数组按x坐标排序的XY，而Y等于将所有数组按y坐标排序的XY。

• 对于X中任何一个数组中的点（x0，y0）：在剩余的X数组中查找具有相同x坐标但不同y坐标的每个点（x0，y1）
• 对于每一对这样的点（如果存在）：在Y中搜索点（x1，y0）和（x1，y1）

令C为最大数组的大小。因此，对所有集合进行排序需要O（N * C * log（C））的时间。在步骤1中，找到单个匹配点需要O（N * log（C））的时间，因为X中的所有数组都已排序。由于总共最多有C * N个点，因此找到所有这样的点需要O（C * N）的时间。步骤2需要O（N * log（C））的时间，因为Y已排序。

因此，总体渐近运行时间为O（C * N ^ 2 * log（C）^ 2）。

对于C == 10和N == 18，您将获得大约10,000次操作。乘以2，因为我由于大O符号而删除了该因子。

这个解决方案的另一个好处是非常简单易行。你只需要使用数组、排序和二分查找，其中前两者很可能已经内置于语言中，而二分查找也非常简单。

还要注意，这是在所有矩形都从相同的x坐标开始的最坏情况下的运行时间。在平均情况下，你的表现可能会比这好得多。

- Philip

---

找到所有这样的点的时间复杂度为O(CN)，因为总共最多有CN个点。但是，如果按照二分查找的方式执行算法，则情况并非如此（通常仅因为某些事情是可能的，并不意味着特定的算法将实现它）。它是O(CN * NlogC)=O(N^2 ClogC)，因此步骤2需要花费O(N^3 C(logC)^2)的时间。为了实现您所说的内容，必须使用哈希。请参见下面的答案。尽管如此，这是一个有趣的想法。 - ninjagecko