I'm stuck into a control system problem with geometrical interpretation. I have a set of linear equations $Ax\leq b$ which form a convex hull (more precisely a parallelogram), where $A \in \mathbb{R}^{4\times2}$ and $x\in \mathbb{R}^2$.
At each iteration I obtain a random point $[x_1^*,x_2^*]$. I'm sure that this point is out of the region formed by the lines that are normal to the faces of the parallelogram and pass through its vertices, i.e. I'm sure that the point $[x_1^*,x_2^*]$ is inside one of the 4 regions formed by the lines orthogonal to the faces of the parallelogram (Regions R2,R4,R6 and R8 in the annexed Figure). My main problem is that I I need a fast(and efficient) way to find, at each iteration, the region in which the point $[x_1^*,x_2^*]$ is. Knowing this, I can calculate the closest point of the line (face of the parallelogram) to the point $[x_1^*,x_2^*]$, which will be the orthogonal projection of the point to the line.
My first idea was to find the points of the vertices(for example $[a_1,b_1],\ldots,[a_4,b_4]$) and use if statements such as: $$if (a_1\leq x_1^*\leq a_2) \quad and \quad(b_1\leq x_2^*\leq b_2)$$ to find in which region the point $[x_1^*,x_2^*]$ is.
Can you guys help me with this problem?
Thanks!
If $P$ is a point outside the quadrilateral and $A_i$ is vertex $i$ of the quadrilateral, then the projection of $P$ onto edge $i$ ($A_iA_{i+1}$) of the quadrilateral is $$ t_i = \frac{(P-A_i)\cdot (A_{i+1} - A_i)}{(A_{i+1}-A_i)\cdot (A_{i+1} - A_i)}. $$ The real number $t_i$ is the position of the the nearest point to $P$ (call it $Q$) on line segment $A_iA_{i+1}$. A value of $t_i=0$ means $Q=A_i$ and a value of $t_i=1$ means $Q=A_{i+1}$. A value of $t_i$ outside the unit interval means the nearest point to $P$ on the line through $A_i$ and $A_{i+1}$ is outside line segment $A_i A_{i+1}$.
Let $\hat{v}_i = (A_{i+1} - A_i) / |A_{i+1} - A_i|$ be the unit direction vector of edge $i$. If the vertices of the quadrilateral are in counter-clockwise orientation, then the outward pointing normal for edge $i$ is $\hat{v}_i$ rotated by -90 degrees about the $z$ axis or $\hat{n}_i = (\hat{v}_{iy}, -\hat{v}_{ix})$. The equation of the line containing edge $i$ can be written as $\hat{n}_i \cdot x + c_i = 0$ (where $c_i = -\hat{n}_i\cdot A_i$). The signed distance of a point $P$ from this line is $\hat{n}_i\cdot P + c_i$.
Using at most three projections and signed distance computations, you can find the region containing $P$. You know that $P$ is in the region outside edge $i$ if $0\le t_i \le 1$ and $\hat{n}_i \cdot P + c_i \ge 0$. If you compute all the quantities $\hat{n_i}$, $c_i$, and $(A_{i+1} - A_i) / (A_{i+1}-A_i) \cdot (A_{i+1}-A_i)$ "offline", the only computation you need to do "online" is at most 6 two-dimensional dot products.