Algorithm for reflecting a point across a line

问题:

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

回答1:

Ok, I'm going to give you a cookbook method to do this. If you're interested in how I derived it, tell me and I'll explain it.

Given (x1, y1) and a line y = mx + c we want the point (x2, y2) reflected on the line.

Set d:= (x1 + (y1 - c)*m)/(1 + m^2)

Then x2 = 2*d - x1

and y2 = 2*d*m - y1 + 2*c

回答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.

回答3:

With reference to the fig in here.

We want to find the reflection of the point A(p,q) to line L1,eqn y = m*x + c. Say reflected point is A'(p',q')

Suppose, The line joining the points A and A' is L2 with eqn: y= m'*x + c' L1 & L2 intersect at M(a,b)

The algorithm for finding the reflection of the point is as follows: 1) Find slope of L2 is = -1/m , as L1 and L2 are perpendicular 2) Using the m' and A(x,y) find c' using eqn of L2 3) Find the intersection point 'M' of L1 anSd L2 4) As now we have coordinate of A and M so coordinate of A' can be easily obtained using the relation [ A(p,q)+A'(p',q') ]/2 = M(a,b)

I haven't checked the following code but the crude form of code in the FORTRAN is

SUBROUTINE REFLECTION(R,p,q)

IMPLICIT NONE

REAL,INTENT(IN)     ::  p,q

REAL, INTENT(OUT)   ::  R(2)

REAL                ::  M1,M2,C1,C2,a,b

M2=-1./M1                       ! CALCULATE THE SLOPE OF THE LINE L2 

C2=S(3,1)-M2*S(3,2)             ! CALCULATE THE 'C' OF THE LINE L2  

q= (M2*C1-M1*C2)/(M2-M1)        ! CALCULATE THE MID POINT O

p= (q-C1)/M1

R(1)=2*a-p                      ! GIVE BACK THE REFLECTION POINTS COORDINATE

R(2)=2*b-q

END SUBROUTINE REFLECTION

回答4:

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.

回答5:

I have a simpler and an easy way to implement in c++

#include<graphics.h>
#include<iostream>
#include<conio.h>
using namespace std;

int main(){
cout<<"Enter the point";
float x,y;
int gm,gd=DETECT;
initgraph(&gd,&gm,"C:\\TC\\BGI");

cin>>x;
cin>>y;
putpixel(x,y,RED);
cout<<"Enter the line slop and intercept";
float a,c;
cin>>a;
cin>>c;
float x1,y1;
x1 = x-((2*a*x+2*c-y)/(1+a*a))*a;
y1=(2*a*x+2*c-y)/(1+a*a);
cout<<"x = "<<x1;
cout<<"y = "<<y1;

putpixel(x1,y1,BLUE);
getch();

}

回答6:

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

回答7:

Reflection of point in the line Given point P(x,y) and a line L1 Then P(X,Y) is the reflected point on the line L1 If we join point P to P’ to get L2 then gradient of L2=1/m1 where m1 is gradient of L1 L1 and L2 are perpendicular to each other Get the point of intersection of L1 and L2 say m(a,b) Since m(a,b) is the midpoint of PP’ i.e. L2, then M=
i.e. = from this we can get coordinates of Example Find the image of point P(4,3) under a reflection in the line
M1=1 M2 will be -1 Equ. L2 with points, (4,3) , (x ,y) grad -1 is

Point of intersection say, M(a ,b) Note that, L1 =L2 ; Then This gives the point for M that is M( 6,1) Then;

          This gives x = 8 and y = -1 hence,

P'(x,y) = P'(8,-1)

回答8:

Reflection of point A(x,y) in the line y=mx+c.
Given point P(x,y) and a line L1 y=mx+c.
Then P(X,Y) is the reflected point on the line L1.
If we join point P to P’ to get L2 then gradient of L2=-1/m1 where m1 is gradient of L1.

  L1 and L2 are perpendicular to each other.
        therefore,
    Get the point of intersection of L1 and L2 say m(a,b)
    Since m(a,b) is the midpoint of PP’ i.e. L2, then
    M= (A+A')/2 
    i.e. m(a,b)=(A(x,y)+ A^' (x^',y^' ))/2.
      from this we can get coordinates of  A^' (x^',y^' )

Example

Find the image of point P(4,3) under a reflection in the line  y=x-5
M1=1
M2 will be -1
Equ. L2 with points, (4,3) , (x ,y) grad -1 is
     y=-x+7
Point of intersection say, M(a ,b)
 Note that, L1 =L2 ;
  Then x-5=-x+7
  This gives the point for M that is M( 6,1)
      Then;
         M(6,1)=(P(4,3)+P^' (x^',y^' ))/2
          M(6,1)=[(4+x)/2  ,(3+y)/2]
              This gives x = 8 and y = -1 hence,
                  P^' (x^',y^' )=         P^' (8,-1)

回答9:

Find slope of the given line. Say it is m. So the slope of line joining the point and its mirror image is -1/m. Use slope point form to find equation of the line and find its interaection with given line. Finally use the intersection point in midpoint formula to get the required point. Regards, Shashank Deshpande