2D bounding box of a sector?

Question

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?

Answer 1

• Generate the following points:
  • The circle's center
  • The positions of the start and end angles of the sector
  • Additionally, for the angles among 0, 90, 180, and 270 that are within the angle range of the sector, their respective points on the sector
• Calculate the min and max x and y from the above points. This is your bounding box

Answer 2

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.