Hi I try to understand this problem. I have 4 numbers which describe laser.
$lx$, $ly$, $dx$, $dy$ where $lx, ly$ are starting position and $dx, dy$ are direction.
and next I have $n$ numbers of mirrors. then for every mirrors $x1, x2, y1, y2$ which describe position of mirrors.
for example
1 1 1 0
3
4.5 0.5 5.5 1.5
4 4 6 5
5.5 2.5 4.5 3.5
And I must designate count of mirrors bounces.
image for example
In this case only 1 and 3 mirrors
How can I way to do this?
You could go through these steps:
1) check which mirrors intersect the line representing the beam; if no mirror is intersected, exit;
2) for every intersected mirror, compute intersection point and its distance from beam starting point;
3) take that intersection point which is nearest to beam starting point (this will be the starting point of the reflected beam) and compute the direction of the reflected beam;
4) repeat from 1) with the reflected beam as new beam.
Steps 1) to 3) require standard knowledge of analytic geometry and can be done in several different ways: please ask in case you need further advice.
EDIT.
To check if a mirror with end points $P$ and $Q$ is intersected by the beam, you could for instance find the cartesian equation of the beam, in the form $f(x,y)=0$, and then compute $f(P)$ and $f(Q)$: the line representing the beam crosses segment $PQ$ if and only if $f(P)\cdot f(Q)<0$.
Then find the intersection between the beam line and line $PQ$. The direction of the reflected beam is then given by $$ 2{\vec d\cdot \vec m\over \vec m\cdot \vec m}\vec m-\vec d, $$ where $\vec d=(d_x,dy)$ is the direction vector of the incident beam, $\vec m=(x_P - x_Q, y_P - y_Q)$ is the vector joining the endpoints of the mirror and $\cdot$ is used for scalar product of vectors.
EXAMPLE.
I'll show this procedure for the data given in the question.
The equation of the line with starting point $(l_x,l_y)=(1,1)$ and direction $(d_x,d_y)=(1,0)$ is $f(x,y)=0$, where: $$ f(x,y)=(y-l_y)d_x-(x-l_x)d_y,\quad\hbox{that is:}\quad f(x,y)=y-1. $$
Let's compute $f(x_1,y_1)\cdot f(x_2,y_2)$ for all the mirrors having endpoints $(x_1,y_1)$ and $(x_2,y_2)$.
Mirror 1: $f(4.5, 0.5)\cdot f(5.5, 1.5)=-0.5\cdot0.5=-0.25$;
Mirror 2: $f(4, 4)\cdot f(6, 5)=3\cdot4=12$;
Mirror 3: $f(5.5, 2.5)\cdot f(4.5, 3.5)=1.5\cdot2.5=3.75$.
As you can see, only mirror 1 is intersected by the beam (negative result).
We can now compute the intersection point $(x_B,y_B)$ between the light beam and mirror 1: $$ \begin{align} x_B=&{d_y l_x x_1 - d_x l_y x_1 - d_y l_x x_2 + d_x l_y x_2 - d_x x_2 y_1 + d_x x_1 y_2\over d_y x_1 - d_y x_2 - d_x y_1 + d_x y_2}=5,\\ y_B=&{d_y l_x y_1 - d_x l_y y_1 - d_y x_2 y_1 - d_y l_x y_2 + d_x l_y y_2 + d_y x_1 y_2\over d_y x_1 - d_y x_2 - d_x y_1 + d_x y_2}=1. \end{align} $$
Finally, let's compute the direction vector of the reflected beam. The vector for the mirror is $\vec m=(x_2 - x_1, y_2 - y_1)=(1,1)$ and the direction vector of the incident beam is $\vec d=(d_x,dy)=(1,0)$. The direction vector of the reflected beam is then: $$ 2{\vec d\cdot \vec m\over \vec m\cdot \vec m}\vec m-\vec d=(0,1). $$
Now you must repeat the whole process but with a beam starting at $(5,1)$ and with direction vector $(0,1)$. You'll find that mirrors 2 and 3 are both intersected by the new beam line (mirror 1 of course mustn't be included) at points $(5, 4.5)$ and $(5,3)$ respectively. This second point is nearer to the start point of the beam, so the reflection takes place on mirror 3, and you can compute the direction of the reflected beam as explained above.
You have several problems to solve each time the beam is reflected.
I like to use vectors to solve problems like these. All vectors in this problem have just two coordinates. You will need to know how to add two vectors, how to subtract one vector from another, how to take the scalar product of a number and a vector, and how to take the inner product (also call "dot product") of two vectors. That is, if $u = (u_x, u_y)$ and $v = (v_x, v_y)$ are two vectors and $r$ is a number, \begin{align} u + v &= (u_x + v_x, u_y + v_y), \\ u - v &= (u_x - v_x, u_y - v_y), \\ rv &= (rv_x, rv_y), \\ u \cdot v &= u_x v_x + u_y v_y. \end{align}
I assume you are given the starting point $p = (p_x,p_y)$ and a direction vector $v = (v_x, v_y)$ for the light ray. (Based on your input file and diagram, $p_x,p_y,v_x,v_y,$ in that order, appear to be the four numbers on the first line of the input.)
Construct another vector $w$ perpendicular to $v.$ One way to do that is to swap the $x$ and $y$ coordinates and then change the sign of one coordinate; for example you can set $w = (-v_y,v_x).$
We will also treat positions as vectors. You can think of a "position vector" as the vector that gives the distance and direction from $(0,0)$ to a point, or you can just treat the coordinates of the point as if they were coordinates of a vector.
Given a mirror with endpoints at $a = (a_x,a_y)$ and $b = (b_x,b_y),$ construct the vectors that show the distance and direction from the starting point of the light ray to the endpoints of the mirrors. These vectors are the vector differences $a - p$ and $b - p.$
Take the dot product of each of the last two vectors with the vector $w$: \begin{align} r_a &= (a - p) \cdot w, \\ r_b &= (b - p) \cdot w. \end{align} If the signs of $r_a$ and $r_b$ are the same (both positive or both negative), the light ray cannot intersect the mirror.
If the signs of $r_a$ and $r_b$ are opposite (one is positive, one is negative), then the light ray might reflect off the mirror. There are several ways to try to find out if it actually does reflect, but you might as well use the method that computes the possible point of intersection.
The reflection point, that is, the point where the light ray would hit the mirror (if it hits it at all) is at the position vector $$ p' = \left(\frac{r_b}{r_b - r_a}\right) a - \left(\frac{r_a}{r_b - r_a} \right) b. $$ The distance and direction of $p'$ from $p$ is $p' - p.$ Take the dot product of this with the direction vector of the light ray: $$ d = (p' - p) \cdot v. $$ The number $d$ is a kind of measurement of the distance of the reflection point from the starting point of the light ray. If it is positive, the light ray is going toward the mirror; if negative, the light ray is going away from the mirror.
For each mirror, follow the procedure to find where the beam of light would intersect it. Ignore the mirror if you find that $r_a$ and $r_b$ have the same sign or if $d$ is negative. The mirror with the smallest positive value of $d$ is the one the light ray will reflect from.
Of course if you do not find any mirror with a positive value of $d,$ there is no reflection.
You now have a new starting point for the reflected light ray: it is the position vector $p'$ where the incoming light ray intersected the mirror.
One way to find the direction of the reflected ray is as follows. Given the mirror's endpoints, $a$ and $b,$ construct a vector $m= (m_x, m_y)$ that gives the direction and length of the mirror's surface: $$ m = b - a. $$ Construct a second vector $n = (n_x, n_y)$ perpendicular (normal) to the mirror: $$ n = (-m_y, m_x). $$ Take the dot product of each of these vectors with the vector $v,$ divided by the dot product of $m$ with itself; this gives you a number by which you multiply each vector to obtain two new vectors, like this: \begin{align} m' &= \left(\frac{v \cdot m}{m\cdot m}\right) m, \\ n' &= \left(\frac{v \cdot n}{m\cdot m}\right) n. \end{align} (You can use $n\cdot n$ instead of $m\cdot m$ if you like; they are the same number.)
The vectors $m'$ and $n'$ are components of the vector $v$ parallel to the mirror and perpendicular to it. That is, they add up to the original vector: $v = m' + n'.$ To get the direction of the reflected ray, you reverse the component of the light ray's direction that is perpendicular to the mirror: the new direction vector is $$ v' = m' - n'.$$
Now you have a starting position $p'$ and a direction $v'$ of the reflected ray; repeat the procedure from the step "find where the beam of light might intersect a particular mirror" until there are no more reflections.
In the procedure above, I have tried to describe what each new position or vector is so that when you are debugging your program, you can check the steps one at a time to verify that they are producing the results they should. If there is a mistake in my explanation or an error in your implementation of it, you will be able to identify exactly which part of the algorithm was wrong.
Here is a commented Matlab program I have done and 3 examples of figures showing beams with multiple reflections generated by it (the third one being with around 250 mirrors arranged along an elliptical curve to which there are approximating segments).
I imagine that Matlab "idiosyncrasies" will not be a too big problem for a C++ adept as you are.
I would like to underline 3 essential steps in this program (I am ready to give more information on demand), with the following notations:
$B=\binom{x_B}{y_B}$ $E=\binom{x_E}{y_E}$ for the Beginning and Endpoints of the mirror under study, $J$ for the impact point on this mirror, $I(x_I,y_I)$ for the previous impact point, and $\binom{dxi}{dyi}$ the unit directing vector of $IJ$.
Here are these 3 steps:
1) The computation of the (unit) directing vector $\binom{dxo}{dyo}$ of the new ray, by first getting the normalized directing vector of the mirror : $\vec{D_1}:=\vec{D}/\|\vec{D}\|$ with $\vec{D}=\binom{x_E-x_B}{y_E-y_B}$; then by expressing the symmetry matrix with respect to this mirror under the so called Householder form $M=I_2-2D_1D_1^T$ (https://en.wikipedia.org/wiki/Householder_transformation), and at last, by getting the directing vector under the form: $\binom{dxo}{dyo}=-M*\binom{dxi}{dyi}$, with an essential minus sign in order to proceed in the right direction.
2) The computation of the length $A$ of the line segment $IJ$ between the previous impact point $I (x_I,y_I)$ and impact point $J$ on line BE. This computation uses as well a linear algebra tool, i.e., determinants. It suffices to express the alignment of points $B,J,E$ under the following classical alignment condition:
$$\tag{1} \begin{vmatrix}x_B&x_J&x_E\\y_B&y_J&y_E\\1&1&1\end{vmatrix}=\begin{vmatrix}x_B&(x_{I}+A.dxi)&x_E\\y_B&(y_{I}+A.dyi)&y_E\\1&1&1\end{vmatrix}=0,$$
For this condition, see for example (http://mathworld.wolfram.com/Collinear.html).
From (1), we can deduce an expression for $A$ that can be found in the program. Moreover, impact point $J$ must not only be on line BE but inside line segment $[BE]$; this is expressed by the positivity of $d$ which is a product of determinants.
Remark: The very good text of @David K has the same lines of thought, with a trend to use matrix/vectors in an essential way.
Matlab program:
function allmirrors;
clear all;close all,hold on;axis equal;
Lx=0;Ly=0;plot(Lx,Ly,'*b'); % origin;
dx=rand;dy=rand; % initial direction
% list of mirror endpoints (here a dodecagon);
w=pi/6;r=(1:12)'; M(r,:)=[cos(r*w),sin(r*w),cos((r+1)*w),sin((r+1)*w)];
nbm=size(M,1); % number of mirrors
M=M+0.2*rand(nbm,4); % small perturbation
for k=1:nbm
plot(M(k,[1,3]),M(k,[2,4]),'k','linesmoothing','on');
end;
A=1000;
Imx=[Lx];Imy=[Ly];
curk=0; % current mirror number on which the ray bumps
h=0; % h = number of rays till now
while A>0.001 && h<100
% depth buffer technique in case there is more than one candidate mirror:
Amini=1000;
for k=1:nbm;
if k ~= curk
[Lxo,Lyo,dxo,dyo,A1]=mirror(k,Lx,Ly,dx,dy,M);
if A1>0 && A1<Amini
Amini=A1;
indi=k;
end; %of internal if
end; %of external if
end;% of for loop
if Amini<999
[Lx,Ly,dx,dy,A]=mirror(indi,Lx,Ly,dx,dy,M);
Imx=[Imx,Lx];Imy=[Imy,Ly];
h=h+1;
curk=indi;
else
A=-1;
end;
end; % while
plot(Imx,Imy,'b','linesmoothing','on'); % all the light path
quiver([Lx,Lxo],[Ly,Lyo],[dx,dxo],[dy,dyo],1); % last arrow
%%%%%%%
function [Lxo,Lyo,dxo,dyo,A]=mirror(k,Lxi,Lyi,dxi,dyi,M);
% letters i and o for input and output rays
Lxo=0;Lyo=0;dxo=0;dyo=0;A=0;
x1=M(k,1);x2=M(k,3);y1=M(k,2);y2=M(k,4);
u1=x1-Lxi;v1=y1-Lyi;
u2=x2-Lxi;v2=y2-Lyi;
p=det([u1,v1;dxi,dyi])*det([dxi,dyi;u2,v2]);
% p>0 iff ray hits mirror
A=(u1*v2 - u2*v1)/(dyi*u1 - dyi*u2 - dxi*v1 + dxi*v2) ; % length of ray
if p>0 && A>0
Lxo=Lxi+A*dxi;Lyo=Lyi+A*dyi;
N=[x2-x1;y2-y1];N=N/norm(N);
V=-(eye(2)-2*N*N')*[dxi;dyi]; % symmetry matrix applied to input vector
dxo=V(1);dyo=V(2);
else
A=-1; % then exit from the while loop
end; % if
So basically i responded to this question earlier wondering whether the function/script provided by Jean Marie (once more, all credit to him) could be used such that multiple rays of light can be plotted in one mirror space, effectively making for a point source or beam source of light.
Now, after some puzzling i have found a way to do this. By making a matlab script that calls in this function while importing a new set of variables on each run of the function (using a for loop) this result can be obtained. See the code provided below.
The original function "allmirrors" as provided by Jean marie has to be edited slightly to let this work, but only very slightly. The things that need to be changed here are the following:
P.S. The credit for this function allmirrors still fully goes to mr Jean Marie! I do not intend to take any of that away, i am only trying to add the function of plotting multi-light sources. P.P.S. I am writing this since i had asked a question about this earlier. I think it is a shame that comment got removed, but i am posting my solution to the problem nonetheless. I hope someone else can use this, so i would like if this comment could be posted :)
clear all
close all
clc
M=[0 0 1 1];
figure
hold on
for i=1:1;
Lx=i;
for j=1:9;
Ly=i;
for a=1:1;
dx=i;
for b=1:1;
dy=i;
save('workspacevars')
allmirrors
end
end
end
end
hold off
