如何快速在点数组中找出所有正方形？O(n⁴)算法性能亟待优化

问题背景 #

程序功能正常但性能极差，核心需求是从点数组中找出所有正方形。当前采用四层嵌套循环遍历所有4点组合，时间复杂度约为O(n⁴)，100个点时性能尚可，但500个点时500⁴的运算量完全无法承受，急需更高效的实现方法。

当前实现代码：

/*j, o, k, l are numbers of each point. This loop will check all possible combinations
(except 2 or more points have the same number(it means also the same coordinades) or they already are part of some figure*/ 
for (int j=0; j < i-1; j++)
{      
    if (Point[j].p != true)
    {
        for (int o = 1; o < i - 2; o++)
        {
            if ((o != j) && (Point[o].p != true))
            {
                for (int k = 2; k < i - 3; k++)
                {
                    if ((k!= j) && (k != o) && (Point[k].p != true))
                    {
                        for (int l = 3; l < i - 4; l++)
                        {
                            if ((l != k) && (Point[l].p != true) && (l != o) && (l!=j))
                            {
                                vx1 = abs(Point[o].x - Point[j].x); //vectors coordinates
                                vx2 = abs(Point[k].x - Point[o].x);
                                vy1 = abs(Point[o].y - Point[j].y);
                                vy2 = abs(Point[k].y - Point[o].y);
                                vx3 = abs(Point[l].x - Point[k].x);
                                vy3 = abs(Point[l].y - Point[k].y);
                                vx4 = abs(Point[j].x - Point[l].x);
                                vy4 = abs(Point[j].y - Point[l].y);
                                dx1 = abs(Point[k].x - Point[j].x); //diagonals coordinates
                                dy1 = abs(Point[k].y - Point[j].y);
                                dx2 = abs(Point[o].x - Point[l].x);
                                dy2 = abs(Point[o].y - Point[l].y);
                                v1 = sqrt(vx1 * vx1 + vy1 * vy1); // sides length
                                v2 = sqrt(vx2 * vx2 + vy2 * vy2);
                                v3 = sqrt(vx3 * vx3 + vy3 * vy3);
                                v4 = sqrt(vx4 * vx4 + vy4 * vy4);
                                d1 = sqrt(dx1 *dx1 + dy1 * dy1); //diagonals length
                                d2 = sqrt(dx2 * dx2 + dy2 * dy2);
                                if (
                                    ((abs(v1-v2)<=0.5) && (abs(v3-v4)<=0.5) && (abs(v3-v2)<=0.5) && (v1<d1)) /*cheks all sides are equal and if the diagonal is bigger than side*/  
                                    && (Point[k].p != true && Point[o].p != true && Point[j].p != true)/*checks if the points aren`t the part of any figure yet*/ 
                                    &&(abs(d1 - d2)<=0.5)/*checks if the diagonals are equal*/)
                                {
                                    q++;
                                    Point[j].p = true; // it means that point with this number is already a part of some figure, so it will be skipped in next operations
                                    Point[o].p = true;
                                    Point[k].p = true;
                                    Point[l].p = true;
                                    // the output
                                    out << "Figure " << q << ":" << "x1=" << Point[j].x << " y1=" << Point[j].y << " x2="
                                        << Point[o].x << " y2=" << Point[o].y <<
                                        " x3=" << Point[k].x << " y3=" << Point[k].y <<
                                        " x4=" << Point[l].x << " y4=" << Point[l].y << endl;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

优化方案：将时间复杂度降至O(n²) #

方案1：基于对角线特性的哈希匹配 #

正方形的核心特性：两条对角线中点相同、长度相等且互相垂直。利用这一点可以大幅减少计算量：

• 遍历所有点对，计算每对点的：
  1. 中点坐标（可用整数对表示，避免浮点误差，比如将坐标乘2后存储）
  2. 对角线长度的平方（(x2-x1)² + (y2-y1)²，避免开根号）
  3. 点对的向量（(x2-x1, y2-y1)）
• 用哈希表将中点+对角线长度平方作为键，对应的点对列表作为值。所有能组成正方形的点对会被分到同一个键下。
• 遍历每个键对应的点对列表，检查任意两个点对的向量是否互相垂直（向量点积为0）：若点对1的向量是(a,b)，点对2的向量是(c,d)，则满足a*c + b*d = 0时，这两个点对可组成正方形。
• 去重：将正方形的四个点按坐标排序后存入集合，确保每个正方形只被输出一次。

方案2：基于边向量旋转的点存在性检查 #

利用正方形边的旋转特性推导其他点：

• 先将所有点存入哈希集合（自定义点的哈希函数，或用pair<int, int>作为键），实现O(1)时间的点存在性查询。
• 遍历每对点P1(x1,y1)和P2(x2,y2)，计算边向量(dx, dy) = (x2-x1, y2-y1)。
• 正方形的邻边是原边旋转90度得到，有两种可能的旋转方向：
  1. 顺时针旋转90度：向量变为(dy, -dx)，推导另外两个点P3(x1+dy, y1-dx)、P4(x2+dy, y2-dx)
  2. 逆时针旋转90度：向量变为(-dy, dx)，推导另外两个点P3(x1-dy, y1+dx)、P4(x2-dy, y2+dx)
• 检查P3和P4是否存在于点集合中，若存在则找到一个正方形。
• 去重：同样用排序后的点序列作为标识，避免重复记录。

额外性能优化细节 #

• 避免浮点运算：所有长度、距离的比较均用平方值代替开根号，既提升性能又避免浮点精度误差。
• 过滤无效点对：直接跳过两个点重合的情况（向量长度为0），减少不必要的计算。
• 移除原代码的Point[p]标记逻辑：原逻辑会导致同一正方形的点被标记后无法参与其他正方形的检测，若需求是找出所有正方形而非不重叠的正方形，此逻辑需删除；若需不重叠，可在找到正方形后再标记点。

内容的提问来源于stack exchange，提问作者В'ячеслав Іванчук