Jump to content
  • Advertisement
Sign in to follow this  
Finalspace

How to calculate aabb for a circle segment

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

 

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

 

- Center

- Start angle in radians

- End angle in radians

- Radius

 

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

Share this post


Link to post
Share on other sites
Advertisement

 

Hi,

 

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

 

- Center

- Start angle in radians

- End angle in radians

- Radius

 

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

 

 

 

 

cx, cy - center

r - radius

 

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 this post


Link to post
Share on other sites

 

 

Hi,

 

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

 

- Center

- Start angle in radians

- End angle in radians

- Radius

 

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

 

 

 

 

cx, cy - center

r - radius

 

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 this post


Link to post
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

 

checkcricle.png

Edited by WiredCat

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!