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?
How to calculate aabb for a circle segment
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);
Author
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.
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
@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)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
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.
Author
You want all control points for each quadrant which is overlapping the start and end angle - that i know for sure.
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
