找到全等三角形的数量？

Question

Say I have a square from (0,0) to (z,z). 
Given a triangle within this square which has integer coordinates 
for all its vertices.
Find out the number of  triangles within this square which are 
congruent to this triangle and have integer coordinates. 
My algorithm is as follows--


 1) Find out the minimum bounding rectangle(MBR) for the given triangle.
 2) Find out the number of congruent triangles, y within that MBR,
    obtained after reflection, rotation of the given triangle. 
    y can be either 2,4 or 8.
 3) Now find out how many such MBR's can be drawn within the given 
    big square, say x;
    (This is similar to finding number of squares on a chess board)
 4) x*y is the required answer.

我不止一次计算一些三角形,或者我错过了这个算法的东西？这是在线评判的问题吗？它给了我错误的答案.我已经考虑了很多,但我无法弄明白.

Answer 1

您描述的方法非常接近,但不会计算网格中所有全等三角形.

最重要的遗漏是由于存在保持整数坐标的旋转,但不是90度的倍数.

考虑具有顶点(0,0),(240,0)和(240,180)的三角形.通过arcsin(3/5)或大约37度逆着原点逆时针旋转它,以获得具有顶点(0,0),(192,144)和(84,288)的全等三角形.

新三角形的边界框具有与原始边框不同的纵横比,这也带来了一些困难.

这是一个算法,给定NxN网格上的三个点,应该在O(N ³)时间内枚举所有全等三角形.

令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:

((py <qy)OR((py = py)AND(px <qx)).

两个三角形T1 =(A,B,C)和T2 =(P,Q,R),T1和T2都是规范形式,如果:

|AB| = |PQ|,
|BC| = |QR|, and 
|CA| = |RP|.

为了避免浮点比较,我们可以比较长度的平方.

考虑一个线段AB,其中A位于原点(0,0),A <B和| AB | ² = L.

(注意,sqrt(L)是O(N),因为三角形的每一边必须适合NxN网格,最大对角线为sqrt(2)*N).

我们可以通过测试由三角形定义的三角形内的所有点(x,y)来找到B的可能选择

(0,0), 
(0,ceil(sqrt(L)), and 
(ceil(sqrt(L), ceil(sqrt(L))

这需要计算| AB | ²对于O(N ²)个点,然后应用对称性为搜索区域中找到的每个匹配生成最多4个点:

如果B =(x,y)有x = 0,则没有其他点,因为(0,-y)<(0,y),这违反了条件

A <B

如果x = y且x> 0,则A <(-x,y)等等(-x,y)是B的有效选择.

如果y <x且x> 0,则点(y,x),( - x,y)和(-y,x)都满足条件.

虽然我们搜索了O(N ²)个点,但最多O(N)将具有正确的长度.(它们将全部位于半径为sqrt(L)的圆上,圆周距离原点2*pi*sqrt(L),并且至少相互间隔一个单位.)

该过程找到线段AB的所有可能取向,其中A <B和| AB | ² = L.保留点B的列表,然后使用相同的过程为L值匹配原型三角形的另外两侧创建点列表.

现在我们要构建一组三角形(A,B,C),其中A固定在原点,B从我们为长度| AB |制作的列表中的点列表中选择.通过找到两个圆的交点,可以在O(1)时间内确定C ,其中一个圆以A为中心,半径为| AC |,另一个以B为中心,半径为| BC |.(这个步骤最容易通过求解浮点的圆交点,然后将最近的格点指向浮点解.格点可以使用整数数学确认,然后测试它们是否满足约束条件A <B <C.假设浮点计算以足够的精度完成,以保证交点的误差小于0.5个单位.)

考虑到每个(A,B,C)与原型的不同之处仅在于从一组大小为O(N)的旋转,以及来自一组大小为O(1)的对称,我们最终得到一个长度为三角形的列表上).

根据原型三角形是等边,等腰还是斜角,我们需要考虑边长的1个,3个或6个排列,以找到与原型一致的所有三角形(A,B,C),A < B <C,A在原点.考虑到各种排列,这个三角形列表仍然具有大小O(N).

此时,列表上的某些三角形可能实际上不适合网格(可能是因为一侧的长度接近sqrt(2)*N并且需要与X轴成一定角度).对于等腰和等边三角形,根据搜索算法的细节,一些三角形可能出现不止一次,冗余三角形的顶点不按顺序排列.这些可以在O(N)时间内从列表中删除.最后的三角形列表代表完整的全等三角形集合,其中A固定在原点,满足我们施加的所有条件,并且是一组大小为O(N).

最后,我们允许A点从原点移动到其他网格点.对于A 有O(N ²)个选择,并且对于A =(x,y)的每个选择,我们通过将坐标(x,y)添加到A,B中的每一个来制作O(N)个翻译三角形的列表. ,和来自"起源"列表的C. 我们检查O(1)时间以确保每个翻译的A,B,C点仍然在NxN网格上,并且存活的点被添加到最终输出列表中.此步骤的运行时为O(N ³),这将占据整个搜索算法的运行时间.

在289x289网格上使用上述示例,我们的原型三角形具有坐标A =(0,0),B =(240,0)和C =(240,180).设Z等于原点(0,0).

| AB | ²是57600. | BC | ²是32400. | CA | ²是90000.

从算法的第一部分开始,Z和Z <B的L = r ² = 57600 的点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网格生成此列表.