 |
|
| Computers Forum Index » Computer - Graphics (Algorithms) » bounding rectangle for a 2D arc... |
|
Page 1 of 1 |
|
| Author |
Message |
| Mukund... |
Posted: Fri Oct 30, 2009 5:37 am |
|
|
|
Guest
|
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
width radius = wR
height radius = hR
I couldn't figure out the earlier algorithms posted. Can someone
help?
Thanks. |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
Posted: Fri Oct 30, 2009 7:14 pm |
|
|
|
Guest
|
"Mukund" <talksense101 at (no spam) gmail.com> wrote in message
news:48a482d1-fe9d-4703-a56e-e07c503b333b at (no spam) 15g2000yqy.googlegroups.com...
Quote: 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?
Quote: starting point of the arc -> x,y
start angle of the arc (measured clockwise) -> startAngle
Measured clockwise from what reference axis?
Quote: swing angle of the arc (measured clockwise from start angle) -
swingAngle
width radius = wR
height radius = hR
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?
Quote: I couldn't figure out the earlier algorithms posted.
What posts are you referring to?
Not without a lot of clarification...
--
Dave Eberly
http://www.geometrictools.com |
|
|
| Back to top |
|
|
|
| Mukund... |
Posted: Sat Oct 31, 2009 5:57 am |
|
|
|
Guest
|
|
| Back to top |
|
|
|
| mike... |
Posted: Mon Nov 02, 2009 6:16 am |
|
|
|
Guest
|
In article <MPG.25586ac516df2a6698986d at (no spam) news.cc.tut.fi>, none at (no spam) here.com
says...
Quote: 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 |
|
|
| Back to top |
|
|
|
| Kaba... |
Posted: Mon Nov 02, 2009 6:16 am |
|
|
|
Guest
|
mike wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
| Kaba... |
Posted: Mon Nov 02, 2009 6:16 am |
|
|
|
Guest
|
Mukund wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
| Mukund... |
Posted: Mon Nov 02, 2009 10:10 am |
|
|
|
Guest
|
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 am, Kaba <n... at (no spam) here.com> wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
| Mukund... |
Posted: Mon Nov 02, 2009 10:39 am |
|
|
|
Guest
|
Well the image loads in Firefox if you directly link to it. So that
link is below.
http://www.documentinteropinitiative.org/implnotes/loadimage.aspx?imageid=1638
--------------------------------------
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 = center point of ellipse.
x(t) = h + a.cos(t).cos(o) - b.sin(t).sin(o)
y(t) = 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 = max(wR, wH), b min(wR, wH). a = semi major axis, b = 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 = x(t) - (a.cos(t).cos(o) - b.sin(t).sin(o))
k = 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 – a,k) Minor intercepts: ( h,k + b),
( h,k – b)
Bounding box = (h - a, k -b) x (h + a, k + b)
For vertical alignment
Major intercepts: ( h, k + a) ( h, k – a) Minor intercepts: ( h + b,
k) ( h – b, k)
Bounding Box = (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? |
|
|
| Back to top |
|
|
|
| Mukund... |
Posted: Mon Nov 02, 2009 11:35 am |
|
|
|
Guest
|
On Nov 2, 3:39 pm, Mukund <talksense... at (no spam) gmail.com> wrote:
Quote: Well the image loads in Firefox if you directly link to it. So that
link is below.
http://www.documentinteropinitiative.org/implnotes/loadimage.aspx?ima...
--------------------------------------
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 = center point of ellipse.
x(t) = h + a.cos(t).cos(o) - b.sin(t).sin(o)
y(t) = 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 = max(wR, wH), b > min(wR, wH). a = semi major axis, b = 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 = x(t) - (a.cos(t).cos(o) - b.sin(t).sin(o))
k = 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 – a,k) Minor intercepts: ( h,k + b),
( h,k – b)
Bounding box = (h - a, k -b) x (h + a, k + b)
For vertical alignment
Major intercepts: ( h, k + a) ( h, k – a) Minor intercepts: ( h + b,
k) ( h – b, k)
Bounding Box = (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?
Changing the parametric equations to the ones below seem to work for
me.
Major axis horizontal: x = acosT + h, y = bsinT + k
Major axis vertical: x = bcosT + h, y = asinT + k |
|
|
| Back to top |
|
|
|
| Kaba... |
Posted: Mon Nov 02, 2009 5:01 pm |
|
|
|
Guest
|
Mukund wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sat Nov 28, 2009 1:30 pm
|
|