Computational geometry: find where the triangle is after rotation, translation or reflection on a mirror

Question

I have a small contest problem in which is given a set of points, in 2D, that form a triangle. This triangle may be subject to an arbitrary rotation, may be subject to an arbitrary translation (both in the 2D plane) and may be subject to a reflection on a mirror, but its dimensions were kept unchanged. Then, they give me a set of points in the plane, and I have to find 3 points that form my triangle after one or more of those geometric operations.

Example:

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

I bet it's supposed to apply some known algorithm, but I don't know which. The most common are: convex hull, sweep plane, triangulation, etc.

Can someone give a tip? I don't need the code, only a push, please!

Answer 1

This is generally done with matrix math. This Wikipedia article covers the rotation, translation, and reflection matrices. Here's another site (with pictures).

Answer 2

A triangle is uniquely defined (ignoring rotations, flips, and translations) by the lengths of its three sides. Label the vertices of your original triangle A,B,C. You're looking for points D,E,F such that |AB| = |DE|, |AC| = |DF|, and |BC| = |EF|. The length is given by Pythagoras' formula (but you can save a square root operation at each test by comparing the squares of the line segment lengths...)

Answer 3

Since the transformations are just rotation, scaling and mirroring, then you can find the points that form the transformed triangle by checking the dot product of two sides of the triangle:

1. For the original triangle A, B, C, calculate the dot product of AB.AC, BA.BC and CA.CB
2. For each set of three points D, E, F, calculate dot product of DE.DF and compare against the three dot products found in 1.

This works since AB.AC = |AB| x |AC| x cos(a), and two lengths and an angle between them defines a triangle.

EDIT: Yes, Jim is right, just one dot product isn't enough, you'll need to do all three, including ED.EF and FD.FE. So in the end, there's the same number of calculations in this as there is in the square distances method.

Answer 4

The given triangle is defined by three lengths. You want to find three points in the list separated by exactly those lengths.

Square the given lengths to avoid bothering with sqrt.

Find the square of the distance between every pair of points in the list and only note those that coincide with the given lengths: O(V^2), but with a low coefficient because most lengths will not match.

Now you have a sparse graph with O(V) edges. Find every cycle of size 3 in O(V) time, and prune the matches. (Not sure of the best way, but here is one way with proper big-O.)

Total complexity: O(V^2) but finding the cycles in O(V) may be the limiting factor, depending on the number of points. Spatially sorting the list of points to avoid looking at all pairs should improve the asymptotic behavior, otherwise.