1. ## Arc coordinate conversion

Hi. First post here. Hope I don't break protocol...
I am writing software to convert a display list file into a different display list file format (conceptually similar to HTML, for those who care). The display list files use differing ways to describe arcs, and I need to transform from one to the other. Both use a Cartesian coordinate system to define the drawing space.
My input file describes arcs in terms of a start-point (x0,y0), end-point (x1,y1), and a central angle (a). I need to transform the arcs described in the input to a format that uses a starting angle (c), a total angle (d), and the coordinates of a bounding box whose sides are tangent to the circle that would complete the arc.
I would like to know how I can make such a translation; at least some pointers to the key rules that I can use.
This is not homework, just to clear the air on that matter. Feel free to correct any jargonolgy errors.
Thanks,
--- rod.

2. Assuming the arcs are centered at the origin, the coordinates of the box would be (r, r), (r, -r), (-r, -r), and (-r, r), where

$r = \sqrt{x_0^2 + y_0^2} = \sqrt{x_1^2 + y_1^2}$.

I don't understand why you would need two angles.

3. The centre point is completely unknown, and will almost never be at the origin. As for why the need for two angles, well that is what the program that reads and renders the display list file requires. This is not an aspect left for me to specify. I guess you could specify the starting and ending angles of the arc, which is really the same thing.

Thanks for responding.

--- rod.

4. Upon reflection, I think I can restate my problem, removing my own problem domain, and creating a generic mathematical question. Here goes...
Given an arc with start-point, end-point, and central angle, what is the center point and radius of the arc?
Clearer, no?

--- rod.

5. Originally Posted by theNbomr
Upon reflection, I think I can restate my problem, removing my own problem domain, and creating a generic mathematical question. Here goes...
Given an arc with start-point, end-point, and central angle, what is the center point and radius of the arc?
Clearer, no?

--- rod.
I have your answer, but it is probably more complicated than you are going to like.

You have three unknowns: $(x_c, y_c)$ which is the circle center, and $r$, the circle radius. You know your two points $(x_1, y_1), (x_2,y_2)$ and the central angle $c_A$ assumed to be in radians (in your picture above, what I'm calling $c_A$ is actually $2\pi - a$. Your $a$ is the angle of the major arc, while $c_A$ is the angle of the minor arc). You have the equations:

$(x_1 - x_c)^2 + (y_1 - y_c)^2 = r^2$
$(x_2 - x_c)^2 + (y_2 - y_c)^2 = r^2$

So far so good. Two equations for 3 unknowns - we are almost there. Now to incorporate the central angle information. Recall the law of cosines. From this we can derive that

$d^2 = 2r^2(1 - \cos(c_A))$

where $d$ is the distance between $(x_1, y_1)$ and $(x_2,y_2)$. So we have

$(x_1 - x_2)^2 + (y_1 - y_2)^2 = 2r^2(1 - \cos(c_A))$

(Let me know if you have questions about this derivation - it follows pretty quickly from the law of cosines.)

We now have three equations and three unknowns. I don't even want to try solving this thing by hand - you can have fun with that if you want. Instead, we can solve this non-linear system of equations using a computer, for example in MATLAB (if you have to program this yourself, I suggest you use a modified Newton's method or the like as described in Numerical Recipes).

In MATLAB, fsolve is used for finding an x that is a solution to the system of non-linear equations $F(x) = 0$. The syntax is

x = fsolve(fun,x0)
where fun is a function reference, and x0 is an initial guess.

Here is a function in MATLAB that solves your problem:

function F = test( x, x_1, y_1, x_2, y_2, c_A )
x_c = x(1);
y_c = x(2);
r = x(3);

F = zeros(3,1);
F(1) = (x_1 - x_c)^2 + (y_1 - y_c)^2 - r^2;
F(2) = (x_2 - x_c)^2 + (y_2 - y_c)^2 - r^2;
F(3) = (x_1 - x_2)^2 + (y_1 - y_2)^2 - 2*r^2*(1 - cos(c_A));
end
You can now run this in MATLAB with the syntax.

A = fsolve(@(x)test(x,3,5,-3,5,acos(7/25)),[1,-1,pi/2])
Here fun = @(x)test(x,3,5,-3,5,c_A) is the function pointer, and x0 = [1,-1,pi/2].

I setup a problem where I know the answer to test this. If you choose $(x_c,y_c) = (0,1)$ and $r = 5$, you can choose the points $(x_1,y_1) = (-3,4)$ and $(x_2,y_2) = (3,4)$. This gives $c_A = \cos^{-1}(7/25)$.

If you run this in MATLAB, you would get the output:

EDU>> A = fsolve(@(x)test(x,3,5,-3,5,c_A),[1,-1,pi/2])
Optimization terminated: first-order optimality is less than options.TolFun.

A =

0 1.00 5.00
which are the parameters I used to create this example. Success!

6. Originally Posted by lgstarn
I don't even want to try solving this thing by hand - you can have fun with that if you want.
Although actually it does seem doable. The non-linearity isn't too bad because $c_A$ is known.

I think you should be able to solve for an exact solution. But I'm not going to right now.

7. Originally Posted by lgstarn
Although actually it does seem doable. The non-linearity isn't too bad because $c_A$ is known.

I think you should be able to solve for an exact solution. But I'm not going to right now.
Oh, last thought for the night. You will get a quadratic equation for the exact solution. Throw away the one that will give you a negative $r$.

8. Originally Posted by lgstarn
Oh, last thought for the night. You will get a quadratic equation for the exact solution. Throw away the one that will give you a negative $r$.

Ok, ok, I finished it. Bad news: there are two possible solutions. This makes sense if you think about it - if you have the same radius and the same central angle, you can have the center in either the positive or negative direction.

Here's the solution:

Let:

$d^2 = (x_1 - x_2)^2 + (y_1 - y_2)^2$

$m = \frac{y_2 - y_1}{x_2 - x_1}$

$x_m = \frac{x_1 + x_2}{2}$

$y_m = \frac{y_1 + y_2}{2}$

Here $d$ is the distance between the two points, $m$ is the slope of the line connecting the two points, and $(x_m, y_m)$ is the mid-point between the two points.

Giving:

$r = \frac{d}{\sqrt{2(1-\cos(c_A))}}$

$y_{c_1} = y_m + \frac{\sqrt{4r^2 - d^2}(x_2 - x_1)}{2d}$

$y_{c_2} = y_m - \frac{\sqrt{4r^2 - d^2}(x_2 - x_1)}{2d}$

$x_{c_1} = x_m - m(y_m - y_{c_1})$

$x_{c_2} = x_m - m(y_m - y_{c_2})$

So, unless you have some more information, looks like your solution is not unique. In my example above, the center can either be at $(0,9)$ or $(0,1)$.

This breaks if $x_1 = x_2$. In that case,

$y_c = y_m$

$x_c = x_2 \pm \sqrt{r^2 - (y_2 - y_c)^2}$

9. Many thanks for your thorough explanation and analysis. I'm sure I will need at least an order of magnitude more time to digest it than it took for you to compose it. I feel certain I will followup with more questions.
The conclusion that the solution is non-unique is a bit disconcerting. Is it possible that I can discern the desired solution from the order of the end-points (or the 'direction' of the angle, to put it another way)? The software that visually renders these data is sensitive to the order in which they are read in the input, hence my description of 'start' and 'end' points.
Thanks.
--- rod.

10. Originally Posted by theNbomr
Many thanks for your thorough explanation and analysis. I'm sure I will need at least an order of magnitude more time to digest it than it took for you to compose it. I feel certain I will followup with more questions.
The conclusion that the solution is non-unique is a bit disconcerting. Is it possible that I can discern the desired solution from the order of the end-points (or the 'direction' of the angle, to put it another way)? The software that visually renders these data is sensitive to the order in which they are read in the input, hence my description of 'start' and 'end' points.
Thanks.
--- rod.
You are welcome. Take your time and follow up with as many questions as you like. This was a fun problem for me.

Ok, so the order does matter. That's a start. If you can say if the central angle is measured clockwise or counter-clockwise, I'll tell you which solution to use. That would give enough for a unique solution.

Make sure you tell me if the orientation is for the minor or major arc.

11. Originally Posted by lgstarn
Make sure you tell me if the orientation is for the minor or major arc.
Oops - minor or major arc doesn't matter. Just orientation between the two points is sufficient. Also looks like from your picture that your orientation is counter-clockwise. Is this correct?

12. Okay, now I'm confused. Isn't the term major/minor arc simply an expression of the magnitude of the central angle (which we already know)?
--- rod.
EDIT:
Oh, darn. I was posting the question while you were posting the answer....