Any maths gurus who can help with geometry?!

[Seymour Clufley]

I need to get the bounding box for an elliptical arc. I have the start point, the end point, and the arc's x and y radii.

This page has some algorithms but I have no idea what they're talking about - "minor intercepts" etc.

I know this is cheeky but maths was never my forte so if someone could supply the algorithm, I'd really be grateful. It's for a project that will benefit the community.

[srod]

Need to know what you mean by the 'arc's x and y radii' ?

Do you mean the lengths of the minor/major axes of the bounding ellipse, or do you mean the length of the radii drawn from the center of the assumed ellipse to the two end-points?

Are you assuming that the arc is bound by an ellipse in canonical position (centered at the origin, minor/major axes parallel to the x/y axis etc.) ?

Which bounding rectangle are you after? Do you require the bounding rectangle of the aforementioned ellipse or do you require the bounds of the smallest rectangle containing the arc?

Questions, questions!

In theory it is not difficult to do what you are after, but the math could be a bit fiddly.

[Seymour Clufley]

It's from the SVG spec. There's a function to draw an elliptical arc.

Draws an elliptical arc from the current point to (x, y). The size and orientation of the ellipse are defined by two radii (rx, ry) and an x-axis-rotation, which indicates how the ellipse as a whole is rotated relative to the current coordinate system. The center of the ellipse is calculated automatically to satisfy the constraints imposed by the other parameters. large-arc-flag and sweep-flag contribute to the automatic calculations and help determine how the arc is drawn.

Graphic examples and more here.

So it's an arc formed using a section of an ellipse, but positioned using arbitrary start and end coordinates. We choose those start/end coordinates, and we choose the ellipse's radii and its angle of rotation.

What I need to know is, if I wanted to frame the resulting arc in a rectangle, what would the (x,y,w,h) of the rectangle need to be? The rectangle cannot be at an angle; it has to be parallel with the x/y axes.

[srod]

With the condition that the rectangle has to be parallel to the x/y axis and with the possibility that the underlying ellipse need not be parallel to these axes... this would appear to me to be a very difficult problem. A rotated rectangle would be relatively simple (by that I mean, quite fiddly! ) A non-rotated rectangle... yuk! I'd need to give this some thought.

[Seymour Clufley]

I'd need to give this some thought.

Well srod, if you could do so it'd be a great help. My maths is dreadful (failed the A-level).

The reason this is needed is so that an SVG element incorporating an arc can be reliably rotated, centralised, repositioned etc. If we don't know its bounding box we can't manipulate an element reliably. I'm currently investigating how to get the bounding box for cubic and quadratic bezier curves.

[srod]

This is a tough problem.

Do-able, but tough!

Assuming that your ellipse has major axis of length a and minor axes of length b and has been rotated by A degrees (with (0, 0) origin still) then the entire ellipse is bounded by the rectange with top left = (-X, Y) and bottom right = (X, -Y) where :

Code: Select all

X = Sqr((a*Cos(A))^2 + (b*Sin(A))^2)
Y = Sqr((a*Sin(A))^2 + (b*Cos(A))^2)

(Using the unsupported ^ operator).

Whilst trying to bound a given arc, you will need to consider whether the arc includes any of the 'extreme points' on the rotated ellipse (those giving max or min x/y coords) and if so you will need to inflate the arc's bounding rectangle as appropriate. Deciding whether the arc includes any of these points is a problem whose solution eludes me right now... still thinking...

**EDIT : okay, the solution requires that we identify the 4 'extreme points' of our rotated ellipse. E.g. the highest point on the ellipse will have y-coordinate given by Y in the above code. More specifically we need to identify the 'parameters' of the four points in question. The points on a rotated (oblique) ellipse can be described by a parametric equation, a quite complex one (see wikipedia - scroll down to the general parametric form). Determining the parameter values for our four extreme points requires a bit of trig.

Armed with these value, and the parameter values for the two end-points of our arc, we can then determine if our arc includes any of these extreme points and inflate our bounding rectangle as appropriate.

At this point I will bow out because I am afraid that I have nowhere near the free time I would require to put this into code.

As I say though, it is doable... just very non-trivial!

[Kaeru Gaman]

just thinking a bit loud, maybe it helps....

when I have two points in the plane and a well defined ellipse (two radii and a rotation),
I will have always TWO possible solutions how this two points lay exactly on the periphery of the ellipse.

the straight line between the two points is a sekant of the ellipse.
it's length and angle relative to the ellipse's rotation is known.
when I rotate this sekant, I can view the ellipse as not-rotated.
now I have a simple origin ellipse with two radiuses.
finding start and end of the sekant is trivial, then I have the translation of the two points to the origin.
rotate them by same amount as the ellipse, these are the distances from the two given drawing points to the centre point of the elliptic arc.
start and end angle also dropped off this calculation.

but, I still say this problem has two solutions, the arc can always go left or right the same bow.

PS:
ok, with an ellipse it seems to be called the normal, not the sekant...
http://de.wikipedia.org/wiki/Ellipse#No ... dinaten.29
PPS:
sorry, can't find this paragraph in the english wiki article...

[idle]

I'm about to run out the door

try modify this perhaps

Code: Select all

Procedure DrawElipse(color.i,ptx,pty)

Protected hdc,cx.f,cy.f,majoraxis.f,minoraxis.f,orient.f,dx.f,dy.f,ndx,ndy,r1.rect,da

      StartDrawing(WindowOutput(0))
       
      cx = ptx
      cy = pty
      
      majoraxis = Random(100)
      minoraxis = Random(100)
      orient = Random(180)
      
      If majoraxis > minoraxis  
       tx = majoraxis 
       ty = minoraxis 
      Else 
       tx=minoraxis 
       ty=majoraxis 
      EndIf 
      
     
      r1\left = (cx - tx) 
      r1\right = (cx + tx) 
      r1\top = (cy - ty) 
      r1\bottom = (cy + ty) 
            
       
       
      LineXY(r1\left, r1\top,r1\right, r1\top ,color)
      LineXY(r1\left, r1\top,r1\left, r1\bottom ,color)
      LineXY(r1\right, r1\top,r1\right, r1\bottom ,color)
      LineXY(r1\left, r1\bottom,r1\right, r1\bottom ,color) 
   

     Protected theta.f,dx1,dy1,cosOrient.f,SinOrient.f
      cosOrient = Cos(orient)
      sinOrient = Sin(orient)
      ;draw a rough elipse
      For da = 1 To 500   
        theta = da
        dx = cx + (Sin(theta) * majoraxis)
        dy = cy + (Cos(theta) * minoraxis)
        dx1 = dx - cx
        dy1 = dy - cy
        ndx = cx + (dx1 * sinOrient - dy1 * cosorient) ;rotate elipse
        ndy = cy + (dx1 * cosOrient + dy1 * sinorient)
        If ndx > 0 And ndx < 800 And ndy > 0 And ndy < 600 
           Plot(ndx, ndy,~color & $FFFF)
        EndIf 
      Next
           
      Plot(Int(cx),Int(cy), color)
   




StopDrawing()


EndProcedure 

Global pt.point

OpenWindow(0,0,0,800,600,"",#PB_Window_ScreenCentered | #PB_Window_SystemMenu )


Repeat 

ev = WaitWindowEvent()

If ev = #WM_LBUTTONUP 
  pt\x=WindowMouseX(0)
  pt\y=WindowMouseY(0)
  DrawElipse(RGB(255,0,0),pt\x,pt\y) 
EndIf 
  
Until ev = #PB_Event_CloseWindow 

[Olliv]

@Seymour Clufley

Sorry but is your problem solved?

Ollivier

[Seymour Clufley]

I'm afraid I don't know yet, as I've been away from home and unable to test Idle's code.

[idle]

well it's an ellipse rather than an arc but if you rotate the major and minor axis or would that be the tangent, it should give you the bounding box.

[srod]

The horizontal/vertical bounding box is not obtained, for a rotated ellipse, by simply rotating the minor/major axes - no sir!

[RASHAD]

idle code modified

Code: Select all

Procedure DrawElipse(color.i,ptx,pty)

Protected hdc,cx.f,cy.f,majoraxis.f,minoraxis.f,orient.f,dx.f,dy.f,ndx,ndy,r1.rect,da

      StartDrawing(WindowOutput(0))
       
      cx = ptx
      cy = pty
      
      majoraxis = Random(100)
      minoraxis = Random(100)
      orient = Random(180)
      
;       If majoraxis > minoraxis  
;        tx = majoraxis 
;        ty = minoraxis 
;       Else 
;        tx=minoraxis 
;        ty=majoraxis 
;       EndIf 
      
     
;       r1\left = (cx - tx) 
;       r1\right = (cx + tx) 
;       r1\top = (cy - ty) 
;       r1\bottom = (cy + ty) 
;             
;        
;        
;       LineXY(r1\left, r1\top,r1\right, r1\top ,color)
;       LineXY(r1\left, r1\top,r1\left, r1\bottom ,color)
;       LineXY(r1\right, r1\top,r1\right, r1\bottom ,color)
;       LineXY(r1\left, r1\bottom,r1\right, r1\bottom ,color) 
    mndx = 800
    xndx = 0
    mndy = 600
    xndy = 0 

     Protected theta.f,dx1,dy1,cosOrient.f,SinOrient.f
      cosOrient = Cos(orient)
      sinOrient = Sin(orient)
      ;draw a rough elipse
      For da = 1 To 500   
        theta = da
        dx = cx + (Sin(theta) * majoraxis)
        dy = cy + (Cos(theta) * minoraxis)
        dx1 = dx - cx
        dy1 = dy - cy
        ndx = cx + (dx1 * sinOrient - dy1 * cosorient) ;rotate elipse
        ndy = cy + (dx1 * cosOrient + dy1 * sinorient)
        If ndx > 0 And ndx < 800 And ndy > 0 And ndy < 600 
           Plot(ndx, ndy,~color & $FFFF)
           If ndx > xndx
              xndx = ndx
           ElseIf ndx < mndx
              mndx = ndx
           EndIf
           If ndy > xndy
              xndy = ndy
           ElseIf ndy < mndy
              mndy = ndy
           EndIf              
        EndIf 
      Next
      
      LineXY(mndx,mndy,xndx,mndy,#Red)
      LineXY(mndx,xndy,xndx,xndy,#Red)
      LineXY(mndx,mndy,mndx,xndy,#Red)
      LineXY(xndx,mndy,xndx,xndy,#Red) 
           
      Plot(Int(cx),Int(cy), color)
      
StopDrawing()

EndProcedure 

Global pt.point

OpenWindow(0,0,0,800,600,"",#PB_Window_ScreenCentered | #PB_Window_SystemMenu )


Repeat 

ev = WaitWindowEvent()

If ev = #WM_LBUTTONUP 
  pt\x=WindowMouseX(0)
  pt\y=WindowMouseY(0)
  DrawElipse(RGB(255,0,0),pt\x,pt\y) 
EndIf 
  
Until ev = #PB_Event_CloseWindow 

[kernadec]

hello
an example for manipulation of ellipses and other figures here:
http://www.purebasic.fr/french/viewtopic.php?f=3&t=8642

bye

[idle]

That the business Rashad

@srod
what? isn't the major and minor axis the length and width respectively, so shouldn't it be possible to get the bounding box by either calculating the rotation of them to the x and y axis or taking the tangent to the x and y axis or something like that. Unfortunately I'm far to inebriated and mathematically challenged to work it out at the moment.

@kernadec

That looks good, maybe you can sort out the arc function.