Started by Jul 27 2008 03:57 PM

,
18 replies to this topic

Posted 27 July 2008 - 03:57 PM

I'm trying to find the area of the portion of a circle within a square.
I'm doing this for a non-realtime rendering of 2D circles; I plan to use the area to calculate the antialiasing.
Unfortunately I really have no idea how to go about this, and the closest thing I've been able to find with Google is squares fully with circles, which is of course no help at all.
Any help would be much appreciated!

Posted 27 July 2008 - 05:41 PM

assuming im correctly interpreting your question..

area of a circle is pi*r^2

area of a square is w^2 where w = width and w = 2*r

so square = 4r^2

and circle is pi*r^2 so the ratio of a squares area to the area of the circle inside of it is (4r^2)/(pi*r^2) or 4/pi

area of a circle is pi*r^2

area of a square is w^2 where w = width and w = 2*r

so square = 4r^2

and circle is pi*r^2 so the ratio of a squares area to the area of the circle inside of it is (4r^2)/(pi*r^2) or 4/pi

Posted 27 July 2008 - 05:44 PM

I don't want the ratio of areas, I want to figure out how much of the circle is within the square.

This image shows what I mean; I would want to figure out the area of the darker region in this example:

You see, I don't want to figure out how much area a circle takes up in the square formed by its extremities, I want to know how much some circle overlaps some square, where the two have no relation at all.

This image shows what I mean; I would want to figure out the area of the darker region in this example:

You see, I don't want to figure out how much area a circle takes up in the square formed by its extremities, I want to know how much some circle overlaps some square, where the two have no relation at all.

Posted 27 July 2008 - 05:54 PM

How comfortable are you with integrals?

I would create a function to represent the circle and clamp it to the range [0,1] then integrate that function over the domain from [0,1] and the result would be exactly the area of the circle in that range. Let me work something out to start you off.

I would create a function to represent the circle and clamp it to the range [0,1] then integrate that function over the domain from [0,1] and the result would be exactly the area of the circle in that range. Let me work something out to start you off.

Posted 27 July 2008 - 06:02 PM

From your picture you can calculate the area of the overlapping square and circle like this:

* You know that every angle inside of a square is 90 degrees.

* You need to find the distance from the corner of the square that is inside the circle to the edge of the circle -- this will be your radius

So:

angle = 90 deg (t)

radius = point_2 - point_1 ®

overlapping area = 0.5t*r^2

NOTE: This is in radians.

radians = pi / 180 degrees

* You know that every angle inside of a square is 90 degrees.

* You need to find the distance from the corner of the square that is inside the circle to the edge of the circle -- this will be your radius

So:

angle = 90 deg (t)

radius = point_2 - point_1 ®

overlapping area = 0.5t*r^2

NOTE: This is in radians.

radians = pi / 180 degrees

Posted 27 July 2008 - 06:12 PM

The circle isn't necessarily (And certainly will very rarely be) aligned in any fashion with the square, so I can't simply figure out the radius around a corner, because the circle is unlikely to be perfectly aligned with a corner, or simply overlapping one corner.

I have little experience with integrals, but I am certainly happy to learn and attempt them if necessary.

I have little experience with integrals, but I am certainly happy to learn and attempt them if necessary.

Posted 27 July 2008 - 06:12 PM

So here is what I think may work:

function for a circle centered at (x0, y0) with radius r

You can then integrate this function over the range [0,1]. But since you only want the parts in the square you would clamp f(x) to the range [0,1].

something like this:

Though I think clamp needs a little work. it may be a bit different than that. Its pretty close I imagine.

Additions:

Basically it assumes that the lower left corner of the square is at the origin and the sides of length one. You can integrate over the x in the range zero to one.

The tricky part will to make sure the integral does not count any part of the circle that is completely above or below the pixel. This is what I was trying to accomplish with the clamp. Basically if the bottom edge of the circle is greater than one or the top edge of the circle is lower than zero for any given value of x, you will need to set the function to zero.

[Edited by - Lexdysic on July 28, 2008 12:12:51 AM]

function for a circle centered at (x0, y0) with radius r

f(x) = +-sqrt( r^2 - (x-x0)^2 ) - y0 and 0 where invalid

You can then integrate this function over the range [0,1]. But since you only want the parts in the square you would clamp f(x) to the range [0,1].

something like this:

area = integral( 0, 1, clamp( f(x), 0, 1 ) )

Though I think clamp needs a little work. it may be a bit different than that. Its pretty close I imagine.

Additions:

Basically it assumes that the lower left corner of the square is at the origin and the sides of length one. You can integrate over the x in the range zero to one.

The tricky part will to make sure the integral does not count any part of the circle that is completely above or below the pixel. This is what I was trying to accomplish with the clamp. Basically if the bottom edge of the circle is greater than one or the top edge of the circle is lower than zero for any given value of x, you will need to set the function to zero.

[Edited by - Lexdysic on July 28, 2008 12:12:51 AM]

Posted 27 July 2008 - 08:53 PM

How accurate and how fast does it have to be? You want a numerical method?

Else, you can use some rendering callbacks by rendering both, and give you the number of pixels overlapping.

Otherwise it will be quite complicated. My intuition says you'll have to clip the circle using the rectangle's plane, but I wouldn't know exactly how to derive the area for the clipped region, which would rely on integral calculus.

Else, you can use some rendering callbacks by rendering both, and give you the number of pixels overlapping.

Otherwise it will be quite complicated. My intuition says you'll have to clip the circle using the rectangle's plane, but I wouldn't know exactly how to derive the area for the clipped region, which would rely on integral calculus.

Posted 27 July 2008 - 09:25 PM

He mentions anti-aliasing, so I think he's looking for sub-pixel precision here.

The easiest solution may simply be to super-sample pixels on the edge of the mathematical circle, choosing enough samples to yield acceptable visual quality. Four or nine sample grids, 2x2 and 3x3 respectively, per pixel might be accurate enough for your needs. If not, you can subdivide greater powers of two, and trivially accept/reject entire blocks of sub-samples... Not sure how this compares speed-wise to a pure numerical function, but its worth investigating. I would think that an 16 sample, optimized test would be sufficiently fast and accurate for most needs, and it would probably lend itself well to parallelism and running on SSE or similar instruction sets.

The easiest solution may simply be to super-sample pixels on the edge of the mathematical circle, choosing enough samples to yield acceptable visual quality. Four or nine sample grids, 2x2 and 3x3 respectively, per pixel might be accurate enough for your needs. If not, you can subdivide greater powers of two, and trivially accept/reject entire blocks of sub-samples... Not sure how this compares speed-wise to a pure numerical function, but its worth investigating. I would think that an 16 sample, optimized test would be sufficiently fast and accurate for most needs, and it would probably lend itself well to parallelism and running on SSE or similar instruction sets.

Posted 27 July 2008 - 09:30 PM

- Get area of circle
- Multiply by fraction of circle covered by chord ( = area of pie slice)
- Subtract area of isosceles triangle ( = area of circular segment)
- Add area of right triangle

[Edited by - AngleWyrm on July 28, 2008 5:30:50 AM]

Posted 28 July 2008 - 12:01 AM

Quote:

Original post by AngleWyrm

- Get area of circle
- Multiply by fraction of circle covered by chord ( = area of pie slice)
- Subtract area of isosceles triangle ( = area of circular segment)
- Add area of right triangle

Wouldnt that fail if the circle intersected parallel edges of the square?

Posted 28 July 2008 - 04:14 AM

I think it would be easier to generalize this idea to triangles and make your rectangle out of two triangles. Then you have not so many cases of how the circle can intersect the rectangle. A sum of areas of triangles and integrals over a circle will give you the final result. Here I have drawn some possible cases one would need to deal with:

Or you could check for all possible cases of intersection between the square and the circle. In both cases you end up with a sum of triangle areas and circle portions. The area of the triangles is easy to calculate. Portions of a circle you can calculate either with an integral:

...or by:

Let me know if you need some help with the math.

Or you could check for all possible cases of intersection between the square and the circle. In both cases you end up with a sum of triangle areas and circle portions. The area of the triangles is easy to calculate. Portions of a circle you can calculate either with an integral:

...or by:

Let me know if you need some help with the math.

Posted 28 July 2008 - 06:07 AM

That seems like your best solution. The area of a polygon is easy to find, as is the cord(?) areas.

Finding the actual inner polygon isn't that hard if you know how to intersect a segment with a circle.

Finding the actual inner polygon isn't that hard if you know how to intersect a segment with a circle.

Posted 28 July 2008 - 01:10 PM

I think some of this stuff is a bit over my head, so for now at least, I've decided to simply supersample the edges, which gives me decent quality and great speed. It might not be as accurate as a strictly mathematical solution, but it's really quite fast, even with 16x16 samples (Though 4x4 usually seems to be good enough). Thanks for all the help! If I decide to go to something more advanced I expect I'll be asking again. ;)

Posted 28 July 2008 - 02:05 PM

Odd... this is the same sort of thing I've been trying to figure out all day. The question I posted elsewhere was this:

-------

Say you have a circle who's diameter is the same as the width of one quadrant. How would you find the area of this circle that falls into each quadrant if the circle's center point was not at the origin?

-------

Same basic problem. I'm good with the math I know, but my studies ended just before trig, so I'm clueless. Surely there's some formula which could take as input the x and y offset of the circle and assume the circle's diameter and the sides of each of the four boxes (quadrants) all equalled 1.

-------

Say you have a circle who's diameter is the same as the width of one quadrant. How would you find the area of this circle that falls into each quadrant if the circle's center point was not at the origin?

-------

Same basic problem. I'm good with the math I know, but my studies ended just before trig, so I'm clueless. Surely there's some formula which could take as input the x and y offset of the circle and assume the circle's diameter and the sides of each of the four boxes (quadrants) all equalled 1.

Posted 28 July 2008 - 02:10 PM

I just took a math class this past year and we totally did this stuff, I totally forget how to solve this, search on Google, there are steps and formulas to solve this.

Posted 28 July 2008 - 02:20 PM

Here's what I came up with...

(Look at AngleWyrm's picture to see what I mean...)

Find the area of the triangle that falls within the square.

Find the area of the circle segment, which is the rounded portion outside the triangle.

The formula for finding the circle segment can be found here:

http://www.mathopenref.com/segmentarea.html

I'm going to verify all of this, so this reply might get editted.

(Look at AngleWyrm's picture to see what I mean...)

Find the area of the triangle that falls within the square.

Find the area of the circle segment, which is the rounded portion outside the triangle.

The formula for finding the circle segment can be found here:

http://www.mathopenref.com/segmentarea.html

I'm going to verify all of this, so this reply might get editted.

Posted 29 July 2008 - 11:35 AM

Finding the intersection points of a line and a circle (2D) or sphere (3D) is useful in many situations. So I just wanted to post a function that finds those intersection points.

A and B are points of the line, P is the center of the circle.

The function is valid for 2D and 3D, and not optimized (const pointers to A and B). Having found the intersection points Q1 and Q2 one can find the "theta area" of the circle.

Now DeathRay2K found a good approximative solution, but the functions above would be the tools to find the correct area of the portion of a circle within a triangle (2 triangles = square). Of course it shouln't be done in real time. If someone is interested in finding this area I could post some code (~150 lines).

A and B are points of the line, P is the center of the circle.

int IntersectionLineSphere(vec *Q1, vec *Q2, vec A, vec B, vec P, float r)

{

vec pa = A - P;

vec ab = B - A;

float a = dot(ab,ab);

float b = dot(pa,ab);

float c = dot(pa,pa) - r*r;

float d = b/a;

float s = d*d-c/a;

if (s < 0.0f)

return 0; // sphere and line do not intersect

else

s = sqrtf(s);

float t1 = -d+s;

float t2 = -d-s;

*Q2 = A + ab * t1; // closer to B

*Q1 = A + ab * t2; // closer to A

int intersections = 0;

// intersection points within line segment?

if (t1 > 0.0f && t1 < 1.0f)

intersections++;

if (t2 > 0.0f && t2 < 1.0f)

intersections++;

// will be either 1 or 2

return intersections;

}

The function is valid for 2D and 3D, and not optimized (const pointers to A and B). Having found the intersection points Q1 and Q2 one can find the "theta area" of the circle.

float SegmentOfCircle(vec Q1, vec Q2, vec P, float r)

{

vec s1 = Q1 - P;

vec s2 = Q2 - P;

float costheta = dot(s1,s2)/(length(s1)*length(s2));

return 0.5f*acosf(costheta)*r*r;

}

float AreaOfTriangle(vec A, vec B, vec C)

{

vec s1 = B - A;

vec s2 = C - A;

vec cr = cross(s1,s2);

return 0.5f * length(cr);

}

Now DeathRay2K found a good approximative solution, but the functions above would be the tools to find the correct area of the portion of a circle within a triangle (2 triangles = square). Of course it shouln't be done in real time. If someone is interested in finding this area I could post some code (~150 lines).

Posted 31 July 2008 - 07:08 PM

There is also the sampling option: you generate many random samples in a shape that contains both the square and the circle. Then you count how many samples are inside the square, how many inside the circle and how many inside both. From that you can find the overlapping area...

I don't really think this is what you need, but I though to put it here nonetheless, you never know....

I don't really think this is what you need, but I though to put it here nonetheless, you never know....