🔒 Locked

arc bounding box

Started by taxman Nov 12, 2000 at 9:06 PM 2 replies 6.8k views

Original Post

Nov 12, 2000 at 9:06 PM

given an arc with the xy of two endpoints, a center pt, and a direction how could i calculate the minimum bounding box around the points? x y i ---------- 180 67 0 140 37 1 170 77 0 ---------- this is an arc starting at pt 180,67 then going to pt 170,77 in direction 1 (counter clock wise). im trying to do it based upon which quadrants the points lay in, but it leads to over 60 if else statements and an ungodly amount of special cases. help?

Wyzfen

Nov 12, 2000 at 11:28 PM

hmm. i can only figure how to do it with 21 ifs - but i'd convert the coords to radius and angles first.

was there any particular reason you are using cartesian rather than polar coordaintes (with a cartesian offset) ?
ie x,y,z rather than radius,angle ?

using angles, the solution is fairly easy:
having worked out the MAXIMUM bounding box, you now need to trim it as needed.
so, all you need to do to check if the current left edge of your box is the correct choice, is to see if the angle 180 is in range.
thus, if you have converted your points to angles,
if it's CW, then point1 >= 180 >= point2
if it's CCW, then point2 >= 180 >= point1
will mean that that edge of the box has to be correct.
if that check isn't true, then the left edge of the box has to be one of the end points - so work out which is the minimum end point (from your cartesian coords)

you then need to do the check for the top (90) right (0) and bottom (270) edges.

oh. you'll also have to take into the account where the arc crosses 360 degrees.

Wyzfen

Edited by - Wyzfen on November 12, 2000 12:45:32 AM

Edited by - Wyzfen on November 12, 2000 12:46:18 AM

taxman

Author

taxman

Nov 13, 2000 at 3:45 PM

oh man! your answer was exactly what i needed!

you gave me a fresh spin on how to approach this problem and now i think i have a perfect solution. (but i cant try anything till i get home from work).

im going to convert to angles of the two points.

then just make a while loop either counting up or down (depending on if the arc is clockwise or counterclockwise) until i hit the second point. and just keep track of the axis that i cross along the way

! im so happy !

thanks man,
-matt

Wyzfen

Nov 13, 2000 at 5:05 PM

Glad that i helped

I kinda shuddered when i heard about your implementations tho

If you use a few if statements, you won't need to use a while loop (which is going to be slow in this case).

Also, in my last post i seem to have chopped some out - to find the maximum possible bounding box (before trimming it) you need to find the radius, then do (centerX+/-radius,centerY+/-radius)

and an example (again, for 180 degrees) assume it starts at angle 1 and finishes at angle 2 and is in the CCW direction

    
if(direction==CCW) // counterclockwise

{
   //check that angle2 > angle1

   if(angle2 < angle1) angle2+=360;
   
   //check the 180 degree case:

   if((angle2 >= 180)&&(angle1 <= 180)) 
   {
     // it does include 180 degrees, so the bounding edge is:

     bounds.left=centerX-radius;
   }
   else
   {
     // it DOESN't include 180 degrees, so work out which is the

     // lowest of the two points.

     float x1,x2;
     x1=(float)radius*cos(angle1);
     x2=(float)radius*cos(angle2);
     bounds.left=centerX + (int)(x1 < x2?x1:x2)
   }
}

You can work out the other 7 cases

NOTE: i normally wouldn't post code, but the idea of using a while loop for this is disturbing.

Wyzfen

Edited by - Wyzfen on November 13, 2000 6:08:21 PM

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.