How can I calculate the point(s) where 2 circles cross

[opus]

I seem to be unable to tell this computer to calculate the crossing- points of circles. I have the centreposition and radius of the circles calculated, now I need to claculate the crossings.
I know I have to use to formula Radius=SQR( (x+CenterX)^2 +(y+Centery)^2). But whow would I do that in code??

I know I'm getting stupid, but........

[alkatran]

Take formula of circle #1:
(x - x')^2 + (y - y') ^2 = r'^2
and #2:
(x - x'')^2 + (y - y'') ^2 = r''^2

isolate Y:
y = sqr(r'^2 - (x - x')^2) + y'
y = sqr(r''^2 - (x - x'')^2) + y''

Combine:
sqr(r'^2 - (x - x')^2) + y' = sqr(r''^2 - (x - x'')^2) + y''

Rearrange:
sqr(r'^2 - (x - x')^2) - sqr(r''^2 - (x - x'')^2) = y'' - y'

Square the whole thing:
(sqr(r'^2 - (x - x')^2) - sqr(r''^2 - (x - x'')^2))^2 = (y'' - y')^2
for simplicity, a=sqr(r'^2 - (x - x')^2), b=sqr(r''^2 - (x - x'')^2)

Binomial expansion:
r'^2 - (x^2 - 2*x*x' + x'^2) + r''^2 - (x^2 - 2*x*x'' + x''^2)-2ab = (y''-y')^2

Simplify:
-2x^2 + 2x*(x'+x'') - 2ab = (y''-y')^2 - r'^2 - r''^2 + x'^2 + x''^2

For simplicity, (y''-y')^2 - r'^2 - r''^2 + x'^2 + x''^2=c
-2x^2 + 2x*(x'+x'') - 2ab = c
2x(x' + x'' - x) - 2ab = c

As you can see. It's kindof complicated. I probably messed up the logic somewhere though. I can't bother to go on!

[opus]

I figured out another way, forget the way using those circle formulas.

If two circles cross at any point, the distance between them has to be within.

Radius1+Radius2>= Distance>= Radius1-Radius2
(with Radius1>=Radius2!)

If they cross consider the connecting line from Centre1 to circle2 a one side of a triangle, the other sider are the radus1 and Radius2. So you've got 3 sides of a triangle, so you can calculate the angles of this triangle.

To calculate the crossing points just use the direction from Circle1 to Circle2, add/subtract the angle from the triangle in Centre1. This will give the direction to both (or to the one and only) crossingpoint. The distance is of course Radius 1.

That looks like a solution which I can easily put into code.

[krtxmrtz]

The easy approach for me consists in applying a transformation of coordinates, doing the calculation for a special case and rolling back the transformation.

For example, you can make a x,y shift such that the new coordinate origin is at the center of circle 1 (radius R) and next apply a rotation such that the center of circle 2 (radius r) lies on the positive x axis at a distance a from the origin. Then it's very straightforward to arrive at these coordinates for the points of intersection:

x(int) = +(R² + a² - r²) / 2a
y(int) = +/- Sqr(R² - x(int)²)

[Ecniv]

If they cross consider the connecting line from Centre1 to circle2 a one side of a triangle, the other sider are the radus1 and Radius2. So you've got 3 sides of a triangle, so you can calculate the angles of this triangle.

uhhh.

I've spent most of today looking at this (I have a piece of a4 with doodles of triangles and circles on it).

I can see how you get the distance from circleA to circleB, and using the radii as the other two sides of the triangle. However (and being its been a long time since I was at school) I cannot see how you would get the angles so easily...

Is there a formula I've forgotten?

[opus]

The quick (and dirty] answer is YES!

And since this is also true for me:

(and being its been a long time since I was at school)

I "googled" "Triangle SSS" and got:

How to solve a traingle with 3 sides given

[Ecniv]

Thanks that link helped.
Seems as I get older there is more crap and its harder to find the best search criteria

Right. So I've coded up the solving of the triangle woo.
Now to use that to find the proper position(s) of the cross points...

Looking at my sketched diagram, I uh cannot see any right angles :/
Christ, never knew I had forgotten maths so badly :/
Can you point me to another link for getting the co-ordinates.

I have a form (in Excel) which is accepting x1,y1, x2,y2 r1,r2 and hopefully will return one or two cross points of the circle (I don't want to look for more than that )

EDIT: I found it... second triangle angle added to the one I've just found can produce the co-ordinates

Lemme try and I'll post up again later

[Ecniv]

Ok hmm it ran - but I think its wrong.
x1 = 1
y1 = 1
r1 = 3
x2 = 5
y2 = 5
r2 = 4

What should the answer be?

Edit:
these are mine (after I used the right radius instead of the line between the points.
ResX1 = 3.997
ResY1 = 1.128
ResX2 = 1.128
ResY2 = 3.997

[Ecniv]

Right, something has gone wrong with it and I cannot even get those result I previously had.

I'm attaching the spreadsheet (up to you if you want to look and download).

Any flaws in my logic I would appreciate the pointers
* Note - the drawing part doesn't appearr to work right, which is one reason I think the values are wrong...

[opus]

You got some errors in the code,
I changed the ArcCos Function(some brackets) and you didn't check wether your point1 was left or right of point2, therefore your third point could be outside the desired triangle, I changed the code for you.

'---------
'----   NOTE: Sticking with  R A D I A N S  as the resulting angles!!
'---------
'---- Check for side one
    If blnDebug Then Debug.Print "Side 1"
    dblSideA = dblR2
    dblSideB = dblR1
    dblSideC = Sqr(((dblX1 - dblX2) ^ 2) + ((dblY1 - dblY2) ^ 2))
    dblAngleC = ((dblSideA ^ 2) + (dblSideB ^ 2) - (dblSideC ^ 2)) / (2 * dblSideA * dblSideB)
    If blnDebug Then
        Debug.Print "  Side A,B,C : " & dblSideA & " : " & dblSideB & " : " & Format(dblSideC, "#0.000")
'        Debug.Print "   Before arccos - AngleC : " & dblAngleC
    End If
    dblAngleC = ArcCosR(dblAngleC)
    
    dblAngleA = ((dblSideA * Sin(dblAngleC)) / dblSideC)
    dblAngleA = ArcSinR(dblAngleA)
    dblAngleB = DegToRad(180 - RadToDeg(dblAngleC) - RadToDeg(dblAngleA))
    
    If blnDebug Then
        Debug.Print "  Angles (R) A, B, C : " & Format(dblAngleA, "#0.00") & " : " & Format(dblAngleB, "#0.00") & " : " & Format(dblAngleC, "#0.00")
        Debug.Print "  Angles (D) A, B, C : " & Format(RadToDeg(dblAngleA), "#0.00") & " : " & Format(RadToDeg(dblAngleB), "#0.00") & " : " & Format(RadToDeg(dblAngleC), "#0.00")
    End If
    
    dblExternalAngle = RadToDeg(ArcSinR(dbly1y2Height / dblSideC))
    dblTemp = dblExternalAngle + RadToDeg(dblAngleA)
 [B]   'you have to check wether Point2 is to the left or right of Point1
    If dblX1 <= dblX2 Then
        txtResX1.Text = Format((Cos(DegToRad(dblTemp)) * dblR1) + dblX1, "#0.000")
        txtResY1.Text = Format((Sin(DegToRad(dblTemp)) * dblR1) + dblY1, "#0.000")
    Else
        txtResX1.Text = Format(-(Cos(DegToRad(dblTemp)) * dblR1) + dblX1, "#0.000")
        txtResY1.Text = Format(-(Sin(DegToRad(dblTemp)) * dblR1) + dblY1, "#0.000")
    End If[/B]
    
'---- Check for side two
    If blnDebug Then Debug.Print "Side 2"
    dblSideA = dblR1
    dblSideB = dblR2
    dblSideC = Sqr(((dblX1 - dblX2) ^ 2) + ((dblY1 - dblY2) ^ 2))
    dblAngleC = ((dblSideA ^ 2) + (dblSideB ^ 2) - (dblSideC ^ 2)) / (2 * dblSideA * dblSideB)
    If blnDebug Then
        Debug.Print "  Side A,B,C : " & dblSideA & " : " & dblSideB & " : " & Format(dblSideC, "#0.000")
'        Debug.Print "   Before arccos - AngleC : " & dblAngleC
    End If
    dblAngleC = ArcCosR(dblAngleC)
    
    dblAngleA = ((dblSideA * Sin(dblAngleC)) / dblSideC)
    dblAngleA = ArcSinR(dblAngleA)
    dblAngleB = DegToRad(180 - RadToDeg(dblAngleC) - RadToDeg(dblAngleA))
    
    If blnDebug Then
        Debug.Print "  Angles (R) A, B, C : " & Format(dblAngleA, "#0.00") & " : " & Format(dblAngleB, "#0.00") & " : " & Format(dblAngleC, "#0.00")
        Debug.Print "  Angles (D) A, B, C : " & Format(RadToDeg(dblAngleA), "#0.00") & " : " & Format(RadToDeg(dblAngleB), "#0.00") & " : " & Format(RadToDeg(dblAngleC), "#0.00")
    End If
    
    dblExternalAngle = RadToDeg(ArcSinR(dbly1y2Height / dblSideC))
    dblTemp = dblExternalAngle + RadToDeg(dblAngleA)
 [B]   If dblX1 <= dblX2 Then
        txtResX2.Text = Format(dblX2 - (Cos(DegToRad(dblTemp)) * dblR2), "#0.000")
        txtResY2.Text = Format(dblY2 - (Sin(DegToRad(dblTemp)) * dblR2), "#0.000")
    Else
        txtResX2.Text = Format(dblX2 + (Cos(DegToRad(dblTemp)) * dblR2), "#0.000")
        txtResY2.Text = Format(dblY2 + (Sin(DegToRad(dblTemp)) * dblR2), "#0.000")
    End If
   [/B]
    If Err.Number <> 0 Then
        MsgBox "Error : " & Err.Number & vbCrLf & Err.Description, vbOKOnly + vbInformation, "Error"
        txtResX1.Text = ""
        txtResY1.Text = ""
        txtResX2.Text = ""
        txtResY2.Text = ""
        lblresult.Caption = "Error"
    Else
        lblresult.Caption = "Complete"
    End If
    
End Sub

And

Public Function ArcCosR(ByVal dblX As Double) As Double
    On Error Resume Next
        'Changed some brackets!!
        ArcCosR = Atn(-dblX / Sqr(-dblX * dblX + 1)) + 2 * Atn(1)
End Function

I didn't look at your circle drawing!

[Ecniv]

Thanks for taking the time to check. I thought there was a problem with the +/- depending on the direction of the triangle.

However, it is still not working right, the calced values on
10,10,30
50,50,40

gives (as the crossing points):
13.341,39.813
38.240,11.768


But this internal triangle should give the exact opposites for the crossing points. I did a very rough sketch that appeared to prove this.

I'll look again at it, as I think one calc is messing up somewhere

**Edit:
Found it !!
Stupid brackets on the arccos were returning the wrong result. Fixed that.
Now on to the actual positions and drawing it

[Ecniv]

Hi,

An updated spreadsheet.
The test data I've used is in the top right, the green appears to work, only the red one doesn't (not sure why yet - but this means that there are more problems inside it).

Any advice?

Oh the direction thing (x1 to x2 etc) I got around and use a direction angle, which when past a certain point becomes a negative sin/cos... And works for all but the one test.

I'm gonna take a break from it and try again tomorrow probably.

[opus]

Sorry, but I can't open your file???

[Ecniv]

Weird...

Ok, here's an updated file and the final spreadsheet/code.
I tried uploading it before, but I guess it never made it (last workplace had a crap net connection after 10am...

[opus]

Still weird, but WindowsXP tells me it doesn'T "know" the method for kompressing.
I still can download and open the first .Zip file, but the last two i can't.
I'm so sorry...............................

[Ecniv]

Same here at the new work place - no winzip inistalled .. so perhaps that is why :/

I'll remove the zips and attach the xls. OR not... Ok rename the txt to xls and it should (in theory) work

[opus]

Hi,
I fixed some of the logics 8espacially the calculation of direction and of the angle.
you had lots of mixups with Radians and degree.
And you still have lots of variables that are not needed.

For the calculation of the Angle, I went the easy way, and just calculated one angle and used this one for both crossing points.

In the drawing I changed the Offset and the fact that you were adding the Y-Value, although VB "counts" Y the other way (downward is +!)

[Ecniv]

uh.. just typed in the top example circles and used the draw lines function (unless this is messed up) it doesn't draw right

opus results
257.130,8.333
142.870,8.333

my results
60.946,343.750
339.054,343.750

If you can prove that (a) my results are wrong and (b) that the drawing is also wrong, fair enough.

I am pretty sure I uploaded the correct version.

Those pesky Radians / Degrees

[opus]

Sorry, I messed up with the versions of your/my triangle file.
Here should be the correct one!

[Ecniv]

Thanks for that. Thought it was working ok - but I guess not huh
Well that was brain stretching.. time for some relaxing -----> Data entry - very little thought required