你所描述的方法非常接近,但无法计算网格中所有全等的三角形。
最重要的遗漏是因为存在保持整数坐标但不是90度倍数的旋转。
考虑顶点为(0,0),(240,0)和(240,180)的三角形。将其逆时针绕原点旋转arcsin(3/5)或约37度,以获得顶点为(0,0),(192,144)和(84,288)的全等三角形。
新三角形的边界框具有不同的长宽比,这也引入了一些困难。
以下是一个算法,给定NxN网格上的三个点,应在O(N ^ 3)时间内枚举所有全等的三角形。
设P =(x,y)表示具有整数坐标的点,
T(p,q,r)表示由不同的点p,q和r形成的三角形。
T(q,r,p),T(r,p,q),T(p,r,q)都表示相同的三角形,因此我们将考虑
具有p < q < r的三角形为其规范表示形式。
我们可以通过以下条件定义 p < q:
((p.y < q.y) OR ((p.y = p.y) AND (p.x < q.x))。
两个三角形 T1=(A,B,C) 和 T2=(P,Q,R),且 T1 和 T2 都处于规范形式中,当且仅当它们全等时:
|AB| = |PQ|,
|BC| = |QR|, and
|CA| = |RP|.
为了避免浮点数比较,我们可以比较长度的平方。
考虑一个线段AB,其中A位于原点(0,0),A
(请注意,sqrt(L)是O(N),因为三角形的每一条边都必须适合于NxN网格中,最大对角线为sqrt(2)*N)。
我们可以通过测试在由三角形定义的所有点(x,y)来找到可能的B的选择。
(0,0),
(0,ceil(sqrt(L)), and
(ceil(sqrt(L), ceil(sqrt(L))
这需要计算O(N^2)个点的|AB|^2,然后应用对称性为在搜索区域中找到的每个匹配生成多达4个点:
如果B = (x,y)具有x = 0,则没有其他点,因为(0,-y)<(0,y),违反条件A
如果x = y且x>0,则A<(-x,y),因此(-x,y)是一个有效的选择B。
如果y0,则点(y,x),(-x,y)和(-y,x)都满足条件。
尽管我们已经搜索了O(N^2)个点,但最多只有O(N)个点具有正确的长度。(它们都位于半径为sqrt(L)、周长为2*pi*sqrt(L)的圆上,并且彼此之间至少相隔一个单位。)
该过程找到线段AB的所有可能方向,其中A < B,并且|AB|
2 = L。保留这些点B的列表,然后使用相同的过程为原型三角形的另外两条边匹配L值创建点列表。
现在,我们想要构建一组三角形(A,B,C),其中A固定在原点,B从我们为长度|AB|制作的点列表中选择。可以通过找到以|AC|为半径以A为中心的圆和以|BC|为半径以B为中心的圆的
交点来在O(1)时间内确定C。(这一步最容易通过浮点数解决圆形交点,然后取最近的格点来完成。可以使用整数运算确认格点,然后测试它们是否满足约束条件A < B < C。假设浮点计算具有足够的精度,以保证交点的误差小于0.5个单位。)
考虑到每个三角形(A、B、C)与原型之间的差异仅为大小为O(N)的一组旋转和大小为O(1)的一组对称性,我们最终得到了一个长度为O(N)的三角形列表。
根据原型三角形是等边、等腰还是不等边,我们需要考虑1、3或6个边长的排列方式,以找到所有与原型相似的三角形(A、B、C),其中A < B < C,A在原点。考虑到各种排列方式,这个三角形列表的大小仍然为O(N)。
此时,列表中的一些三角形实际上可能不适合于网格(可能是因为一条边的长度接近sqrt(2)*N并且需要与X轴成角度)。对于等腰和等边三角形,根据搜索算法的细节,一些三角形可能会出现多次,冗余三角形的顶点顺序可能会错乱。这些可以在O(N)时间内从列表中剪枝。最终的三角形列表表示满足我们所施加的所有条件,且A固定在原点的全等三角形的完整集合,并且其大小为O(N)。
最后,我们允许点A从原点移动到其他的网格点。点A有O(N2)种选择,对于每个A=(x,y)的选择,我们将A、B和C从“起点”列表中加上坐标(x,y),得到O(N)个已翻译的三角形列表。我们在O(1)时间内检查,以确保每个已翻译的A、B、C点仍然在NxN网格上,并将幸存下来的点添加到最终输出列表中。这一步的运行时间为O(N3),这支配了整个搜索算法的运行时间。
在一个289x289的网格上使用上述示例,我们的原型三角形具有坐标A=(0,0),B=(240,0)和C=(240,180)。设Z为原点(0,0)。
|AB|2为57600。
|BC|2为32400。
|CA|2为90000。
从算法的第一部分开始,距离Z的距离为L=r2=57600且Z<B的点B为:
(0, 240), (240, 0), (144, 192), (192, 144), (-144, 192), (-192, 144)
当L=32400且Z<C时,点C的坐标为:
(0, 180), (180, 0), (108, 144), (144, 108), (-108, 144), (-144, 108)
当L=90000且Z<A时,点A的坐标为:
(84, 288), (288, 84), (-84, 288), (-288, 84), (180, 240), (240, 180),
(-180, 240), (-240, 180)
从这些坐标集合中获得的三角形,在取所有6个边长的排列并剪枝不符合条件的情况下,为:
(0, 0),(-180, 240),(0, 240) L= 90000 32400 57600
(0, 0),(0, 240),(180, 240) L= 57600 32400 90000
(0, 0),(240, 0),(240, 180) L= 57600 32400 90000
(0, 0),(192, 144),(84, 288) L= 57600 32400 90000
(0, 0),(-192, 144),(-84, 288) L= 57600 32400 90000
(0, 0),(240, 0),(0, 180) L= 57600 90000 32400
(0, 0),(0, 180),(240, 180) L= 32400 57600 90000
(0, 0),(180, 0),(180, 240) L= 32400 57600 90000
(0, 0),(108, 144),(-84, 288) L= 32400 57600 90000
(0, 0),(-108, 144),(84, 288) L= 32400 57600 90000
(0, 0),(180, 0),(0, 240) L= 32400 90000 57600
(0, 0),(144, 108),(-144, 192) L= 32400 90000 57600
(0, 0),(-144, 108),(144, 192) L= 32400 90000 57600
(0, 0),(-240, 180),(0, 180) L= 90000 57600 32400
(0, 0),(288, 84),(144, 192) L= 90000 32400 57600
(0, 0),(-288, 84),(-144, 192) L= 90000 32400 57600
(0, 0),(-180, 240),(0, 240) L= 90000 32400 57600
将它们转换为289x289的网格并修剪不符合条件的部分,我们得到最终的三角形列表,共计43,504个。
前几个如下:
(0, 0),(0, 240),(180, 240) L= 57600 32400 90000
(0, 0),(240, 0),(240, 180) L= 57600 32400 90000
(0, 0),(192, 144),(84, 288) L= 57600 32400 90000
(0, 0),(240, 0),(0, 180) L= 57600 90000 32400
(0, 0),(0, 180),(240, 180) L= 32400 57600 90000
(0, 0),(180, 0),(180, 240) L= 32400 57600 90000
(0, 0),(180, 0),(0, 240) L= 32400 90000 57600
(0, 0),(288, 84),(144, 192) L= 90000 32400 57600
(0, 1),(0, 241),(180, 241) L= 57600 32400 90000
(0, 1),(240, 1),(240, 181) L= 57600 32400 90000
(0, 1),(240, 1),(0, 181) L= 57600 90000 32400
最后几个:
(288, 94),(0, 178),(144, 286) L= 90000 32400 57600
(288, 95),(48, 275),(288, 275) L= 90000 57600 32400
(288, 95),(0, 179),(144, 287) L= 90000 32400 57600
(288, 96),(48, 276),(288, 276) L= 90000 57600 32400
(288, 96),(0, 180),(144, 288) L= 90000 32400 57600
(288, 97),(48, 277),(288, 277) L= 90000 57600 32400
(288, 98),(48, 278),(288, 278) L= 90000 57600 32400
(288, 99),(48, 279),(288, 279) L= 90000 57600 32400
(288, 100),(48, 280),(288, 280) L= 90000 57600 32400
(288, 101),(48, 281),(288, 281) L= 90000 57600 32400
(288, 102),(48, 282),(288, 282) L= 90000 57600 32400
(288, 103),(48, 283),(288, 283) L= 90000 57600 32400
(288, 104),(48, 284),(288, 284) L= 90000 57600 32400
(288, 105),(48, 285),(288, 285) L= 90000 57600 32400
(288, 106),(48, 286),(288, 286) L= 90000 57600 32400
(288, 107),(48, 287),(288, 287) L= 90000 57600 32400
(288, 108),(48, 288),(288, 288) L= 90000 57600 32400
在生成这个 289x289 网格的列表时,运行时间不到一秒钟。