**0**

# Area of circle within square

###
#1
Members - Reputation: **100**

Posted 27 July 2008 - 03:57 PM

###
#2
Members - Reputation: **205**

Posted 27 July 2008 - 05:41 PM

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

###
#3
Members - Reputation: **100**

Posted 27 July 2008 - 05:44 PM

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.

###
#4
Members - Reputation: **197**

Posted 27 July 2008 - 05:54 PM

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.

###
#5
Members - Reputation: **200**

Posted 27 July 2008 - 06:02 PM

* 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

###
#6
Members - Reputation: **100**

Posted 27 July 2008 - 06:12 PM

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

###
#7
Members - Reputation: **197**

Posted 27 July 2008 - 06:12 PM

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]

###
#8
GDNet+ - Reputation: **2025**

Posted 27 July 2008 - 08:53 PM

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.

###
#9
GDNet+ - Reputation: **10555**

Posted 27 July 2008 - 09:25 PM

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.

###
#10
Members - Reputation: **554**

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]

###
#11
Members - Reputation: **640**

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?

###
#12
Members - Reputation: **160**

Posted 28 July 2008 - 04:14 AM

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.

###
#14
Members - Reputation: **100**

Posted 28 July 2008 - 01:10 PM

###
#15
Members - Reputation: **134**

Posted 28 July 2008 - 02:05 PM

-------

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.

###
#17
Members - Reputation: **134**

Posted 28 July 2008 - 02:20 PM

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

###
#18
Members - Reputation: **160**

Posted 29 July 2008 - 11:35 AM

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

###
#19
Members - Reputation: **723**

Posted 31 July 2008 - 07:08 PM

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