Projection On Parallelogram

Question

In my research, I encountered the problem of finding the projection of any point on given parallelogram with the following properties :

1. If the point is in region 1, the projection should be vertex A.
2. If the point is in region 2, the projection should be on segment AB parallel to Y-axis.
3. If the point is in region 3, the projection should be vertex B.

And so on.

The equations of parallelogram sides are also given in the figure.

I am trying to find out a computational way to figure out this projection.

I tried to set up the problem as a minimum L1 distance to parallelogram from the given point. But, I realized that this is not the correct projection.

Can some one provide help on what would be the efficient computational way to figure out this kind of projection? I am totally new to this field - Any references are highly appreciated.

Thank you very much!

Answer 1

So, each couple of lines given by $$ b_{\,1,\,1} x + b_{\,1,\,2} y = \pm 1 $$ and $$ b_{\,2,\,1} x + b_{\,2,\,2} y = \pm 1 $$ denotes a couple of lines symmetrical wrt the origin.

The four lines defines a parallelogram centered at the origin.

The four vertices are given by $$ \left( {\matrix{ {A_{\,p,\,p} } & {A_{\,p,\,m} } & {A_{\,m,\,p} } & {A_{\,m,\,m} } \cr } } \right) \; : \; \left( {\matrix{ {b_{\,1,\,1} } & {b_{\,1,\,2} } \cr {b_{\,2,\,1} } & {b_{\,2,\,2} } \cr } } \right)\left( {\matrix{ x \cr y \cr } } \right) = \left( {\matrix{ 1 & 1 & { - 1} & { - 1} \cr 1 & { - 1} & 1 & { - 1} \cr } } \right) $$ i.e.: $$ \left( {\matrix{ {A_{\,p,\,p} } & {A_{\,p,\,m} } & {A_{\,m,\,p} } & {A_{\,m,\,m} } \cr } } \right) = \left( {\matrix{ {b_{\,1,\,1} } & {b_{\,1,\,2} } \cr {b_{\,2,\,1} } & {b_{\,2,\,2} } \cr } } \right)^{\, - \,1} \left( {\matrix{ 1 & 1 & { - 1} & { - 1} \cr 1 & { - 1} & 1 & { - 1} \cr } } \right) $$

If some of the $b$ values are negative the denomination of the A points will change with respect to that shown in the figure: it is better to rearrange the denominations as to match with that shown, i.e. lower, higher $x$, lower,higher $y$ coordinates.

Now, at each vertex attach three unitary vectors as shown.

Compute the projection of the vector $A_{p,m}P$ onto the unitary vectors $\bf x_{pm}$ and $\bf y_{pm}$ stemming from $A_{p,m}$. If both projections are positive, then the point P lies in the $90^\circ$ sector encompassed by those vectors and $P$ projects onto the vertex itself.
Repeat for the other vertices and check if both projections are positive.

If P is not in any of the sector above, then express the vector $A_{p,m}P$ in the reference system given by $\bf x_{pm}, \, \bf v_{pm}$. If the coordinates in that system are both positive, then $P$ projects on the edge $A_{pm}A_{pp}$, and its coordinate wrt $\bf v_{pm}$ gives the distance from the vertex $A_{pm}.

You can see that the reference system $\bf y_{pp}, \, \bf v_{pp}$ in $A_{pp}$ will cover the edge $A_{pp}A_{mp}$, and so on.
You can also see that $P$, if external to the parallelogram, can have both coordinates positive only in one of the four systems.

To translate the above into a computational algorithm we can proceed along the following lines.

a) Construct the matrix $$ {\bf B} = \left( {\matrix{ {b_{\,1,\,1} } & {b_{\,1,\,2} } \cr {b_{\,2,\,1} } & {b_{\,2,\,2} } \cr } } \right) $$ ensure that its determinant is non null and compute $\bf B^{-1}$.

b) Compute the four points A $$ \left( {\matrix{ {A_{\,p,\,p} } & {A_{\,p,\,m} } & {A_{\,m,\,p} } & {A_{\,m,\,m} } \cr } } \right) = {\bf B}^{\, - \,1} \left( {\matrix{ 1 & 1 & { - 1} & { - 1} \cr 1 & { - 1} & 1 & { - 1} \cr } } \right) $$

c) Rearrange points A
for instance by taking as pivot the point with minimal abscissa ($A_0$ in the sketch) and arranging the others according to the tangent of the angle that they form with the pivot (if $\Delta x = 0 \; \to \; \Delta x = \epsilon $);
re-name the suffixes to $(0,1,2,3)$ so that they increase along the perimeter (e.g. ACW).

d) Construct unit vectors $\bf u_n, \; v_n$
$$ \eqalign{ & {\bf v}_{\,n} = \overrightarrow {A_{\,n} A_{\,\left( {n + 1} \right)} } \mathop {\;/}\limits_{} \;\left| {\overrightarrow {A_{\,n} A_{\,\left( {n + 1} \right)} } } \right|\quad \left( {n\bmod 4} \right) \cr & {\bf u}_{\,n} = \left( {\matrix{ {\cos \left( {\left( {n - 2} \right)\pi /2} \right)} \cr {\sin \left( {\left( {n - 2} \right)\pi /2} \right)} \cr } } \right) \cr} $$

e) Allocate the point P in the corresponding sector
construct the two lists $$ L_{\,x} = \left[ {A_{\,n,\,x} ,P_{\,x} } \right]\quad L_{\,y} = \left[ {A_{\,n,\,y} ,P_{\,y} } \right] $$ and sort them in increasing order;

f) use the rank indices of P in the ordered lists to determine its position and projection
if (corner sector in $A_0$)
$P_{\,x} < A_{\,0,\,x} \; \wedge \;A_{\,0,\,y} < P_{\,y} $ then $P \to A_{\,0} $ exit;
elif (lateral sector below $A_0$)
$P_{\,x} < A_{\,1,\,x} \; \wedge \;A_{\,1,\,y} < P_{\,y} < A_{\,0,\,y} $ then
- take the matrix ${\bf V}_{\,0} = \left( {\matrix{ {{\bf u}_{\,0} } & {{\bf v}_{\,0} } \cr } } \right)$
- determine the coordinates of $P$ in that system $$ \left( {\matrix{ {P'_x } \cr {P'_y } \cr } } \right) = {\bf V}_{\,0} ^{\, - \,{\bf 1}} \;\left( {\matrix{ {P_x } \cr {P_y } \cr } } \right) $$ - if $P'_y<0 \; \to$ error;
- elif $P'_x<0 \; \to$ the point is internal to the p., $\to$ ?
- else $P\; \to \;A_{\,0} + P'_y {\bf v}_{\,0} $
elif
....
(continue with the same path for the other sectors)

Answer 2

In my solution $x_1, x_2$ are replaced by $x,y.$
The solution should be easy to code.

Assume the given straight lines are not horizontal neither vertical. In this case are all coefficients $b_{ij}\neq 0.$
From the coefficients $\pm 1$ in the equations follows that the parallelogram is centered in $O.$
Thus if $A(x_A,y_A), B(x_B,y_B),$ then necessarily $C(-x_A,-y_A), D(-x_B,-y_B).$

In the enclosed figure are the equations of the straight lines $\color{blue}{blue},$ and located across the corresponding line.

Each region is determined by a system of inequations written in black.

The input point $P(x,y)$ has to be transformed to an output $P'(X,Y).$ These new coordinates $X,Y$ are written in the corresponding region in $\color{red}{red}.$

Remark
If a pair of lines is horizontal or vertical (the product $\prod_{i,j=1,2} b_{ij}=0$ ), the above solution has to be modified, but is easier.