在给定 n 个点的平面上求正方形

Question

给定平面上的 n 个点，可以形成多少个正方形......？

我尝试通过计算每 2 个点之间的距离，然后对它们进行排序，并在验证点和斜率后查找具有四个或更多相等距离的点中的正方形。

但这看起来是一种非常复杂的方法。任何其他想法......？

我认为用于检查相等距离的线段的动态编程可能会起作用......但无法完全正确地得到这个想法......

有什么更好的主意吗？？？

PS：正方形可以是任何形式。它们可以重叠，有一个共同的一面，一个正方形在另一个正方形内......

如果可能，请提供示例代码来执行上述...

Answer 1

O(n^1.5)这个问题可以用时间和空间来解决O(n)。

基本思想是通过 X 或 Y 坐标对点进行分组，小心避免分组太大。详细信息请参见《Finding squares and quartegins in groups ofpoints》一文。该论文还涵盖了许多其他情况（允许旋转正方形、允许矩形以及在更高维度上工作）。

我在下面解释了他们的二维轴对齐平方查找算法。请注意，我将它们的树集更改为哈希集，这就是为什么我给出的时间限制不是O(n^1.5 log(n))：

1. 制作所有点的哈希集。您可以使用它来快速检查某个点是否存在。

2. 按 X 坐标对点进行分组。将任何超过多个sqrt(n)点的组分开，并按 Y 坐标将这些现在空闲的点重新分组。这保证了组最多sqrt(n)有点，并保证对于每个正方形都有一个组拥有两个正方形的角点。

3. 对于每个组，对于中的g每对点，检查包含和的两个可能的方格中的其他两个点是否存在。记录下您找到了多少个。注意重复项（两个相反的点也在一组中吗？）。p,qgpq

为什么它有效？好吧，唯一棘手的是重组。如果正方形的左列或右列位于不太大的组中，则当迭代该列组时将找到该正方形。否则，它的左上角和右上角都会被重新分组，放入同一行组中，并且当迭代该行组时将找到该正方形。

Answer 2

让d[i][j] = distances between points i and j. 我们对一个函数感兴趣，该函数count(i, j)尽可能快地返回我们可以使用点i和绘制的正方形数量j。

基本上，count(i, j)必须找到两个点x，并y使得d[i][j] = d[x][y]和检查，如果这4个点真正定义一个正方形。

您可以使用哈希表来解决O(n^2)平均问题。让H[x] = list of all points (p, q) that have d[p][q] = x.

现在，对于每对点(i, j)，count(i, j)必须迭代H[ d[i][j] ]并计算该列表中与点i和形成正方形的点j。

这在实践中应该运行得非常快，而且我认为它不会比O(n^3)（我什至不确定它会变得那么糟糕）变得更糟。

Answer 3

我有一个 O(N^2) 时间，O(N) 空间解决方案：

假设给定的点是一个对象点数组，每个点都有 x,y。

1. 首先遍历数组并将每个项目添加到 HashSet 中：此操作进行重复数据删除并为我们提供 O(1) 访问时间。整个过程耗时 O(N)
2. 使用数学，假设顶点A，B，C，D可以组成一个正方形，AC已知并且它是一条对角线，那么对应的B，D是唯一的。我们可以编写一个函数来计算它。这个过程是 O(1) 时间
3. 现在让我们回到我们的事情。写一个 for-i-loop 和一个 for-j-inner-loop。说 input[i] 和 input[j] 形成一条对角线，在集合中找到它的对角线与否：如果存在，计数器++；这个过程需要 O(N^2) 时间。

我在 C# 中的代码：

    public int SquareCount(Point[] input)
    {
        int count = 0;

        HashSet<Point> set = new HashSet<Point>();
        foreach (var point in input)
            set.Add(point);

        for (int i = 0; i < input.Length; i++)
        {
            for (int j = 0; j < input.Length; j++)
            {
                if (i == j)
                    continue;
                //For each Point i, Point j, check if b&d exist in set.
                Point[] DiagVertex = GetRestPints(input[i], input[j]);
                if (set.Contains(DiagVertex[0]) && set.Contains(DiagVertex[1]))
                {
                    count++;
                }
            }
        }
        return count;

    }

    public Point[] GetRestPints(Point a, Point c)
    {
        Point[] res = new Point[2];

        int midX = (a.x + c.y) / 2;
        int midY = (a.y + c.y) / 2;

        int Ax = a.x - midX;
        int Ay = a.y - midY;
        int bX = midX - Ay;
        int bY = midY + Ax;
        Point b = new Point(bX,bY);

        int cX =  (c.x - midX);
        int cY =  (c.y - midY);
        int dX = midX - cY;
        int dY = midY + cX;
        Point d = new Point(dX,dY);

        res[0] = b;
        res[1] = d;
        return res;
    }