我有一个小竞赛问题，其中给出了一组二维点，形成一个三角形。这个三角形可以进行任意旋转，可以进行任意平移（都在 2D 平面中）并且可以在镜子上进行反射，但其尺寸保持不变。然后，他们给了我平面上的一组点，我必须在一个或多个几何运算后找到构成我的三角形的 3 个点。
例子：
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
Output:
5 17
10 5
15 20
我打赌它应该应用一些已知的算法，但我不知道是哪个。最常见的有：凸包、扫描平面、三角剖分等。
有人可以给小费吗？我不需要代码，只需要一个推送，拜托！
三角形由其三个边的长度唯一定义（忽略旋转、翻转和平移）。标记原始三角形 A、B、C 的顶点。您正在寻找点 D、E、F 使得 |AB| = |德|, |交流| = |DF| 和 |BC| = |EF|。长度由毕达哥拉斯公式给出（但您可以通过比较线段长度的平方在每次测试中保存平方根运算......）
给定的三角形由三个长度定义。您想在列表中找到由这些长度分隔的三个点。
平方给定的长度以避免打扰sqrt。
求列表中每对点之间距离的平方，只注意那些与给定长度一致的点：O(V^2)，但系数较低，因为大多数长度不匹配。
现在你有一个带有 O(V) 边的稀疏图。在 O(V) 时间内找到每个大小为 3 的循环，并修剪匹配项。（不确定最好的方法，但这是一种适当的大 O 方法。）
总复杂度：O(V^2) 但在 O(V) 中找到循环可能是限制因素，具体取决于点数。对点列表进行空间排序以避免查看所有对应该改善渐近行为，否则。
这通常通过矩阵数学来完成。 这篇 Wikipedia 文章涵盖了旋转、平移和反射矩阵。这是另一个网站（带图片）。
由于变换只是旋转、缩放和镜像，那么您可以通过检查三角形两侧的点积来找到形成变换三角形的点：
这有效，因为 AB.AC = |AB| x |交流| x cos(a)，两个长度和它们之间的角度定义了一个三角形。
编辑：是的，Jim 是对的，只有一个点积是不够的，你需要做所有三个，包括 ED.EF 和 FD.FE。所以最后，这里的计算数量与平方距离方法的计算数量相同。