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

Question

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.

Answer 1

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)
def lineIntersectCircleQuadrantAtO(line, r, q):
    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