Find the number of congruent triangles?

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.

Am I counting some triangles more than once or I am missing something by this algorithm? It is a problem on online judge? It gives me wrong answer. I have thought a lot about it, but I am not able to figure it out.

Answer 1

It seems to me that you might be missing a lot of congruent triangles this way. For smaller triangles, there won't be many different angles that you can place a congruent triangle such that all of its vertices are lattice points. But, as the size of the triangle increases, there are more opportunities to snap to the grid, so you could end up with far more than 8 different orientations of the triangle.

Instead, designate one of the points of the example triangle as the origin. Try all the lattice points of a circle of the radius of the first side as locations for the second vertex. Once you've picked the candidate point, calculate the location of the third vertex, and if it is a lattice point too, then calculate how many times the resulting triangle fits into the square without rotation. The only symmetry you have to worry about is if the original triangle is isosceles or equilateral, which would cause you to over count triangles by a factor of 2 and 3 respectively.

Answer 2

Do you want to know exact number of triangles of just estimation?

For "exact" one I don't have a answer but I'm sure that usage of MBR for this is not a good idea - because:

1. there may be triangles that intersect bounds of MBR
2. there may be triangles with integer coords with zoom not equal to integer number (i.e. via rotation. It's a theory (because I don't have a example in hands) but we have to proove that it's wrong before going forward)

If you want to know an estimation than MBR is good enough

Answer 3

The approach you describe is pretty close, but will not count all the congruent triangles in the grid.

The most significant omission is due to the fact that there are rotations that preserve integer coordinates, but are not multiples of 90 degrees.

Consider the triangle with vertices (0,0), (240,0), and (240,180). Rotate it counter-clockwise about the origin by arcsin(3/5), or approximately 37 degrees, to obtain a congruent triangle with vertices (0,0), (192,144), and (84,288).

The bounding box for the new triangle has a different aspect ratio than the original, which also introduces some difficulties.

Here's an algorithm that, given three points on an NxN grid, should enumerate all the congruent triangles in O(N³) time.

Let P=(x,y) denote a point with integer coordinates, and

T(p,q,r) a triangle formed from distinct points p, q, and r.

T(q,r,p), T(r,p,q), T(p,r,q) all denote the same triangle, so we will consider the triangle with

p < q < r

to be its canonical representation.

We can define p < q by the condition:

((p.y < q.y) OR ((p.y = p.y) AND (p.x < q.x)).

Two triangles T1=(A,B,C) and T2=(P,Q,R), with both T1 and T2 in canonical form, are congruent iff:

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

To avoid floating point comparisons, we can compare the squares of the lengths.

Consider a line segment AB, with A at the origin (0,0), A < B, and |AB|² = L.

(Note that sqrt(L) is O(N), since each side of the triangle must fit within an NxN grid, with a maximum diagonal of sqrt(2)*N).

We can find the possible choices of B by testing all the points (x,y) within the triangle defined by

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

This requires calculating |AB|² for O(N²) points, then applying symmetries to generate up to 4 points for each match found in the search area:

If B = (x,y) has x = 0, there are no additional points, since (0,-y) < (0,y), which violates the condition

A < B.

If x = y with x > 0, A < (-x, y) and so (-x, y) is a valid choice for B.

If y < x with x > 0, the points (y, x), (-x, y), and (-y, x) all satisfy the conditions.

Although we have searched O(N²) points, at most O(N) will have the correct length. (They will all lie on a circle of radius sqrt(L) and circumference 2*pi*sqrt(L) from the origin, and will be separated by at least one unit from each other.)

This procedure finds all the possible orientations of a line segment AB, with A < B, and |AB|² = L. Keep this list of points B, then use the same procedure to create lists of points for values of L matching the other two sides of the prototype triangle.

Now we want to build a set of triangles (A, B, C), with A fixed at the origin, and B chosen from the list of points from the list we made for length |AB|. C can be determined in O(1) time by finding the intersection points of two circles, one centered at A with radius |AC|, and the other centered at B with radius |BC|. (This step is most easily accomplished by solving the circle intersection in floating point, then taking the nearest lattice points to the floating point solutions. The lattice points can be confirmed using integer math, then tested to see if any of them satisfy the constraint A < B < C. It is assumed that the floating point calculations are done with sufficient precision to guarantee an error of less than 0.5 units for the intersection points.)

Considering that each (A, B, C) differs from the prototype by only a rotation from a set of size O(N), and symmetries from a set of size O(1), we end up with a list of triangles of length O(N).

Depending on whether the prototype triangle is equilateral, isosceles, or scalene, we will need to consider 1, 3, or 6 permutations of the side lengths to find all the triangles (A,B,C) congruent to the prototype, with A < B < C, and A at the origin. Taking the various permutations into account, this list of triangles still has size O(N).

At this point, some triangles on the list may not actually fit on the grid (perhaps because one side had a length close to sqrt(2)*N and needs to be at an angle to the X axis). For isosceles and equilateral triangles, depending on the details of the search algorithm, some of the triangles may appear more than once, with the redundant triangles' vertices out of order. These can be pruned out of the list, again in O(N) time. The final list of triangles represents the complete set of congruent triangles with A fixed at the origin, meeting all the conditions we have imposed, and is a set of size O(N).

Finally, we allow point A to move away from the origin to some other grid point. There are O(N²) choices for A, and for each choice of A=(x,y), we make a list of O(N) translated triangles by adding the coordinates (x,y) to each of A, B, and C from the "origin" list. We check in O(1) time to make sure each of the translated A, B, C points is still on the NxN grid, and the ones that survive get added to the final output list. The runtime of this step is O(N³), and this dominates the runtime of the entire search algorithm.

Using the above example on a 289x289 grid, our prototype triangle has coordinates A=(0,0), B=(240,0), and C=(240,180). Let Z equal the origin (0,0).

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

From the first part of the algorithm, the points B with L = r²= 57600 from Z and Z < B are:

(0, 240), (240, 0), (144, 192), (192, 144), (-144, 192), (-192, 144)

The points C with L = 32400 and Z < C are:

(0, 180), (180, 0), (108, 144), (144, 108), (-108, 144), (-144, 108)

The points A with L = 90000 and Z < A are:

(84, 288), (288, 84), (-84, 288), (-288, 84), (180, 240), (240, 180), (-180, 240), (-240, 180)

The triangles obtained from these sets of coordinates, after taking all 6 permutations of the side lengths and pruning the ones that don't meet the conditions, are:

(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

Translating these to the 289x289 grid and pruning the ones that don't fit, we get a final list of 43,504 triangles.

The first few:

(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

and the final few:

(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

The runtime was well under one second to generate this list for the 289x289 grid.