寻找相似三角形的数量？

Question

寻找相似三角形的数量？

3

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.

我是否重复计算了一些三角形或者说这个算法有什么遗漏？这是一个在线评测的问题吗？它给出了错误的答案。我已经思考了很多，但是我无法找到答案。

- avd

有趣的问题...事实证明，这个问题太有趣了，我不能不给出一个真正的答案。享受吧！顺便问一下，这个问题来自哪里...我不认为这个问题在欧拉计划中出现过？ - Jim Lewis

@Jim：我甚至忘记了这道题的在线评测系统是从哪里来的。 - avd

3个回答

2

我认为你可能会错过很多个全等三角形。对于较小的三角形，你可能无法找到许多不同的角度来放置一个全等三角形，使得它的所有顶点都是格点。但是，随着三角形的大小增加，有更多的机会与网格吻合，因此你可能会得到远超过8个不同方向的三角形。

相反，将示例三角形的其中一个点指定为原点。尝试以第一条边的半径为半径的所有圆格点作为第二个顶点的位置。一旦选定了候选点，计算第三个顶点的位置，如果它也是格点，则计算出该三角形在不旋转的情况下适合正方形的次数。你唯一需要担心的对称性是原始三角形是否等腰或等边，这会导致你过度计算三角形的数量，分别为2和3倍。

- Theran

请给我一个例子，说明在大三角形的情况下我可能会错过什么。由于它在MBR中，我认为它不可能超过8。 - avd

MBR意味着其3个顶点都位于最小边界矩形的一侧或另一侧。由于我们只想要格点，所以我们无需检查每种组合。 - avd

我有非常严格的时间限制。你建议的算法可能需要很多时间。 - avd

但这将非常快。即使是朴素实现，它在三角形最短边的长度为O(N)。 - Jason Orendorff

1

你想知道是要精确计算三角形的数量还是估算呢？

对于“精确”的计算，我没有答案，但我确定使用MBR不是一个好主意，因为：

可能会有与MBR边界相交的三角形
可能会有整数坐标的三角形，缩放比例不等于整数（即通过旋转实现）。这只是一种理论（因为我手头没有例子），但我们必须证明它是错误的，然后再继续。

如果您只是想估算，则MBR已经足够了。

- Meta

我认为一个好的想法是通过尝试圆周内的所有三点（如果我们搜索最大适合三角形）来找出所有可能的这样或更小的三角形。然后，我们需要用这些三角形填充正方形（贪婪算法可能是一个不错的开始）。 - Meta

你能在帖子中更详细地阐述一下这个算法吗？我没有理解这个想法。 - avd

1

我的意思是我们应该取所有在外接圆内的全等三角形。然后我们使用这个集合来填充正方形。获取所有三角形的复杂度为：

获取第一个点（~N^2，其中N与三角形边长成比例）
获取第二个点（~N^2）
尝试获取第三个点，假设我们有一个正方形的一条边（1）

因此，结果的复杂度是N^2，以获取完整的三角形集合。对于小正方形/小三角形集，暴力填充正方形可能是不错的选择-它是N(P)复杂度任务，您必须阅读Knut或其他大师才能填充真正大的正方形。 - Meta

这里我是指“三角形”，而不是正方形的一边。 - Meta

嗯...看起来我误解了你的任务。你需要用这些三角形填充正方形，还是只需要找到一定数量的全等三角形？ :) - Meta

为了找到适合给定正方形的全等三角形变体的数量，我只能假设一个O(z^2)复杂度的算法。 - Meta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Lewis · Accepted Answer

你所描述的方法非常接近，但无法计算网格中所有全等的三角形。

最重要的遗漏是因为存在保持整数坐标但不是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|² = 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(N²)种选择，对于每个A=(x,y)的选择，我们将A、B和C从“起点”列表中加上坐标(x,y)，得到O(N)个已翻译的三角形列表。我们在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的距离为L=r²=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 网格的列表时，运行时间不到一秒钟。