你有两组连通的坐标点列表（如下所示），需要编写Python程序统计其中由坐标点构成的正方形数量，且已知可以通过图遍历追踪已访问节点，但没有方向信息。

# 第一组坐标点列表
point_list_1 = [[1, 2], [3, 4], [1, 5], [2, 6], [4, 8], [5, 6], [6, 7], [7, 8], [6, 10], [7, 11], [8, 12], [10, 11], [10, 14], [12, 16], [14, 15], [15, 16]]

# 第二组坐标点列表
point_list_2 = [[1, 2], [2, 3], [3, 4], [1, 5], [4, 8], [6, 7], [5, 9], [6, 10], [7, 11], [8, 12], [9, 13], [10, 11], [12, 16], [13, 14], [14, 15], [15, 16]]

一、预处理：构建高效查询的点集与连通分量（可选） #

• 转换点为可哈希结构：因为列表不能直接存入集合，先把所有坐标点转换成元组，存入set中，这样判断一个点是否存在的时间复杂度是O(1)，比遍历列表高效得多：

  all_points = set(tuple(p) for p in point_list_1)  # 替换成你要处理的目标列表
  

• 划分连通分量（如果需要限制正方形在同一连通区域）：如果要求正方形的四个点必须属于同一个连通分量，先用BFS/DFS遍历所有点，给每个点标记所属的连通ID。这里假设连通性是指两点上下左右相邻（如果是自定义的边连接，只需调整邻接判断逻辑即可）：

  from collections import deque
  
  def get_connected_components(points_set):
      visited = set()
      component_map = {}
      current_id = 0
      # 上下左右四个相邻方向
      directions = [(-1,0), (1,0), (0,-1), (0,1)]
      
      for point in points_set:
          if point not in visited:
              queue = deque([point])
              visited.add(point)
              while queue:
                  x, y = queue.popleft()
                  component_map[(x,y)] = current_id
                  # 检查所有相邻点
                  for dx, dy in directions:
                      neighbor = (x+dx, y+dy)
                      if neighbor in points_set and neighbor not in visited:
                          visited.add(neighbor)
                          queue.append(neighbor)
              current_id += 1
      return component_map
  
  # 获取每个点的连通分量ID
  component_map = get_connected_components(all_points)
  

二、遍历点对，计算潜在正方形的顶点 #

正方形的核心几何性质是：任意一条边旋转90度后能得到相邻的边。我们可以通过遍历所有点对，计算另外两个可能的顶点，再验证这两个顶点是否存在于点集中：

• 遍历所有不重复的点对（只处理i < j的点对，避免重复计算A-B和B-A）
• 对每对点A(x1,y1)和B(x2,y2)，计算边向量(dx, dy) = (x2-x1, y2-y1)
• 生成两种垂直方向的向量（对应顺时针和逆时针旋转90度），计算另外两个顶点C和D
• 检查C和D是否在点集中，同时（如果需要连通性）检查四个点是否属于同一连通分量

示例代码片段：

found_squares = set()
points_list = list(all_points)
total_points = len(points_list)

for i in range(total_points):
    x1, y1 = points_list[i]
    for j in range(i + 1, total_points):
        x2, y2 = points_list[j]
        dx = x2 - x1
        dy = y2 - y1

        # 情况1：逆时针旋转90度得到的正方形顶点
        c_x, c_y = x1 - dy, y1 + dx
        d_x, d_y = x2 - dy, y2 + dx
        c_point = (c_x, c_y)
        d_point = (d_x, d_y)
        
        if c_point in all_points and d_point in all_points:
            # 可选：检查四个点是否在同一连通分量
            if component_map[(x1,y1)] == component_map[(x2,y2)] == component_map[c_point] == component_map[d_point]:
                # 排序四个点，确保同一个正方形只会被记录一次
                sorted_square = tuple(sorted(((x1,y1), (x2,y2), c_point, d_point)))
                found_squares.add(sorted_square)

        # 情况2：顺时针旋转90度得到的正方形顶点
        c_x2, c_y2 = x1 + dy, y1 - dx
        d_x2, d_y2 = x2 + dy, y2 - dx
        c_point2 = (c_x2, c_y2)
        d_point2 = (d_x2, d_y2)
        
        if c_point2 in all_points and d_point2 in all_points:
            if component_map[(x1,y1)] == component_map[(x2,y2)] == component_map[c_point2] == component_map[d_point2]:
                sorted_square2 = tuple(sorted(((x1,y1), (x2,y2), c_point2, d_point2)))
                found_squares.add(sorted_square2)

三、去重与统计结果 #

• 我们用set存储排序后的正方形顶点元组，这样同一个正方形无论从哪条边开始检测，都会被转换成相同的元组，不会重复计数
• 最终正方形的数量就是found_squares集合的长度：

  print(f"检测到的正方形数量：{len(found_squares)}")
  

关键注意事项 #

• 避免重复计算：通过只遍历i < j的点对，以及对正方形顶点排序后存入集合，彻底解决重复计数的问题
• 连通性判断：如果不需要限制正方形在同一连通区域，只需去掉代码中关于component_map的判断逻辑即可
• 性能优化：如果点的数量很大，可以考虑提前过滤掉零长度的点对（即两个点完全相同的情况），减少无效计算

内容的提问来源于stack exchange，提问作者user1411837