Quickest way to find a point at a certain distance on the angle bisector

Question

Here's the for reference. The objective is to find the point (xc,yc) when (x1,y1), (x2,y2), (x3,y3) and 'd' are known. My present approach is as follows.

Find the dot product of the lines described by the point pairs ((x1,y1) and (x2,y2)) and ((x2,y2) and (x3,y3)) to obtain the angle between the lines.

The projection of the angle-bisector on the line ((x1,y1) to (x2,y2)) results in a point (xa,ya). This point (xa,ya) can be solved by using two equations namely, one where the point lies on the line ((x1,y1) and (x2,y2)) and second where its distance from the point (x2,y2) is d*cos(theta/2). The same process is repeated for the point (xb,yb).

Once these are obtained, simultaneous equations are obtained for xc and yc by finding the dot product of the lines ((x2,y2) and (xc,yc)) and ((x2,y2) and (xa,ya)) which should equal d*cos(theta/2) and the process is repeated for (xb,yb). These simultaneous equations are then solved to obtain (xc,yc).

My question, is there any other alternative solution to this problem?

Answer 1

You could, for instance, construct the rhombus of which $C$ is the center: let $A$ on ray $P_2P_1$ and $B$ on ray $P_2P_3$ be constructed such that $$ P_2A=P_2B={d\over\cos\theta/2}. $$ Point $C$ is then the midpoint of $AB$. We have then: $$ C={d\over2\cos\theta/2}\left({P_3-P_2\over P_3P_2} +{P_1-P_2\over P_1P_2}\right)+P_2. $$

Answer 2

You could use basic vector algebra.

Let's consider the point $\vec{p}_2 = (x_2 ,\, y_2)$ the origin, and construct unit vectors $\hat{e}_A$ and $\hat{e}_B$ towards the points $\vec{p}_1 = (x_1 ,\, y_1)$ and $\vec{p}_3 = (x_3 ,\, y_3)$, respectively: $$\hat{e}_A = (x_A ,\, y_A) = \frac{\vec{p}_1 - \vec{p}_2}{\left\lVert \vec{p}_1 - \vec{p}_2 \right \rVert} \iff \begin{cases} x_A = \frac{x_1 - x_2}{\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }} \\ y_A = \frac{y_1 - y_2}{\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }} \end{cases}$$ $$\hat{e}_B = (x_B ,\, y_B) = \frac{\vec{p}_3 - \vec{p}_2}{\left\lVert \vec{p}_3 - \vec{p}_2 \right \rVert} \iff \begin{cases} x_B = \frac{x_3 - x_2}{\sqrt{ (x_3 - x_2)^2 + (y_3 - y_2)^2 }} \\ y_B = \frac{y_3 - y_2}{\sqrt{ (x_3 - x_2)^2 + (y_3 - y_2)^2 }} \end{cases}$$ Note that if $\vec{p}_1 = \vec{p}_2$ or $\vec{p}_2 = \vec{p}_3$, there is no angle at all.

 
If $\vec{p}_1$, $\vec{p}_2$, and $\vec{p}_3$ are not collinear, the bisector line passes through the midpoint between $\vec{p}_2 + \hat{e}_A$ and $\vec{p}_2 + \hat{e}_B$. The direction unit vector for the bisector line is $\hat{e}_L$, $$\hat{e}_L = ( x_L ,\, y_L ) = \frac{\hat{e}_A + \hat{e}_B}{\left\lVert \hat{e}_A + \hat{e}_B \right\rVert} \iff \begin{cases} x_L = \frac{x_A + x_B}{\sqrt{(x_A + x_B)^2 + (y_A + y_B)^2}} \\ y_L = \frac{y_A + y_B}{\sqrt{(x_A + x_B)^2 + (y_A + y_B)^2}} \end{cases}$$ and the desired point is $$\vec{c} = ( x_C ,\, y_C ) = \vec{p}_2 + d \, \hat{e}_L \iff \begin{cases} x_C = x_2 + d \, x_L \\ y_C = y_2 + d \, y_L \end{cases}$$

 
In a comment, amd pointed out that we can calculate $\vec{e}_L$, the unnormalized version of $\hat{e}_L$, $$\hat{e}_L = \frac{\vec{e}_L}{\left\lVert\vec{e}_L\right\rVert}$$ using multiplication instead of division. It turns out that this is a superior method, because it is robust even when $\vec{p}_1$ and/or $\vec{p}_3$ are close to $\vec{p}_2$; the earlier method above has issues with that because the denominator(s) are close to zero. In essence, we get the exact same final $\hat{e}_L$, if we compute $\vec{e}_L$ as $$\vec{e}_L = ( x_U ,\, y_U ) = \left\lVert \vec{p}_1 - \vec{p}_2 \right\rVert \left ( \vec{p}_3 - \vec{p}_2 \right ) + \left\lVert \vec{p}_3 - \vec{p}_2 \right\rVert \left ( \vec{p}_1 - \vec{p}_2 \right )$$ i.e. $$\begin{cases} x_U = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} ( x_3 - x_2 ) + \sqrt{(x_3 - x_1)^2 + (y_3 - y_1)^2} ( x_1 - x_2 ) \\ y_U = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} ( y_3 - y_2 ) + \sqrt{(x_3 - x_1)^2 + (y_3 - y_1)^2} ( y_1 - y_2 ) \end{cases}$$ The two methods are equivalent, because instead of unit vectors in this latter case, the summed vectors both have length $\left\lVert \vec{p}_1 - \vec{p}_2 \right\rVert \, \left\lVert \vec{p}_3 - \vec{p}_2 \right\rVert$. It does not matter what the length of the two vectors is, as long as they are the same; their sum is always on the bisector line.

 
If the three points are collinear, and $\hat{e}_A = \hat{e}_B$, both $\vec{p}_1$ and $\vec{p}_3$ are in the same direction from $\vec{p}_2$, and the angle is zero. In that case, the bisector is in that same direction, $$\vec{c} = ( x_C ,\, y_C ), \quad \begin{cases} x_C = x_2 + d \, x_A \\ y_C = y_2 + d \, y_A \end{cases}$$ However, as amd pointed out in a comment, the general case covers this case just fine, so you don't need to handle this case specially at all.

 
If the three points are collinear, and $\hat{e}_A = -\hat{e}_B$, point $(x_2 ,\, y_2)$ is on the line between $(x_1 ,\, y_1)$ and $(x_3 ,\, y_3)$, and we can get the desired point by rotating $\hat{e}_A$ (or $\hat{e}_B$) ninety degrees. Rotating $(x_A , y_A)$ counterclockwise yields $( -y_A , x_A )$, and clockwise $( y_A , -x_A )$. So, the two desired points are $$\vec{c} = ( x_C ,\, y_C ), \quad \begin{cases} x_C = x_2 - d \, y_A \\ y_C = y_2 + d \, x_A \end{cases} \text{ and } \begin{cases} x_C = x_2 + d \, y_A \\ y_C = y_2 - d \, x_A \end{cases}$$

 
Keeping temporary results (rather than recomputing them), the entire operation costs at most two conditional checks, 3 square roots, 3 divisions, 8 multiplications, and 19 additions or subtractions.

For numerical evaluation, you can examine $S = \sqrt{(x_A+x_B)^2 + (y_A+y_B)^2}$ (the divisor for $\hat{e}_L$) to determine whether the three points are collinear or not, for just one additional conditional check. In the first collinear case, $ 0 \le S \le \epsilon$ (but because $S \ge 0$, you only need to check if $S \le \epsilon$). In the second case, $2-\epsilon \le S \le 2$ (but you only need to check if $S \ge 2-\epsilon$). Here, $\epsilon$ represents the maximum allowed rounding error in the numerical values, and is typically something like $10^{-6} = 0.000001\,$ or smaller, depending on the precision of your numerical representation and the cumulative precision of the basic algebraic operations done. Similarly, examine the divisors of $\hat{e}_A$ and $\hat{e}_B$ (distances from $\vec{p}_2$ to $\vec{p}_1$ and $\vec{p}_3$, respectively) to determine whether the points are separate or not.