ye@henri.ucsb.edu (03/21/91)
Hi everyone, I am looking for an algorithm for the following problem: Given an arc that starts at point (x1,y1), passes through point (x2,y2), and ends at point (x3,y3) find its equivalent representation by a center point (x0,y0), the radius R, and the sweep angle (alpha). If there is an existing algorithm somewhere, could somebody tell me where I can find it? Thanks, David
spencer@eecs.umich.edu (Spencer W. Thomas) (03/22/91)
In article <10082@hub.ucsb.edu> ye@henri.ucsb.edu writes: > Given an arc that starts at point (x1,y1), passes > through point (x2,y2), and ends at point (x3,y3) > find its equivalent representation by a center point > (x0,y0), the radius R, and the sweep angle (alpha). Connect P1 and P2 with a line, connect P2 and P3 with a line. The intersection of the perpendicular bisectors of these lines is the center point (P0). R is the distance from P0 to P1. Let Vi = Pi - P0, and define Vi x Vj = (xi yj - yi xj). Then if (V1 x V2), (V2 x V3), and (V1 x V3) all have the same sign, A = acos(V1 . V3), otherwise A = 2Pi - acos(V1 . V3). (Vi . Vj is vector dot product). -- =Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F)
hyu@eng.umd.edu (Henry K. Yu) (04/03/91)
>In-Reply-To: ye@henri.ucsb.edu's message of 20 Mar 91 22:29:48 GMT > >In article <10082@hub.ucsb.edu> ye@henri.ucsb.edu writes: >> Given an arc that starts at point (x1,y1), passes >> through point (x2,y2), and ends at point (x3,y3) >> find its equivalent representation by a center point >> (x0,y0), the radius R, and the sweep angle (alpha). > >Connect P1 and P2 with a line, connect P2 and P3 with a line. >The intersection of the perpendicular bisectors of these lines is the >center point (P0). R is the distance from P0 to P1. Let Vi = Pi - >P0, and define Vi x Vj = (xi yj - yi xj). Then if >(V1 x V2), (V2 x V3), and (V1 x V3) all have the same sign, >A = acos(V1 . V3), otherwise A = 2Pi - acos(V1 . V3). (Vi . Vj is >vector dot product). > > >-- >=Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 >spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F) A less computationally intensive way would be to use the Law of Cosine. 1. Find the center P0, describe above 2. Borrowing Mr. Thomas's convention, one can compute the cord length of [P0,P1], [P0,P3], and [P1,P3] (note the first two is the same, R) 3. Law of Consine: c^2 = a^2 + b^2 - 2*a*b*cos(C) The angle C = acos( (a^2 + b^2 - c^2) / (2*a*b) ) The sweep angle (alpha) = acos( (2*R^2 - [P1,P3]^2) / (2*R^2) ) Note: number of multiplications can further be reduced by storing 2*R^2. Please let me know if there is anything wrong. Comments are very welcome. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ hyu@wam.umd.edu