1
$\begingroup$

First of all, sorry for the possibly crude formulation of the question. I suspect that there's a more sophisticated way but I simply lack the domain specific lingo. I hope it's understandable without too much annoyance.

Suppose that we have a convex hull and that B and C are two adjacent vertices of many. Suppose that we have a slope kb for a line through B. Suppose that we have a slope kc for a line through C. Given the information it's easy to compute the point X where the two lines intersect.

I'd like to compute the angle BXC. It's easy in most cases by creating the vectors BX and CX applying the formula:

arccos( BX dot CX / |BX| * |CX| )

The problem occurs when the intersection point X is the same as the vertex C. In such case, I need another point on the line through C, because the vector CX then is just the origin , i.e. (0,0). Obtaining such points is trivial because we only need to put in different values for t in the formula of the line, kc t + mc.

The issue I can't resolve is how to pick such a value. It can be t < C.x but also t > C.x and depending on which I pick, the angle computed will be different. I need to pick t in such a way so that the second point on the c-line is clockwisely further away from B than C is. How do I do that?

I've tried to relate the t to the other points, to the coordinates of B, the point D after C etc. There seems to always be a case where it stops working though so I'm guessing that I need a push in right direction on how to reason here.

It's worth keeping in mind that the slopes kb and kc don't align with the sides of the convex hull and may be or not be parallel to any edge of it. They do tangent the vertices, though.

$\endgroup$
1
$\begingroup$

It looks like you want to measure the angle between $\vec{XB}=\vec{CB}$ and the second line (the one that doesn’t pass through $B$) in a clockwise direction in this “degenerate” case. As you’ve noted, this comes down to choosing a $t$ with the correct sign to produce a point $C'=C+t(1,k_c)$. You can use the “two-dimensional cross product” for this.

For vectors $\mathbf v$ and $\mathbf w$, compute $\|\mathbf v\|\,\|\mathbf w\|\sin\theta=v_xw_y-v_yw_x$ and examine its sign: if positive, then a counterclockwise rotation takes $\mathbf v$ onto $\mathbf w$; if negative, the rotation is clockwise. For your problem, take $\mathbf v=B-C$ and $\mathbf w=(1,k_c)$, the direction vector of the second line. If this is negative, then a positive value of $t$ is called for; if positive, then you want a negative value for $t$.

$\endgroup$
2
  • $\begingroup$ Just to make sure that I understand the notation - I'm assuming that ||**v**|| means the length of the vector? I'm normalizing the 2D-cross-product there, right? $\endgroup$ – Konrad Viltersten Sep 21 '16 at 6:32
  • $\begingroup$ Yes, $\|\cdot\|$ stands for vector norm, but there’s no need to actually normalize the cross product for this as you’re only interested in its sign. That’s determined by the sine of the angle between the vectors, since it’s the only part of the expression that can be non-negative. $\endgroup$ – amd Sep 21 '16 at 7:33

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.