# How to calculate aabb for a circle segment

This topic is 1086 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

i have a circle segment, defined with the following parameters:

- Center

How do i calculate an axis aligned bounding which will exactly fit the segment in?

##### Share on other sites

Hi,

i have a circle segment, defined with the following parameters:

- Center

How do i calculate an axis aligned bounding which will exactly fit the segment in?

cx, cy - center

here is important note depending on from where you start to draw and in which direction arc expands you may have to change that: it begins from right towards top,left 90 degrees.

vec2 p1 = vec2( cx + cos(start_angle)*radius, cy + sin(start_angle)*radius);
vec2 p2 = vec2( cx + cos(end_angle)*radius, cy + sin(end_angle)*radius);

'

now when you have thes two points

template <class T> T min(T a, T b)				{ return (a < b ? a : b); }
template <class T> T max(T a, T b)				{ return (a > b ? a : b); }

float minx = min(p1.x, p2.x);
float maxx = max(p1.x, p2.x);

float miny = min(p1.y, p2.y);
float maxy = max(p1.y, p2.y);

clock wise order starting from top left vertex

A = vec2(minx, maxy);
B = vec2(maxx, maxy);
C = vec2(maxx, miny);
D = vec2(minx, miny);
Edited by WiredCat

##### Share on other sites

Hi,

i have a circle segment, defined with the following parameters:

- Center

How do i calculate an axis aligned bounding which will exactly fit the segment in?

cx, cy - center

here is important note depending on from where you start to draw and in which direction arc expands you may have to change that: it begins from right towards top,left 90 degrees.

vec2 p1 = vec2( cx + cos(start_angle)*radius, cy + sin(start_angle)*radius);
vec2 p2 = vec2( cx + cos(end_angle)*radius, cy + sin(end_angle)*radius);

'

now when you have thes two points

template <class T> T min(T a, T b)				{ return (a < b ? a : b); }
template <class T> T max(T a, T b)				{ return (a > b ? a : b); }

float minx = min(p1.x, p2.x);
float maxx = max(p1.x, p2.x);

float miny = min(p1.y, p2.y);
float maxy = max(p1.y, p2.y);

clock wise order starting from top left vertex

A = vec2(minx, maxy);
B = vec2(maxx, maxy);
C = vec2(maxx, miny);
D = vec2(minx, miny);

This wont work when segments overlaps more than one quadrant.

##### Share on other sites

ah now i see. so for now i dont see any othe options rather than dividing segment fto each quadrant and calculating aabb for every quadrant then mixing that together

Edited by WiredCat

##### Share on other sites

@WiredCat:

The basic idea seems fine, maybe it just misses some extremes?

from math import pi, sin, cos

def xy(cx, cy, r, a):
"""
Return (x,y) position relative to (cx, cy), at r distance with an angle a
"""
return cx + r * cos(a), cy + r * sin(a)

def aab(cx, cy, r, sa, ea):
"""
Compute aabb for a circle segment around (cx, cy) with radius r, and
angle running from sa to ea.
"""
# Collect extrema: center, start and end of the circle segment.
points = [(cx, cy), xy(cx, cy, r, sa), xy(cx, cy, r, ea)]
# Collect extrema: Points at 0, pi/2, pi, and 1.5*pi if part of the segment.
for a in [0, pi/2, pi, 3*pi/2]:
if sa <= a <= ea: points.append(xy(cx, cy, r, a))

# Split point list into a list x coordinates and a list y coordinates.
xs = [x for x, y in points]
ys = [y for x, y in points]

# Return bounding box for all collected points.
return min(xs), min(ys), max(xs), max(ys)

##### Share on other sites

alberth for loop wont give you all points you will compute by segment, pi is more like infinite bumber and there exists infinite numbers between 0.00000000000000000000000000000001 0.0000000000000000000000000000000000000000000000001

##### Share on other sites

for loop wont give you all points

Indeed it does not, but if I understand the problem correctly, you don't need all points. Let me illustrate:

[attachment=30002:circle_segments.png]

A nice circle, with 4 test case segments in it.

First segment runs from point 0 clockwise to point 1, which results in the blue area.

Second segment runs from point 0 clockwise to point 2, which results in the blue + green area.

Third segment runs from point 0 clockwise to point 3, resulting in blue + green + red area.

Fourth segment runs from point 0 clockwise to point 4, resulting in blue + green + red + magenta area.

For the first segment, you don't need all points at the circle between points 0 and 1, since you only want the extreme values. Points 0, 1, and the center C are enough to derive the blue box.

This works until you cross a quadrant border. For example, from 0 to 2, you want to include points 0, 2, C, and also P, since its angle is part of the segment. The key notion here is that you are only interested in the extreme values rather than every value on the segment.

For 0 to 3 you want to add P and Q, and so on.

For this reason besides the center, start, and end point, I also loop over the 4 extreme points P, Q, R, and S. If their angle is part of the segment, the point is part of the segment, and it is included in the computation.

Edited by Alberth

##### Share on other sites

You want all control points for each quadrant which is overlapping the start and end angle - that i know for sure.

##### Share on other sites

Got a solution:

- Add circle center and start and point to a list of extreme points

- Find quadrant for start and end angle

- Loop through start to end quadrant, but dont increase quadrant, rather increase and mod by 4

- Make sure that you go at least one time into this loop, when both points are in the same quadrant

- In the loop determine which is the next quarant and add the point for the proper direction into the extereme points list

- Calculate aabb from extreme points list

Edited by Finalspace

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633691
• Total Posts
3013345
×