Efficient Calculations for computing the center of a circle
pnachtwey
What is known is the two vectors that intersect at x1,y1 and the
radius of turn. The first vector goes from x0,y0 to x1,y1. The
second from x1,y1 to x2,y2. I need a formula that will calculate an
constant radius turn from the first vector to the second vector. This
problem is similar to CNC g code types of problems. I have a very
efficient way to calculate the center of the circle if I have 2 points
and the radius but not two lines and the radius.
The two point and radius calculations require only one divide, one
square root and then a few multiply and adds or subtracts. My two
lines and a radius method required a lot of trig functions which is
going to be very slow.
I know I am not the first one to solve this problem. I am hoping
there is a simpler solution to the one I have.
BTW, my two points and a radius Scilab routine is
// Given r, x0, y0, x1, y1
x0=-1.0;
y0=0.0;
x1=0.0;
y1=1.5;
r=1; // radius of circle/turn
U=(x1-x0)^2+(y1-y0)^2; // Think of U as R^2
Q=sqrt((4*r^2-U)/U);
Center1=0.5* [ 1 -Q 1 Q ; Q 1 -Q 1 ]*[ x0 ; y0 ; x1 ; y1 ];
Center2=0.5* [ 1 Q 1 -Q ; -Q 1 Q 1 ]*[ x0 ; y0 ; x1 ; y1 ];
disp(Center1,Center2);
I am looking for a similar efficient method for finding the center of
the circle for two lines and a radius. I am sure it will be more
complicated but my current method uses the cosine law to find the
angle between the two vectors. The sine law to find the distance from
the intersection of the two vectors to the center of the circle, an
atan2 to compute the direction of motion and finally a sin and cos
function to calculate the center point relative to the intersection of
the two points. There must be a simpler way.
Peter Nachtwey
pnachtwey
the intersection of two lines parallel to the original two vectors
with a distance equal to the radius. The problem is now divide by
zero errors and there are four possible answers. I need a way to
calculate which way to offset the parallel lines.
Peter Nachtwey
Ray Koopman
> I need an efficient formula for calculating the center of a circle.
> What is known is the two vectors that intersect at x1,y1 and the
> radius of turn. The first vector goes from x0,y0 to x1,y1. The
> second from x1,y1 to x2,y2. I need a formula that will calculate
Slide point 2 along the line connecting it to point 1 until
it's just as far from point 1 as point 0 is. Call that point 3.
Let point 4 be the average of points 0 and 3.
Slide point 4 along the line connecting it to point 1 until
its distance from the line conecting point 0 to point 1 is r.
pnachtwey
the form of Δy*x-Δx*y=b. The parallel line is made by adding or
subtracting from b. This turns out to be in the form of r*sqrt
(Δx^2+Δy^2). The problem is that there can be a parallel line of
distance r on either side of both vectors. This yields four solutions
and I need only the right one. I now need a sign() function to compute
the correct sign of r*r*sqrt(Δx^2+Δy^2). So far I have only two
square roots and two divides to get this far not counting the multiply
and adds which happen quickly.
Peter Nachtwey
pnachtwey
The delta didn't display right. The Δ is supposed to be a delta
Peter Nachtwey
Niels Diepeveen
> I solved the divide by 0 problem by expressing the parallel lines in
> subtracting from b. This turns out to be in the form of r*sqrt
> distance r on either side of both vectors. This yields four solutions
> and I need only the right one. I now need a sign() function to compute
> square roots and two divides to get this far not counting the multiply
> and adds which happen quickly.
>
> Peter Nachtwey
As far as I can see the problem boils down to solving the linear system
det(v, v1-v0) / ||v1-v0|| = +/-r
det(v, v2-v1) / ||v2-v1|| = +/-r
If you can define whether v should be "to the left" or "to the right" of
v1-v0 and v2-v1 respectively then you know which of +/- to choose and
you're done. If you don't know that, what do you know?
--
Niels Diepeveen