🔒 Locked

Area of circle within square

Started by DeathRay2K Jul 27, 2008 at 9:57 PM 17 replies 11.1k views

Original Post

Jul 27, 2008 at 9: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!

ibebrett

Jul 27, 2008 at 11: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

DeathRay2K

Jul 27, 2008 at 11: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.

jjanevski

Jul 28, 2008 at 12:02 AM

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 (r)
overlapping area = 0.5t*r^2

NOTE: This is in radians.

radians = pi / 180 degrees

DeathRay2K

Jul 28, 2008 at 12:12 AM

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.

oliii

Jul 28, 2008 at 2:53 AM

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.

Ravyne

Jul 28, 2008 at 3:25 AM

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.

AngleWyrm

Jul 28, 2008 at 3:30 AM

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]

grekster

Jul 28, 2008 at 6: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?

84r

Jul 28, 2008 at 10: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:
some cases

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:
some cases

...or by:

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

oliii

Jul 28, 2008 at 12:07 PM

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.

DeathRay2K

Jul 28, 2008 at 7: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. ;)

PDX_Catalyst

Jul 28, 2008 at 8: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.

Kaycon11

Jul 28, 2008 at 8: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.

PDX_Catalyst

Jul 28, 2008 at 8: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.

84r

Jul 29, 2008 at 5:35 PM

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.

Intersection of a line and a circle

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).

cignox1

Aug 1, 2008 at 1:08 AM

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....

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.