

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

I've a need to compute the area of single elements (dice) of a matrix like this:


The matrix is composed by 'c' columns and 'r' rows and every element/rectangle has the same height and width of any other.

knowing the element (x,y) center, I can know if its vertex are: - All out of circle area - All inside the circle area or - Partially inside the circle area (ray = 75.000 micron)

My problem is how I can compute the area of dice that are intersectated by the circle and more in deep how I can can compute the area of the portion of dice dice inside the circle.

So, to make an example, to work on, I've a dice with

 CenterX , CenterY               [  29870.4 ,  67144.9 ]
 DieDimensionX, DieDimensionY    [  5430.52 ,  4320.54 ]
 Coord of upper left corner (A)  [ 27155.14 , 69305.17 ]
 Coord of upper rightcorner (B)  [ 32585.66 , 69305.17 ]
 Coord of lower left corner (C)  [ 27155.14 , 64984.63 ]
 Coord of lower right corner (D) [ 32585.66 , 64984.63 ] 

For each coord I've computed the segment lenght from axis origin and 1 corner (on 4) is out of circle:


 A: 74435.261920332
 B: 76583.495783129    == >75.000 
 C: 70430.133924738
 D: 72696.81818259

Which is the area of this dice inside the circle? Or else: which is the percentage of the area of dice inside the reticule compared with a full dice? I've read something about 'Simpson rule' that could help me but I don't know (a) if this is the correct approach (b) neither how to apply it on my example.

Thanks to anyone that would be able to help me.

Ciao, Stefano

share|improve this question
up vote 1 down vote accepted
  • Simplest and probably the most time consuming method - find out the points of intersection by solving for the line equations and the circle equation and then find out the area of the triangle formed by these points and the corner of the rectangle inside the circle. This way you will get the fraction of area of a rectangle inside the circle.
  • Consider a rectangle. The 4 coordinates of the corners are known. Solve for the circle eq. arranged as F(x,y) = (x-a)^2 + (y-b)^2 - r^2 If F < 0 (let it be p) that coordinate is inside the circle. If F > 0 (let it be q), it is outside the circle. You can calculate an approximation for the intersection point by using section formula for these coordinates using the ration obtained from abs(p/q).
  • Approximate the circle eq. by the eq. of it's tangent for a rectangle using CenterX of that rect.
  • You can use bisection method reliably here to solve for x coordinate (y coord. is know when considering line parallel to x-axis). You know which coord is inside circle and which is outside i.e. values of xcoord for which the eq. of circle is +ve and -ve.
share|improve this answer
Thx Colorless Photon. Is this the unique approach? Or better: for dice on very left or right site of the circle, intersected having 2 corners out of circle, I cannot use it. isn't it? For such cases I have to consider that area as a trapezoid and then use a different formula to compute its area. To reply to my 2nd question: the "Simpson rule" cannot be an alternative and available purpouse? – Stefano Radaelli Jul 4 '13 at 17:26
@StefanoRadaelli Yes. When there is one corner inside the circle, you can consider the area of a triangle. If you have two corners consider area of trapezoid. If you have 3 corners, find out the area not inside the circle i.e. area of triangle outside and subtract that from the rect area to get area inside. – Colorless Photon Jul 4 '13 at 17:36
@StefanoRadaelli You could also use Simpson's rule. In that case, you would need 3 nodes. You can consider 2 of those nodes to be the points of intersection and the third node as the midpoint of these 2. You would have to shift the axes however before you could use the formula. But on the pro side, you would not have to bother about the shape formed by area of rect. inside the circle. – Colorless Photon Jul 4 '13 at 17:46

Your Answer


