[Math] Newbie: determine if line segment intersects circle

circlesgeometry

I've read related posts, including:

How to tell if a line segment intersects with a circle?
where the suggestions are probably relevant, but above my level, and the final solution is actually not what I need, and

Circle and Line segment intersection
Which may be what I need, but assumes more math knowledge than is in my brain.

Context: I have two circles in powerpoint, each of which have 8 points (anchors) on the perimeter. I am cycling through all 64 combinations in VBA to identify which two lines provide the longest point-to-point connectors that do not go through either circle. For convenience, I can check each line against each circle separately.

Basically, I am trying to create code that will allow me to automatically create something like this http://www.harrisgolfonline.com/userfiles/image/wlcc%201932%20bylaws%20callout.jpg except I'll also have a small circle around the enlarged part of the original image. I'm trying to get the math to figure out which circle anchors will give me those two outer lines.

So for example, if I draw the shortest possible line segment between the two closest connectors, I should not intersect with either circle. A line between the furthest away connectors would have to travel through both circles, and therefore fail either circle test.

Anyway, I'm hoping someone can help me with the equation setup, since the two pages I reference put in multiple equations and then say "then just solve it". I'm not exactly sure how to combine those formulas to solve. What I'm hoping for is something more like this equation, except this evaluates based on the whole line and not just a line segment:

Private Function LineCrossesCircle(x1, y1, x2, y2, cx, cy, cr) As Boolean

x1 = x1 - cx

y1 = y1 - cy

x2 = x2 - cx

y2 = y2 - cy

LineCrossesCircle = 0 <= cr ^ 2 * ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) - (x1 * y2 - x2 * y1) ^ 2

End Function

Reading the answers, I do understand that there may be multiple conditions, e.g. it may be something similar to the above AND some other equation or two.

My connector points will always be on the circumference of the circle, so I was adjusting my calculated radius value to be [r*.95] otherwise they might all intersect at the endpoints. That means that my endpoints will never fall within the circles, but part of the line will fall in one or both circles probably 80% of the time. Once I find the lines that don't, I can check their lengths and add them as connectors.

Any help translating the previous solutions into one or more equations that just take the two endpoints (x1, y1, x2, y2) and circle info (cx, cy, cr) and return a boolean for whether there is an intersect would be greatly appreciated!!

===================================================================================

Sample code based on OAO's helpful post. I think I got something wrong, because it is no connectors with intersects, when I know about 80% should have an intersect.

EDIT: updated the formulas for MA and MB (I had some of the elements reversed I think) but still showing no intersects

Private Function IntersectCheck(ByVal Cx As Single, _
                            ByVal Cy As Single, _
                            ByVal Radius As Single, _
                            ByVal Ax As Single, _
                            ByVal Ay As Single, _
                            ByVal Bx As Single, _
                            ByVal By As Single) As Boolean

'distance between endpoints

d = (((Bx – Ax) ^ 2) + ((By – Ay) ^ 2)) ^ 0.5

'not totally sure what this is

alpha = (1 / (d ^ 2)) * ((Bx – Ax) * (Cx – Ax) + (Bx – Ax) * (Cx – Ax))

'point nearest circle center

mx = Ax + ((Bx – Ax) * alpha)

my = Ay + ((By – Ay) * alpha)

MC = ((Cx – mx) ^ 2 + (Cy – my) ^ 2) ^ 0.5

MA = ((Ax – mx) ^ 2 + (Ay – my) ^ 2) ^ 0.5

MB = ((Bx – mx) ^ 2 + (By – my) ^ 2) ^ 0.5

AC = ((Cx – Ax) ^ 2 + (Cy – Ay) ^ 2) ^ 0.5

BC = ((Cx – Bx) ^ 2 + (Cy – By) ^ 2) ^ 0.5

IntersectCheck = False

If MC > Radius Then

'there is no intersect

Else

If (MA < d) And (MB < d) Then

    'there is an intersect

    IntersectCheck = True

Else

    If AC <= Radius Or BC <= Radius Then

        'there is an intersect

        IntersectCheck = True

    End If

End If

End If

End Function

Best Answer

Given the coordinates of two distinct points, represented by vectors of coordinates $v_p$ and $v_q$, the coordinate vectors of points on the line between them can be parameterized by $v(t) = tv_p + (1-t)v_q$, in which the $x$ and $y$ coordinates of $v(t)$ are linear functions of $t$. The squared distance from $v(t)$ to center of the circle is a quadratic function of $t$ with coefficients calculable from the given information, $At^2 + Bt + C$ with $A > 0$, and you want to know whether its minimum (which is the value when $t = -\frac{B}{2A}$) is less than or equal to $R^2$.

Related Solutions

Geometry – How to Tell if a Line Segment Intersects with a Circle?

Find the intersections of the line containing the segment and the circle. This amounts to solving a quadratic equation. If there are no intersections (i.e. the solutions of the corresponding equation are non-real), then your segment does not intersect the circle. Now, if there are intersections, see whether they are inside the segment or not.

To implement this, let $P$ and $Q$ be the endpoints of your segment and $C$ and $r$ be the center and the radius of your circle. Then every point of the line through $P$ and $Q$ is given by the formula $$t P + (1-t) Q$$ for exactly one value of $t\in\mathbb R$, and the points in the segment are precisely those for which the corresponding $t$ is in the interval $[0,1]$.

Now the point corresponding to $t\in\mathbb R$ is on the circle if and only if $$\langle t P + (1-t) Q - C,t P + (1-t) Q - C\rangle = r^2,$$ where $\langle\mathord\cdot,\mathord\cdot\rangle$ is the usual inner (dot) product of vectors. If you solve this equation—this is easy, as it is a quadratic equation for $t$—, you find the $t$'s corresponding to the points of intersection of the circle and the line, and if at least one of those $t$'s belong to the interval $[0,1]$, then the segment intersects the circle.

Later: I tried to have Mathematica do the computation for me. Assuming $C=(0,0)$ and $r=1$, as we may up to translation and rescaling, and letting $P=(p1,p2)$, $Q=(q1,q2)$, the following computes the $t$'s:

P = {p1, p2};
Q = {q1, q2};
ts = t /. Solve[Norm[t P + (1 - t) Q]^2 == 1, t];

This ends up with the variable ts having the value

$$\left\{\frac{-p_1 q_1-p_2 q_2-\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2},\frac{-p_1 q_1-p_2 q_2+\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}\right\}$$

(This was a huge formula, which will likely not fit on your browser window...) If the expression inside the square roots is negative, there are no real $t$'s, so the line (hence, a fortiori the segment) and the circle are disjoint. If not, now we need to see if at least one of the roots in in $[0,1]$.

If I now tell Mma to tell me when then first of the roots is in $[0,1]$, by telling her to compute

Reduce[0 <= ts[[1]] <= 1, Reals]

it works for a while, and comes up with a huge answer, presumably equivalent to the original

0 <= ts[[1]] <= 1

Can anyone make sense of the huge answer? (if one asks instead for the more meaningful

Reduce[0 <= ts[[1]] <= 1 || 0 <= ts[[2]] <= 1, t, Reals]

the same thing happens)

PS: Please notice that I have made absolutely no attempt at being fast or particularly smart with this idea: it is just the straightforward was to set up the problem and solve it.

[Math] Circle and Line segment intersection

The points $(x,y)$ on the line segment that joins $(x_1,y_1)$ and $(x_2,y_2)$ can be represented parametrically by $$x=tx_1+(1-t)x_2, \qquad y=ty_1+(1-t)y_2,$$ where $0\le t\le 1$. Substitute in the equation of the circle, solve the resulting quadratic for $t$. If $0\le t\le 1$ we have an intersection point, otherwise we don't. The value(s) of $t$ between $0$ and $1$ (if any) determine the intersection point(s).

If we want a simple yes/no answer, we can use the coefficients of the quadratic in $t$ to determine the answer without taking any square roots.

Best Answer

Related Solutions

Geometry – How to Tell if a Line Segment Intersects with a Circle?

[Math] Circle and Line segment intersection

Related Question