Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Is there any reason you're not simply calculating the tangent lines from the one circle to the other? –  Mark Ping May 31 '13 at 21:10
    
It seems to me that your sample code just tests whether either of the endpoints of the line segment are inside the circle. But both endpoints could be outside, and the line segment might enter and then exit the circle, no? –  Jyrki Lahtonen May 31 '13 at 21:14
    
@Mark Ping- The powerpoint shapes have anchors that I want to connect to, even if they aren't the perfect tangents. That allows me to move the shapes manually and the lines will adjust automagically. If I used tangents then I'd need to manually adjust those as well. The key is to find anchor-to-anchor connectors that are just shorter than the tangent on each side :) –  Keith May 31 '13 at 21:17
    
@Jurki Lahtonen That may be true, it was a sample I picked up that someone else created in VBA. Both endpoints will definitely be outside, and the question is whether (each) enters and exits, you are correct –  Keith May 31 '13 at 21:18
    
off topic comment: I thought you were calling me. –  newbie May 31 '13 at 22:38

2 Answers 2

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$.

share|improve this answer

Let's name your segment $[A,B]$, $C$ the center of your circle and $R$ it radius. $d=\sqrt{(Bx-Ax)^2 + (By-Ay)^2}$ is the distance between the two points.

First you get the point that is the nearest of C, in $(A,B)$. This point, M, has coordinates $Ax + (Bx-Ax)\ \alpha$ and $Ay + (By-Ay)\ \alpha$ , where $\alpha=\frac{1}{d^2}\left((Bx-Ax)\ (Cx-Ax) + (By-Ay)\ (Cy-Ay) \right)$ is the distance between A and B. This is just $\overrightarrow{AM}=\left( \frac{\overrightarrow{AB}}{AB} \cdot\overrightarrow{AC}\right) \frac{\overrightarrow{AB}}{AB}$

Then you check if this point is in the circle. If $|MC|=\sqrt{((Cx-Mx)^2+(Cy-My)^2)}>R$, the circle and the line doesn't intersect, so the circle and the segment doesn't intersect.

If $|MC| \leq R$, you have to check if M is in the segment, ie if $|MA| \leq d$ and $|MB| \leq d$. If it is true, the circle and the line intersect.

If $|MC| \leq R$ but M is not in the segment, you just have to check if $|AC| \leq R$ or $|BC| \leq R$. If it is true, the segment and the circle intersect. If is is false, they do not intersect.

share|improve this answer
    
This is almost down to my low level of understanding- thank you for spelling out all of the equations. |MC| signifies the distance between M and C? If so then I understand what MA and MB stands for, but I need to work out the math to understand what it is doing. I don't know what Ror or R$ stand for? This is the closest yet to my level of understanding, I appreciate any further help! –  Keith May 31 '13 at 21:47
    
Yes $|MC|$ is the distance between M and C. It is also commonly writen just $MC$. R is the radius of the circle. R$ is a mispelling ;) –  oao May 31 '13 at 21:59
    
I've converted the formulas to the following code, but I'm getting 100% of the results indicating that there is an intersect (even though I know there should be a handful without). I know this is a less familiar format, but if you notice any errors on my part, please let me know. –  Keith May 31 '13 at 22:19
    
I will append to original post, the comments are too small to accept the code –  Keith May 31 '13 at 22:21
    
Oops, error on my part- it is 100% returned without intersect (I thought it was the reverse) –  Keith May 31 '13 at 22:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.