Page 1 of 3
Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 9:05 am
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 12:13 pm
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 1:42 pm
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 1:47 pm
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 2:08 pm
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 3:38 pm
by 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!
Re: Any maths gurus who can help with geometry?!
Posted: Fri Jan 08, 2010 3:57 pm
by 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...
Re: Any maths gurus who can help with geometry?!
Posted: Sun Jan 10, 2010 8:22 pm
by 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
Re: Any maths gurus who can help with geometry?!
Posted: Sat Jan 16, 2010 9:24 pm
by Olliv
@Seymour Clufley
Sorry but is your problem solved?
Ollivier
Re: Any maths gurus who can help with geometry?!
Posted: Tue Jan 19, 2010 2:24 pm
by Seymour Clufley
I'm afraid I don't know yet, as I've been away from home and unable to test Idle's code.
Re: Any maths gurus who can help with geometry?!
Posted: Tue Jan 19, 2010 7:31 pm
by 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.
Re: Any maths gurus who can help with geometry?!
Posted: Tue Jan 19, 2010 7:37 pm
by srod
The horizontal/vertical bounding box is not obtained, for a rotated ellipse, by simply rotating the minor/major axes - no sir!
Re: Any maths gurus who can help with geometry?!
Posted: Tue Jan 19, 2010 9:33 pm
by 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
Re: Any maths gurus who can help with geometry?!
Posted: Wed Jan 20, 2010 1:19 am
by kernadec
hello
an example for manipulation of ellipses and other figures here:
http://www.purebasic.fr/french/viewtopic.php?f=3&t=8642
bye
Re: Any maths gurus who can help with geometry?!
Posted: Wed Jan 20, 2010 5:21 am
by 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.