I've googled till I'm blue in the face, and unless I'm missing something really obvious, I can't find any algorithms for calculating the bounding box of a 2D sector.
Given the centre point of the enclosing circle, the radius, and the angles of the extent of the sector, what's the best algorithm to calculate the axis-aligned bounding rectangle of that sector?
The points on the circle for every angle between the two that divides by 90o (maximum of 4 points) can you elaborate ? –
Acetylate I'm going to rephrase yairchu's answer so that it is clearer (to me, anyway).
Ignore the center coordinates for now and draw the circle at the origin. Convince yourself of the following:
You now have at most 4+1+2 points to find. Find the max and min of those coordinates to draw the rectangle.
The rectangle is easily translated to the original circle by adding the coordinates of the center of the original circle to the rectangle's coordinates.
First of all I apologize if I commit mistakes writing but english is not my first language, spanish is actually!
I faced this problem, and I think I found an efficient solution.
First of all let's see an image of the situation
So we have an ellipse (actually a circle) and two points (C, D) which indicates our sector.
We also have the center of our circle (B) and the angle of the Arc alpha.
Now, in this case I made it passing through 360º on porpouse to see if it would work.
Let's say alpha -> -251.1º (it negative cause its clockwise), lets transform it to positive value 360º - 251.1º = 108.9º now our goal is to find the angle of the bisection of that angle so we can find the max point for the bounding box (E in the image), actually as you may have realized, the length of the segment BE equals the radius of the circle but we must have the angle to obtain the actual coordinates of the E point.
So 108.9º / 2 -> 54.45º now we have the angle.
To find the coordinates of E we use polar coordinates so
x = r * Cos(theta)
y = r * Sin(theta)
we have r and theta so we can calculate x and y
in my example r = 2.82… (actually it's irational but I took the first two decimal digits as a matter of ease)
We know our first radii is 87.1º so theta would be 87.1 - 54.45º -> 32.65º
we know *theta * is 32.65º so let's do some math
x = 2.82 * Cos(32.65º) -> 2.37552
y = 2.82 * Sin(32.65º) -> 1.52213
Now we need to adjust these values to the actual center of the circle so
x = x + centerX
y = y + centerY
In the example, the circle is centered at (1.86, 4.24)
x -> 4.23552
y -> 5.76213
At this stage we should use some calculus. We know that one of the edges of the bounding box will be a tangent of the arc that passes through the point we just calculated so, lets find that tangent (the red line).
We know that the tangent passes through our point (4.23, 5.76) now we need a slope.
As you can see, the slope is the same as the slope of the rect that passes through our radii's so we have to find that slope.
For doing that we need to get the coordinates of our radii's (a fast conversion to cartessian coordinates from polar coordinates).
x = r * Cos(theta)
y = r * Sin(theta)
So
p0 = (centerX + 2.82 * Cos(87.1º), centerY + 2.82 * Sin(87.1º))
p1 = (centerX + 2.82 * Cos(-21.8º), centerY + 2.82 * Sin(-21.8º))
(21.8º is the angle measured clockwise from the horizontal axis to the radii that is below it and thus I put it negative)
p0 (2, 7.06)
p1 (4.48, 3.19)
now let's find the slope:
m = (y - y0) / (x - x0)
...
m = (3.19 - 7.06) / (4.48-2) = -3.87 / 2.48 = -1.56048
...
m = -1.56
having the slope we need to calculate the equation for the tangent, basically is a rect with an already known slope (m = -1.56) that passes through an already know point (E -> (4.23, 5.76))
So we have Y = mx + b where m = -1.56, y = 5.76 and x = 4.23 so b must be
b = 5.76 - (-1.56) * 4.23 = 12.36
Now we have the complete equation for our tangent -> Y = -1.56X + 12.36
All we must do know is project the points C and D over that rect.
We need the equations for the rects CH and DI so let's calculate 'em
Let's start with CH:
We know (from the tanget's equation) that our direction vector is (1.56, 1)
We need to find a rect that passes through the point C -> (2, 7.06)
(x - 2) / 1.56 = (y - 7.06) / 1
Doing some algebra -> y = 0.64x + 5.78
We know have the equation for the rect CH we must calculate the point H.
we have to solve a linear system as follows
y = -1.56x + 12.36
y = 1.56x + 5.78
Solving this we'll find the point H (3, 7.69)
We need to do the same with the rect DI so let's do it
Our direction vector is (1.56, 1) once again
D -> (4.48, 3.19)
(x - 4.48) / 1.56 = (y -3.19) / 1
Doing some algebra -> y = 0.64x + 0.32
Lets solve the linear system
y = -1.56x + 12.36
y = 0.64x + 0.32
I (5.47, 3.82)
At this stage we already have the four points that make our Bounding box -> C, H, D , I
Just in case you don't know or rememeber how to solve a linear system on a programming language, i'll give you a little example
It's pure algebra
Let's say we have the following system
Ax + By = C
Dx + Ey = F
then
Dx = F - Ey
x = (F - Ey) / D
x = F/D - (E/D)y
replacing on the other equation
A(F/D - (E/D)y) + By = C
AF/D - (AE/D)y + By = C
(AE/D)y + By = C - AF/D
y(-AE/D + B) = C - AF/D
y = (C - AF/D) / (-AE/D + B)
= ( (CD - AF) / D ) / ( (-AE + BD) / D) )
so
y = (CD - AF) / (BD - AE)
and for x we do the same
Dx = F - Ey
Dx - F = -Ey
Ey = F - Dx
y = F/E - (D/E)x
replacing on the other equation
Ax + B(F/E - (D/E)x) = C
Ax + (BF/E - (DB/E)x) = C
Ax - (DB/E)x = C - BF/E
x (A-(DB/E)) = C - BF/E
x = (C - BF/E)/(A-(DB/E))
= ((CE - BF) / E) / ((AE-DB) / E)
x = (CE - BF) / (AE - DB)
I apologize for the extent of my answer but I meant to be as clear as possible and thus, I made it almost step by step.
In C# code:
/// <summary>
/// The input parameters describe a circular arc going _clockwise_ from E to F.
/// The output is the bounding box.
/// </summary>
public Rect BoundingBox(Point E, Point F, Point C, double radius)
{
// Put the endpoints into the bounding box:
double x1 = E.X;
double y1 = E.Y;
double x2 = x1, y2 = y1;
if (F.X < x1)
x1 = F.X;
if (F.X > x2)
x2 = F.X;
if (F.Y < y1)
y1 = F.Y;
if (F.Y > y2)
y2 = F.Y;
// Now consider the top/bottom/left/right extremities of the circle:
double thetaE = Math.Atan2(E.Y - C.Y, E.X - C.X);
double thetaF = Math.Atan2(F.Y - C.Y, F.X - C.X);
if (AnglesInClockwiseSequence(thetaE, 0/*right*/, thetaF))
{
double x = (C.X + radius);
if (x > x2)
x2 = x;
}
if (AnglesInClockwiseSequence(thetaE, Math.PI/2/*bottom*/, thetaF))
{
double y = (C.Y + radius);
if (y > y2)
y2 = y;
}
if (AnglesInClockwiseSequence(thetaE, Math.PI/*left*/, thetaF))
{
double x = (C.X - radius);
if (x < x1)
x1 = x;
}
if (AnglesInClockwiseSequence(thetaE, Math.PI*3/2/*top*/, thetaF))
{
double y = (C.Y - radius);
if (y < y1)
y1 = y;
}
return new Rect(x1, y1, x2 - x1, y2 - y1);
}
/// <summary>
/// Do these angles go in clockwise sequence?
/// </summary>
private static bool AnglesInClockwiseSequence(double x, double y, double z)
{
return AngularDiffSigned(x, y) + AngularDiffSigned(y, z) < 2*Math.PI;
}
/// <summary>
/// Returns a number between 0 and 360 degrees, as radians, representing the
/// angle required to go clockwise from 'theta1' to 'theta2'. If 'theta2' is
/// 5 degrees clockwise from 'theta1' then return 5 degrees. If it's 5 degrees
/// anticlockwise then return 360-5 degrees.
/// </summary>
public static double AngularDiffSigned(double theta1, double theta2)
{
double dif = theta2 - theta1;
while (dif >= 2 * Math.PI)
dif -= 2 * Math.PI;
while (dif <= 0)
dif += 2 * Math.PI;
return dif;
}
I tried to implement jairchu's answer, but found some problems, which I would like to share:
My coordinate system for the circle starts with 0 degrees at the right side of the circle and runs counterclockwise through the top (90deg), the left(180deg) and the bottom (270deg). The angles can be between 0 and 359,9999 deg.
The center point should not be part of the list of points
You have to distinguish between clockwise and counterclockwise arcs in order to make the list of points that lie on 0,90,180,270 deg
It is tricky to determine if the angle span includes the angle 0,90,180 or 270 deg.
public override Rect Box()
{
List<Point> potentialExtrema = new List<Point>();
potentialExtrema.Add(StartPoint);
potentialExtrema.Add(EndPoint);
if (!ClockWise)
{
if (EndAngle < StartAngle || EndAngle == 0 || StartAngle == 0 || EndAngle == 360 || StartAngle == 360)
potentialExtrema.Add(new Point(Point.X + Radius, Point.Y));
if ((StartAngle <= 90 || StartAngle > EndAngle) && EndAngle >= 90)
potentialExtrema.Add(new Point(Point.X, Point.Y + Radius));
if ((StartAngle <= 180 || StartAngle > EndAngle) && EndAngle >= 180)
potentialExtrema.Add(new Point(Point.X - Radius, Point.Y));
if ((StartAngle <= 270 || StartAngle > EndAngle) && EndAngle >= 270)
potentialExtrema.Add(new Point(Point.X, Point.Y - Radius));
}
else
{
if (StartAngle < EndAngle || EndAngle == 0 || StartAngle == 0 || EndAngle == 360 || StartAngle == 360)
potentialExtrema.Add(new Point(Point.X + Radius, Point.Y));
if ((StartAngle >= 90 || StartAngle < EndAngle) && EndAngle <= 90)
potentialExtrema.Add(new Point(Point.X, Point.Y + Radius));
if ((StartAngle >= 180 || StartAngle < EndAngle) && EndAngle <= 180)
potentialExtrema.Add(new Point(Point.X - Radius, Point.Y));
if ((StartAngle >= 270 || StartAngle < EndAngle) && EndAngle <= 270)
potentialExtrema.Add(new Point(Point.X, Point.Y - Radius));
}
double maxX = double.NegativeInfinity;
double maxY = double.NegativeInfinity;
double minX = double.PositiveInfinity;
double minY = double.PositiveInfinity;
foreach (var point in potentialExtrema)
{
if (point.X > maxX)
maxX = point.X;
if (point.Y > maxY)
maxY = point.Y;
if (point.X < minX)
minX = point.X;
if (point.Y < minY)
minY = point.Y;
}
return new Rect(minX, minY, maxX - minX, maxY - minY);
}
}
There is a more elegant solution determining wether 0,90,180 or 270 deg lie within the angle span:
public override Rect Box()
{
List<Point> potentialExtrema = new List<Point>();
potentialExtrema.Add(StartPoint);
potentialExtrema.Add(EndPoint);
if (AngleProduct(0))
potentialExtrema.Add(new Point(Point.X + Radius, Point.Y));
if (AngleProduct(90))
potentialExtrema.Add(new Point(Point.X, Point.Y + Radius));
if (AngleProduct(180))
potentialExtrema.Add(new Point(Point.X - Radius, Point.Y));
if (AngleProduct(270))
potentialExtrema.Add(new Point(Point.X, Point.Y - Radius));
double maxX = double.NegativeInfinity;
double maxY = double.NegativeInfinity;
double minX = double.PositiveInfinity;
double minY = double.PositiveInfinity;
foreach (var point in potentialExtrema)
{
if (point.X > maxX)
maxX = point.X;
if (point.Y > maxY)
maxY = point.Y;
if (point.X < minX)
minX = point.X;
if (point.Y < minY)
minY = point.Y;
}
return new Rect(minX, minY, maxX - minX, maxY - minY);
}
private bool AngleProduct(int alpha)
{
if (StartAngle == EndAngle)
if (StartAngle == alpha)
return true;
else
return false;
double prod = 0;
if (ClockWise)
prod = -1 * (alpha - StartAngle) * (EndAngle - alpha) * (EndAngle - StartAngle);
else
prod = (alpha - StartAngle) * (EndAngle - alpha) * (EndAngle - StartAngle);
if (prod >= 0)
return true;
else
return false;
}
© 2022 - 2024 — McMap. All rights reserved.