# Quickest algorithm to intersect a line and a circular arc , using vectors where possible.

Assuming the line is given by two points $\textbf{a,b}$, and the circular arc by radius $r$ and its exponential coordinate interval $(\theta_0, \theta_1) \subset [0, 2\pi)$.

Let $\textbf{y} = \textbf{a} + t (\textbf{b} - \textbf{a})$ be the line's vector equation. An equation for the circle is $\textbf{x} \equiv \textbf{x}\cdot\textbf{x} = r^2$ and s:

$$\textbf{a}^2 + 2\textbf{a}\cdot(\textbf{b}-\textbf{a})t + (\textbf{b}-\textbf{a})^2 t^2 = r^2$$

And of course we can solve for $t$ with the quadratic formula. But how do we then determine whether the circular arc $\textbf{x}(t) = r e^{i t}, t \in (\theta_0, \theta_1)$ contains one possibly two $\textbf{y}(t)$ and what those points of intersection are?

What is the quickest way? And we cannot use complex numbers as that would mean creating a once-used datatype in my app.

• After finding $t$ using the quadratic formula (which can have none, one or two real solutions), evaluate $\mathbf y(t)$ and find the argument in $[0, 2\pi)$ and check whether it is contained in $(\theta_0, \theta_1)$. – Pratyush Sarkar Mar 15 '17 at 19:17
• @PratyushSarkar formula? – AbstractAlgebraLearner Mar 15 '17 at 19:18
• I gave a sketch for an algorithm which is pretty straightforward to implement if you are programming. There obviously isn't a single formula as there are multiple cases to consider but that's easy to do in a program. – Pratyush Sarkar Mar 15 '17 at 19:20

I'm cheating here since I know more about my app. :P

Feel free to create a more accurate answer with respect to the question, and I will accept it.

I only need to interesect with corners of a rounded rectangle (translated to origin for simplicity). The algorithm would go:

# q = (-1,-1), (1, 1), (-1, 1), or (1, -1)
A = line.p1();  B = line.p2()
V = b - a
a = dot2D(V, V)
b = 2*dot2D(A, V)
c = dot2D(A, A) - r*r
d = b*b - 4*a*c
if d < 0:
return []
d = sqrt(d)
a *= 2
t0 = (-b + d)/a
t1 = (-b - d)/a
y0 = A + V*t0
y1 = B + V*t1
q = QPointF(*q) * r
rect = rectFromTwoPoints(q, QPointF(0.0, 0.0))
intersects = []
if rect.contains(y0):
intersects.append(y0)
if rect.contains(y1):
intersects.append(y1)
return intersects

• Where do you check that you are looking for solutions $t \in [0,1]$ ? – Jean Marie Mar 15 '17 at 20:22
• I think you should provide a little accompanying picture, which should be logic for such applications (without taking you hours). – Jean Marie Mar 15 '17 at 20:37