在给定n个点的平面中找到正方形
给定一个平面中的n个点，可以形成多少个方格……
我通过计算每个2点之间的距离，然后对它们进行排序，并在validation点和斜率后查找具有四个或更多相等距离的点中的方块来尝试此操作。
但这看起来像是一种复杂性很高的方法。 任何其他想法……？
我认为用于检查相等距离的线段的动态编程可能会起作用……但是无法将想法弄得恰到好处……
任何更好的想法？
PS：正方形可以是任何方式。 它们可以重叠，有一个共同的一面，一个正方形在另一个…
任何有助于我更好地理解问题的链接都是可观的……如果可能的话，请提供示例代码来执行上述操作…
设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)更糟（我甚至不确定它会变得那么糟糕）。
这个问题可以在O(n^1.5)时间内用O(n)空间来解决。
基本思想是按X或Y坐标对点进行分组，小心避免使组太大。 详细信息请参阅文章查找点集中的正方形和矩形 。 该论文还涵盖了许多其他案例（允许旋转的正方形，允许矩形，并在更高的维度工作）。
我已经解释了下面的2d轴对齐方形查找算法。 请注意，我将其树集更改为哈希集，这就是为什么我给出的时间限制不是O(n^1.5 log(n)) ：
-
制作所有点的哈希集。 你可以用来快速检查一个点是否存在的东西。
-
按X坐标对点进行分组。 打破任何超过
sqrt(n)点的组，并按Y坐标重新分组这些现在自由点。 这保证了团体最多只有sqrt(n)点并且保证每个正方形都有一个具有两个正方形角点的组。 -
对于每个组
g，对于g中的每对点p,q，检查是否存在包含p和q的两个可能正方形中的另外两个点。 跟踪您找到的数量。 注意重复（在一组中也是两个相反的点？）。
它为什么有效？ 嗯，唯一棘手的事情就是重新组合。 如果正方形的左列或右列都在不太大的组中，则在该列组被迭代时将找到该正方形。 否则，它的左上角和右上角都会重新分组，放入同一行组，并且当该行组被迭代时将找到方形。
它看起来像O（n ^ 3）。 一个简单的算法可能是这样的：
for each pair of points for each of 3 possible squares which might be formed from these two points test remaining points to see if they coincide with the other two vertices
此pdf包含相同的详细算法。
只是一个想法：如果顶点A是正方形的一个角，则在其他角处必须有顶点B，C，D，AB = AD且AC = sqrt（2）AB和AC必须平分BD。 假设每个顶点都有唯一的坐标，我认为你可以用O（n ^ 2）解决这个问题，其中哈希表键入（距离，角度）。
我有一个O（N ^ 2）时间，O（N）空间解决方案：
假设给定的点是一个对象Point数组，每个Point都有x，y。
- 首先遍历数组并将每个项添加到HashSet中：此操作会重复删除并为我们提供O（1）访问时间。 整个过程需要O（N）时间
- 使用Math，Say顶点A，B，C，D可以形成一个正方形，AC是已知的并且它是一条对角线，那么相应的B，D是唯一的。 我们可以写一个函数来计算它。 这个过程是O（1）时间
- 现在让我们回到我们的事情。 写一个for-i-loop和一个for-j-inner-loop。 假设输入[i]和输入[j]形成对角线，在集合中找到它的反对角线：如果存在，则计数器++; 此过程需要O（N ^ 2）时间。
我在C＃中的代码：
public int SquareCount(Point[] input) { int count = 0; HashSet set = new HashSet (); 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 = (ax + cy) / 2; int midY = (ay + cy) / 2; int Ax = ax - midX; int Ay = ay - midY; int bX = midX - Ay; int bY = midY + Ax; Point b = new Point(bX,bY); int cX = (cx - midX); int cY = (cy - midY); int dX = midX - cY; int dY = midY + cX; Point d = new Point(dX,dY); res[0] = b; res[1] = d; return res; }