1
$\begingroup$

I am trying to understand the source code of a small program. There is a function I am not able to understand. I know what the function does, but I don't understand how it works.

This function is about finding the size of the blue line segment :

Figure of the problem

Special case of the problem?

What we know:

  • The size of the red line. ( first input of the function )
  • The cosine of the angle between the red and purle lines. ( second input )
  • The size of the yellow line ( the blue circle radius )
  • The radius of the green circle.
  • The purple and the blue lines are parallel.

The two radii are constants.

We want to find the size of the blue line, which starts at the D point to the point G.

In case you are interested by the function, r is the size of the red line, mu is the cosine of the angle between the red and the purple lines.

float limit(float r, float mu) {
    float dout = -r * mu + sqrt(r * r * (mu * mu - 1.0) + RL * RL);
    float delta2 = r * r * (mu * mu - 1.0) + Rg * Rg;
    if (delta2 >= 0.0) {
        float din = -r * mu - sqrt(delta2);
        if (din >= 0.0) {
            dout = min(dout, din);
        }
    }
    return dout;
}

So I am interested in several things here:

  • I'd like to understand how the function works. So if you have any tips about what it does, it would be helpful.
  • Another solution to solve that line segment for any cosine angle, in case I am not able to understand the function.
$\endgroup$
1
$\begingroup$

The cosine formula applies to triangle $\triangle ADG$ as follows, where $r=AD$, $d = DG$, $R_L = AG$, and $\theta = \angle ADG$: $$ R_L^2 = d^2 + r^2 - 2dr\cos\theta. $$

But $\cos\theta = -\mu$, because $\mu$ (mu in the software function) is the cosine of an angle that is the supplement of $\theta$. (That is, $\mu$ is the cosine of the exterior angle at $D$ in $\triangle ADG$, whereas $\theta$ is the interior angle at $D$.) So \begin{align} R_L^2 &= d^2 + r^2 + 2dr\mu \\ &= d^2 + 2dr\mu + r^2\mu^2 + r^2(1 - \mu^2) \\ &= (d + r\mu)^2 - r^2(\mu^2 - 1), \\ r^2(\mu^2 - 1) + R_L^2 &= (d + r\mu)^2. \tag1 \end{align}

Since the two sides of the last equation are equal, so are their square roots, and since $d + r\mu$ is positive, it is the square root of $(d + r\mu)^2.$ That is,

\begin{align} \sqrt{r^2(\mu^2 - 1) + R_L^2} &= d + r\mu \\ -r\mu + \sqrt{r^2(\mu^2 - 1) + R_L^2} &= d , \end{align}

so $d$ is dout in the statement dout = -r * mu + sqrt(r * r * (mu * mu - 1.0) + RL * RL). So we see that this statement in the function is just the cosine formula in disguise.

Next, we observe that $\mu^2 - 1 = \cos^2\theta - 1 = -\sin^2\theta,$ so using $\Delta_2$ for delta2 the next line of the function says that

\begin{align} \Delta_2 &= r^2(\mu^2 - 1) + R_g^2 \\ &= R_g^2 - (r\sin\theta)^2. \end{align}

Since $r\sin\theta$ is the distance from $A$ to the line $DG$, we know the line $DG$ will intersect the green circle if and only if $\Delta_2 \geq 0$. If the line does intersect the circle, the software function next sets \begin{align} d' &= -r\mu - \sqrt{\Delta_2} \\ &= -r\mu - \sqrt{r^2(\mu^2 - 1) + R_g^2}. \end{align}

Notice that this is much like the first statement in the software function, but $R_L$ has been replaced by $R_g$ and we are subtracting the square root rather than adding it. In fact, the last equation is equivalent to $$ \sqrt{r^2(\mu^2 - 1) + R_g^2} = -(d' + r\mu). \tag2 $$

Squaring both sides, we have $$ r^2(\mu^2 - 1) + R_g^2 = (d' + r\mu)^2, $$ which is just like Equation $1$ (above) except that $R_L$ has been replaced by $R_g$. So $d' = DP$ where $AP=R_g$ (so $P$ is on the green circle) and $\angle ADP = \angle ADG$ (so $P$ is on the line $DG$).

In other words, $d'$ is the distance from $D$ to one of the intersections of $DG$ with the green circle. But notice that Equation $2$ is possible only if $d' + r\mu \leq 0$, that is, if $\mu < 0$ (which it is, in the figures given as examples) and if $d' \leq \lvert r\mu \rvert.$ What this means is that in the "special case" figure, $d'$ is the distance from $D$ to the "first" intersection of the line $DG$ with the green circle, that is, the intersection nearest to $D$.

If $d' \geq 0$, the function then returns the smaller of $d$ and $d'$. If you've been paying careful attention, you may notice that this will always be $d'$, because $d'\leq -r\mu \leq d$. (Whoever wrote the function apparently did so without paying attention, in addition to neglecting their duty to document the code.)

The case $d' < 0$ occurs when $D$ is inside the green circle, meaning $d'$ identifies the intersection on the opposite side of $D$ from $G$. In that case, the function will return $d$, the distance $DG$ to the light blue circle, even if the segment $DG$ passes through the green circle's circumference first. If you wanted the function to give the distance to the first intersection with either the green or blue circles' circumferences, when $d' < 0$ the function should return $$ \min\{d, -r\mu + \sqrt{\Delta_2}\}. $$ This is where the min function might be required; notice that this is not how the min function is called in the function as written, because $d ' = -r\mu - \sqrt{\Delta_2} \neq -r\mu + \sqrt{\Delta_2}.$

$\endgroup$
  • $\begingroup$ Great answer, thanks! Tbh, now that I understand the function, the comparison with d' and the min call seems nonsense to me, because the context doesn't allow r <= Rg, so d' will always be positive. I will try to compare both with and without, maybe some weird cases forced them to do that. Thank you again for your time! $\endgroup$ – Aulaulz Jan 5 '17 at 12:26
  • $\begingroup$ As you've just observed, the formula to use depends on the assumptions/requirements: indeed, if we know that $r>R_g$ always, then the function can be simpler than it would be if we didn't know that. Conversely, if it is possible for $D$ to be outside of both circles and you want the first intersection with the blue circle, the distance to that intersection requires a calculation that isn't in the function as currently written (you have to subtract the square root instead of adding it). My answer assumed you only need to consider the "exit point" from the blue circle. $\endgroup$ – David K Jan 5 '17 at 13:31
  • $\begingroup$ r is clamped between Rg and RL. Thanks for clarifying. $\endgroup$ – Aulaulz Jan 5 '17 at 14:25

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.