Flexing my Brain: Find Your Centre

I've been meaning to do a post of this type this since I started this blog, hence the "coding" part of the URL. I not sure how this popped into my head, I was just doodling on some paper some paper and somehow came up with.

"If you have three points on the circumference of a circle how do you find the centre of that circle?"

Yes, I do ponder odd things at times. To solve this graphically its pretty simple.

Given points p₁,p₂,and p₃, construct two lines l₁and l₂ by connecting p₁ to p₂,and p₂ to p₃.
Find the centre point of each line m₁ and m₂.
From each of these points construct a line, perpendicular to the parent line and find the point intersection of these two new lines (l₃and l₄).
This point of intersection is the centre of the circle, from there you can calculate any and all other circular goodness you might need.

Click the image for a demonstratrion.

But then I thought, How would I implement this in code? yeah i do this often when im pondering about things.

Generally before you translate something into your programming language of choice, you must first translate it into the universal language, Mathematics.

To do this you need to know three equations;
how to get the midpoint of a line ( ( x₁ + x₁ ) / 2, ( y₁ + y₁ ) / 2 ),
how to get the equation of a line in the form  y = mx + b
and how to get the slope of a line m = ( p₁y - p₂y ) / ( p₁x - p₂x ).
These are the tools you need to get the job done.

First we find the mid points of lines l₁ and l₂, and call these m₁ and m₂
Then we get the slope of these lines, we need the line to be perpendicular so to that we need a new slope that is equal to -1/m (where m is the original slope). Now that we have a point and a new slope its simple to construct a line perpendicular to our original line in the form y = mx +b.

Now from this we have two new lines l₃ and l₄ and we need to find a point of intersection between these two. To do this we simply equate the two equations of y = mx + b and solve for x. Then subsitute our new value for x back into one of our line equations and solve for y. These two values for x and y are the point of intersection and by glorious hapenstance is the centre of our circle. That was a little dry so here follows a "real world" example:

Our equations are

l3: y = -x+6

l4: y = x - 4

So now we equate these and solve for x

x - 4= -x + 6

x + x = 6 +4

2x = 10

x = 5

Now with this value of x, we sub it back into our equation and we get

y = -(5) + 6

y = 1

There you have it point of intersection is x = 5, y = 1

Now to translate this into code. The midpoint, slope and perpendicular slope are pretty easy achieve.

The point of intersection while still simple took a little bit brain flexing, which now you dont have to do. 

m1x + b3 = m2x + b4
m1x - m2x = b4 - b3
x = (b4 - b3)/(m1-m2)

where;
m₁ and m₂ are the perpendicular slope of line l₁ and l₂
b₃ and b₄ are the constants of the equations of l₃ and l₄
note: I'm aware of the slight cheating of the math but trust me it works.


//Create Three Points on Circle
Point p1 = new Point( P1X, P1Y );
Point p2 = new Point( P2X, P2Y );
Point p3 = new Point( P3X, P3Y );
    
//Get MidPoint of l1
Point m1 = new Point( ( ( p1.x + p2.x ) / 2 ), ( ( p1.y + p2.y ) / 2 ) );
//Get MidPoint of l2
Point m2 = new Point( ( ( p2.x + p3.x ) / 2 ), ( ( p2.y + p3.y ) / 2 ) );

//Get Slope of l1
double sl1 = ( p1.y - p2.y ) / ( p1.x - p2.x );
//Get Slope of l2
double sl2 = ( p2.y - p3.y ) / ( p2.x - p3.x );
double sl3 = -1 / sl1;
double sl4 = -1 / sl2;

double b3 = ( m1.y - ( sl3 * m1.x ) );
double b4 = ( m2.y - ( sl4 * m2.x ) );


double cx = ( b4 - b3 ) / ( sl3 - sl4 );
double cy = sl3 * cx + b3;

And there you have it in pseudo code, now granted this doesn't contain any error catching, such as what happens with a slope of 0, or making sure all three starting points are unique and not in a straight line, but the guts of it are there, and that wasn't really the point of the post.

Any questions? see me after class