COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### bounding rectangle for a 2D arc

• Follow

Hi,

I need the bounding algorithm for a 2D arc.  I have the following
parameters available.

starting point of the arc -> x,y
start angle of the arc (measured clockwise) -> startAngle
swing angle of the arc (measured clockwise from start angle) ->
swingAngle

I couldn't figure out the earlier algorithms posted.  Can someone
help?

Thanks.
 0
Reply talksense101 (1) 10/30/2009 5:37:24 AM

"Mukund" <talksense101@gmail.com> wrote in message
> I need the bounding algorithm for a 2D arc.  I have the following
> parameters available.

Do you want an axis-aligned rectangle?  An oriented rectangle?
If the latter, do you want the minimum-area rectangle?

> starting point of the arc -> x,y

> start angle of the arc (measured clockwise) -> startAngle

Measured clockwise from what reference axis?

> swing angle of the arc (measured clockwise from start angle) ->
> swingAngle

What do these numbers mean?  With two length measurements, can
we assume that this is not a circular arc with center at the origin?
If it is not a circular arc, then what type of arc is it?  For a circular
arc whose center is not at the origin, let (x0,y0) be the starting
point and let (x1,y1) be the ending point.  Let r0 = Length(x0,y0)
and r1 = Length(x1,y1).  How are wR and hR related to r0 and r1?

> I couldn't figure out the earlier algorithms posted.

What posts are you referring to?

> Can someone help?

Not without a lot of clarification...

--
Dave Eberly
http://www.geometrictools.com

 0

Thank you for the reply, Dave.

http://www.documentinteropinitiative.org/implnotes/ecma-376/625dc787-3cbc-46a9-8952-8308ff88f83f.aspx

It should explain things a lot better.   I am trying to draw that
shape on a device and the only drawing function available requires the
bounding rectangle of the arc and the start and swing angles.
 0

Mukund wrote:
> It should explain things a lot better.   I am trying to draw that
> shape on a device and the only drawing function available requires the
> bounding rectangle of the arc and the start and swing angles.

Hi,

I didn't get the meaning of the parameters either from the original post
nor from the link. An image could help here to explain..

--
http://kaba.hilvi.org
 0

In article <MPG.25586ac516df2a6698986d@news.cc.tut.fi>, none@here.com
says...
> Mukund wrote:
> > It should explain things a lot better.   I am trying to draw that
> > shape on a device and the only drawing function available requires the
> > bounding rectangle of the arc and the start and swing angles.
>
> Hi,
>
> I didn't get the meaning of the parameters either from the original post
> nor from the link. An image could help here to explain..
>
I gt the feeling that he isn't talking circles but means ellipses
oriented with major and minor axes in the horizontal and vertical
directions. Like the 'circle select' as used in photoshop for example.

Mike
 0

mike wrote:
> > Hi,
> >
> > I didn't get the meaning of the parameters either from the original post
> > nor from the link. An image could help here to explain..
> >
> I gt the feeling that he isn't talking circles but means ellipses
> oriented with major and minor axes in the horizontal and vertical
> directions. Like the 'circle select' as used in photoshop for example.
>
> Mike

That sounds like a plausible interpretation. In this case, define

f : R -> R^2 : f(x) = [cos(x), sin(x)]^T = [f_1(x), f_2(x)]^T

That is, f parametrizes a unit circle. We shall generalize to arbitrary
ellipses later.

Also define:

a in R - the start angle
b in R - the end (swing) angle, a <= b

These angles are measured counter-clockwise from the vector (1, 0). The
problem is to find a minimal axis-aligned box for this circle.

Let

X = {f_1(x) : x in [a, b]} = {cos(x) : x in [a, b]}
Y = {f_2(y) : y in [a, b]} = {sin(x) : x in [a, b]}

Then the minimal axis-aligned bounding box B is given by

B = [min(X), max(X)] x [min(Y), max(Y)]

If the range [a, b] contains such a point x that cos(x) = -1, then min
(X) = -1. Otherwise min(X) = min({cos(a), cos(b)}). max(X), min(Y), and
max(Y) are determined similarly.

Generalization to an ellipse works by mapping the ellipse's major and
minor axes to vectors (1, 0) and (0, 1), respectively, finding the
bounding box as above, and inverse-mapping the bounding box back to
bound the ellipse. Depending on the transformation, the inverse-mapped
bounding box can be axis-aligned or not. However, in the particular case
that the ellipses have their principal axes aligned with standard basis
axes, the boxes remain axis-aligned (the transformations consists of
translation + (non-uniform) scaling w.r.t standard basis axes).

I leave it to the OP to fill in the details.

--
http://kaba.hilvi.org
 0

For some reason, the image in the link shows up only in Chrome or
Safari or IE and it doesn't render in Firefox.

On Nov 2, 7:05=A0am, Kaba <n...@here.com> wrote:
> Mukund wrote:
> > It should explain things a lot better. =A0 I am trying to draw that
> > shape on a device and the only drawing function available requires the
> > bounding rectangle of the arc and the start and swing angles.
>
> Hi,
>
> I didn't get the meaning of the parameters either from the original post
> nor from the link. An image could help here to explain..
>
> --http://kaba.hilvi.org

 0

Well the image loads in Firefox if you directly link to it.  So that

=3D1638

--------------------------------------

I tried the following approach assuming that the ellipse that contains
the arc is restricted along either the X-Axis or the Y-Axis.

Using the general parametric form.

h, k =3D center point of ellipse.
x(t) =3D h + a.cos(t).cos(o) - b.sin(t).sin(o)
y(t) =3D k + a.cos(t).sin(o) + b.sin(t).cost(o)

where (o) is either 0 or 90 degrees (angle between X axis and
alignment of ellipse) and (t) is the angle for a point of interest.

Given the fact that the ellipse is axis aligned, a =3D max(wR, wH), b =3D
min(wR, wH).  a =3D semi major axis, b =3D semi minor axis.

I calculated the center of the ellipse (h, k) as below as the starting
angle(startAngle) and the starting point of the arc (startX, startY)
are known.

h =3D x(t) - (a.cos(t).cos(o) - b.sin(t).sin(o))
k =3D y(t) - (a.cos(t).sin(o) + b.sin(t).cos(o))

from the above equations.

For horizontal alignment.
Major intercepts: ( h + a,k), ( h =96 a,k) Minor intercepts: ( h,k + b),
( h,k =96 b)
Bounding box =3D (h - a, k -b) x (h + a, k + b)

For vertical alignment
Major intercepts: ( h, k + a) ( h, k =96 a) Minor intercepts: ( h + b,
k) ( h =96 b, k)
Bounding Box =3D (h - b, k - a) x (h + b, k + a)

------------------

Having said that, the vertically aligned ellipses don't work
correctly.   I am trying to figure out what I am doing wrong.  Any
ideas?

 0

On Nov 2, 3:39=A0pm, Mukund <talksense...@gmail.com> wrote:
> Well the image loads in Firefox if you directly link to it. =A0So that
>
>
> --------------------------------------
>
> I tried the following approach assuming that the ellipse that contains
> the arc is restricted along either the X-Axis or the Y-Axis.
>
> Using the general parametric form.
>
> h, k =3D center point of ellipse.
> x(t) =3D h + a.cos(t).cos(o) - b.sin(t).sin(o)
> y(t) =3D k + a.cos(t).sin(o) + b.sin(t).cost(o)
>
> where (o) is either 0 or 90 degrees (angle between X axis and
> alignment of ellipse) and (t) is the angle for a point of interest.
>
> Given the fact that the ellipse is axis aligned, a =3D max(wR, wH), b =3D
> min(wR, wH). =A0a =3D semi major axis, b =3D semi minor axis.
>
> I calculated the center of the ellipse (h, k) as below as the starting
> angle(startAngle) and the starting point of the arc (startX, startY)
> are known.
>
> h =3D x(t) - (a.cos(t).cos(o) - b.sin(t).sin(o))
> k =3D y(t) - (a.cos(t).sin(o) + b.sin(t).cos(o))
>
> from the above equations.
>
> For horizontal alignment.
> Major intercepts: ( h + a,k), ( h =96 a,k) Minor intercepts: ( h,k + b),
> ( h,k =96 b)
> Bounding box =3D (h - a, k -b) x (h + a, k + b)
>
> For vertical alignment
> Major intercepts: ( h, k + a) ( h, k =96 a) Minor intercepts: ( h + b,
> k) ( h =96 b, k)
> Bounding Box =3D (h - b, k - a) x (h + b, k + a)
>
> ------------------
>
> Having said that, the vertically aligned ellipses don't work
> correctly. =A0 I am trying to figure out what I am doing wrong. =A0Any
> ideas?

Changing the parametric equations to the ones below seem to work for
me.

Major axis horizontal: x =3D acosT + h, y =3D bsinT + k
Major axis vertical: x =3D bcosT + h, y =3D asinT + k
 0

Mukund wrote:
> Having said that, the vertically aligned ellipses don't work
> correctly.   I am trying to figure out what I am doing wrong.  Any
> ideas?

You describe an arc of an axis-aligned ellipse by the following
information

1) Half-length of x-axis 'a'
2) Half-length of y-axis 'b'
3) A point (x, y) on the arc
4) Starting angle 'startAngle'
5) Swing angle 'swingAngle'

Of these, information 3) is redundant and can easily make the
description undefined. For example, there is no ellipse which would
satisfy: a = 1, b = 1, (x, y) = (0.1, 0.1). This is because a and b
already describe an axis-aligned ellipse unambiguosly.

There's something wrong with the problem description..

Btw, it is not good (either for analysis or algorithms) to use the
concepts of major and minor axes of an ellipse, because which is which
depends on lengths and leads you into dealing with cases. Better just to
associate each principal axis statically with a length.

--
http://kaba.hilvi.org
 0

9 Replies
528 Views

Similiar Articles:

7/21/2012 11:38:55 PM