Algorithm for reflecting a point across a line

Question

Given a point (x1, y1) and an equation for a line (y=mx+c), I need some pseudocode for determining the point (x2, y2) that is a reflection of the first point across the line. Spent about an hour trying to figure it out with no luck!

See here for a visualization - http://www.analyzemath.com/Geometry/Reflection/Reflection.html

Answer 1

This link contains an algorithm that is similar to what you are trying to do:

That is reflect a ray off a normal.

alt text http://local.wasp.uwa.edu.au/~pbourke/geometry/reflected/diagram.gif

Answer 2

This is a simple explanation of Il-Bhima's solution. The trick is to notice that what you want is to project that point orthogonally on the line, move it by that much, and then move it once again, in the same direction.

For these types of problems, it's easier to work with a slightly more redundant representation for a line. Instead of y = m x + b, let's represent the line by a point p that is on the line and a vector d in the line's direction. Let's call this point p = (0, b), the vector d = (1, m), and your input point will be p1. The projected point on the line will be pl and your output point p2, then, is p1 + 2 * (pl - p1) = 2 * pl - p1

The formula you need here is the projection of a vector v onto a line which goes through the origin in direction d. It is given by d * <v, d> / <d, d> where <a, b> is the dot product between two vectors.

To find pl, we have to move the whole problem so that the line goes through the origin by subtracting p from p1, using the above formula, and moving it back. Then, pl = p + (d * <p - p1, d> / <d, d>), so pl_x = p_x + (b * p1_x) / (1 + m * m), pl_y = p_y + (m * p1_x) / (1 + m * m), and then use p2 = 2 * pl - p1 to get the final values.

Answer 3

Reflection can be found in two steps. First translate (shift) everything down by b units, so the point becomes V=(x,y-b) and the line becomes y=mx. Then a vector inside the line is L=(1,m). Now calculate the reflection by the line through the origin,

(x',y') = 2(V.L)/(L.L) * L - V

where V.L and L.L are dot product and * is scalar multiple.

Finally, shift everything back up by adding b, and the final answer is (x',y'+b).

As an affine transformation you can write the above operation as the composition (product) of three matrices, first representing the shift y => y-b, then the reflection through the line through the origin, then the shift y => y+b:

[ 1 0 0] [(1-m^2)/(1+m^2)      2m/(1+m^2) 0] [ 1 0  0] [x]
[ 0 1 b] [     2m/(1+m^2) (m^2-1)/(1+m^2) 0] [ 0 1 -b] [y]
[ 0 0 1] [             0               0  1] [ 0 0  1] [1]

The situation is very similar to rotation matrices in affine geometry. If you already have matrix multiplication routines available, because you're also doing rotations for example, this might be the most maintainable way of implementing reflections.