2
$\begingroup$

Given two line segments $L1 = (P1, P2)$ and $L2 = (P2, P3)$, the width and height $(W, H)$ of a rectangle, and the angle between $L1$ and $L2$ $(\phi)$, how would I determine the point $Q$ on L1 such that the rectangle $(W, H)$ centered at $Q$ doesn't exceed L2? The diagram below shows an example of the setup.

enter image description here

EDIT: I am currently working on a solution, but since it is not complete yet I would like to hear people's input.

Taking the top-left corner of the box as point $P$, I create a triangle $Q, P2, P$. I can calculate all the internal angles of the triangle, and I know the length of line $PQ$ is $\sqrt{\left ( \frac{W}{2} \right )^2 + \left ( \frac{H}{2} \right )^2}$, therefore, I can use the sine rule to find the length of the line $QP2$, I'll call it $d$. From there, I can find point $Q$ by normalizing the vector from $P2$ to $P1$ and multiplying it by $d$. $Q = P2 + |P1 - P2| \cdot d$

I'm still not sure how to perform this for the lines being at any angle, since at the moment I'm taking $P$ to be the top-left corner of the box.

$\endgroup$
  • $\begingroup$ Tl;dr: what available information do you have on the line angle with the axis? Long version: for instance, do you have a coordinate systems, and the coordinates of the points $P1,P2,P3$? Even though you say the rectangle is axis-aligned, we need to exploit some information on the angle of the lines with respect to the axis, or it cannot be solved... Said differently, without that angle information, you could rotate lines $L1$ and $L2$ around, which would change the distance $QP2$. $\endgroup$ – N.Bach Jun 1 '17 at 16:44
  • $\begingroup$ @N.Bach Yes, I am using Euclidean coordinates and I have the (x, y) position for each $P1, P2, P3$ so I can also calculate the angle of the lines with respect to the axes. $\endgroup$ – Sarathi Hansen Jun 1 '17 at 17:54
  • $\begingroup$ The method described in your edit works. It's not too difficult to know what corner you have to work with, given you already know whether the rectangle is above/below your line (the position of $P1$ can help you there). If you want to program this, it's sufficient to make it work. $\endgroup$ – N.Bach Jun 1 '17 at 19:22
0
$\begingroup$

Solving this problem comes down to computing a bunch of intersections of pairs of lines, so it’s not really necessary to compute any angles or trigonometric functions of them explicitly.

It’s slightly more convenient to work with the half-lengths of the rectangle sides to eliminate stray factors of two in the calculations. If the center of the rectangle is at $C$, its corners are then at $C+(\pm w,\pm h)$. We can also place $P_2$ at the origin, which will simplify some of the arithmetic, but isn’t strictly necessary.

This solution proceeds by computing the intersections of lines parallel to $L_1=\overline{P_2P_1}$ with $L_2=\overline{P_2P_3}$. These lines pass through the corners of the rectangle that are on the same side of $L_1$ as $P_3$. The corresponding center position that’s farthest from $P_2$ (and on the correct side of it) is the solution.

I’ll use homogeneous coordinates because computing lines in the Euclidean plane and their intersections is straightforward with them. To review, a point with Cartesian coordinates $(x,y)$ has homogeneous coordinates $[wx,wy,w]$, where $w$ is any arbitrary non-zero scalar. Converting to homogeneous coordinates is accomplished by appending $1$ to the tuple, while converting back to Cartesian coordinates is a matter of dividing through by $w$. The line with the equation $ax+by+c=0$ can also be represented by the homogeneous triple $[a,b,c]$. With this representation, the line through two points is just their cross product, and the intersection of two lines is also their cross product. If the last coordinate of the point of intersection is $0$, then the lines intersect at infinity, i.e., they are parallel. There is a point at infinity for each direction that lines can have and it is often convenient to identify points at infinity with direction vectors. Finally, if $\mathbf p$ is a point and $\mathscr l$ a line, the dot product $\mathscr l\cdot\mathbf p$ is equal to the signed distance of $\mathbf p$ from $\mathscr l$, scaled by $\mathbf p_w$ and the length of $\mathscr l$’s normal, $[\mathscr l_x,\mathscr l_y,0]$.

We have the homogeneous coordinates of the three points $\mathbf p_1$, $\mathbf p_2$ and $\mathbf p_3$, along with the half-side lengths, $W$ and $H$ of the rectangle (I’m using capital letters to avoid confusion with the $w$-component of a homogeneous coordinate triple). The line along which the rectangle slides is then $\mathscr l=\mathbf p_2\times\mathbf p_1$, while $\mathscr m=\mathbf p_2\times\mathbf p_3$ is the constraint line. Compute $\mathscr l\cdot\mathbf p_3$: if this is negative, negate $\mathscr l$ so that the region of interest is on the “positive” side of this line. We’ll also need $\mathscr l$’s normal, $\mathbf n=[\mathscr l_x,\mathscr l_y,0]$.

Compute the four points $\mathbf v_i=\mathbf p_2+[\pm W,\pm H,0]$. These are the four corners of the rectangle when it’s centered at $\mathbf p_2$. Select those corners for which $\mathscr l\cdot\mathbf v_i\gt0$; these are the corners that are on the same side of $\mathscr l$ as $\mathbf p_3$. As the rectangle slides along $\mathscr l$, its corners move along lines parallel to this line. The track for $\mathbf v_i$ is $\mathscr l_i=\mathbf n+[0,0,-\mathbf n\cdot\mathbf v_i]$, i.e., replace the last component of $\mathscr l$ with $-\mathbf n\cdot\mathbf v_i$. The intersections of these lines with $\mathscr m$, $\mathbf q_i=\mathscr l_i\times\mathscr m$, are the points at which the corners collide with the constraint line. Normalize the homogeneous coordinates of these points by dividing through by their $w$-coordinates and subtract the appropriate corner offset to obtain the candidate center points $\mathbf c_i$. The winner is $\operatorname*{arg max}_{\mathbf c_i}\{\mathbf c_i\cdot(\mathbf p_1-\mathbf p_2)\}$.

The above computation is a solution for rays $\overrightarrow{P_2P_1}$ and $\overrightarrow{P_2P_3}$, but we’re not quite done yet. There’s also a minimum offset, which corresponds to the near edge of the rectangle butting up against $P_2$. I’ll leave it to you to work this out, but it can also be found by computing intersections of a line parallel to $\mathscr l$ with edges of the rectangle. Dealing with this will also handle the case when $\mathscr l$ coincides with a diagonal of the rectangle. Alternatively, you can take care of that situation by including corners for which $\mathscr l\cdot\mathbf v_i=0$ in the above computations. There’s one other nontrivial complication that I’ve ignored: if the line segment $P_2P_3$ is short enough, the center point calculated above might put the rectangle farther away than the end of that segment so that the rectangle isn’t touching it: there’s also a maximum possible offset that’s a result of the finite length of the constraining line segment. I’ll leave detecting this case and the necessary adjustments to you, too. Finally, the computed center point might be off the end of $P_2P_1$, but that’s easy to detect.

It’s not strictly necessary to reject the irrelevant corners before proceeding with the above calculations. It’s possible to bulk-process all four corners at once via various matrix operations and then discard the bad results when convenient, at any time before the $\operatorname{arg max}$ operation. The intersection computation in particular can be accomplished by multiplying the matrix of lines by the cross-product matrix $$\mathscr m_\times = \begin{bmatrix} 0 & -\mathscr m_w & \mathscr m_y \\ \mathscr m_w & 0 & -\mathscr m_x \\ -\mathscr m_y & \mathscr m_x & 0\end{bmatrix}.$$ This matrix-oriented approach might be more efficient (or at least more convenient) than processing variable-length lists of points and lines.

Note that this solution works equally well for a non-axis aligned rectangle. The only place where the assumption that the rectangle is axis-aligned is used is in generating its corner offsets. For a non-aligned rectangle, you can simply rotate these offsets by the appropriate amount. It’s also easier to compute the min/max offsets with an aligned rectangle, but again, those can be rotated into the correct orientation after computing them for the simpler case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.