Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for an algorithm to calculate the area of various shapes (created out of basic shapes such as circles, rectangles, etc...). There are various possibilities such as the area of 2 circles, 1 triangular and 1 square (intersections possible). As you can see this gets quite complicated and requires a numeric solution.

Of course, there are various special cases which can be calculated without any problems, but just as there are simple cases, there are also complex structures.

The only thing which comes to my mind is to write an algorithm which fills these geometrical structures with small squares and sums them up, but maybe there are already some smarter solutions.

Maybe I could also put the whole geometrical shape in a rectangle, and approximate the outlines of my shapes, and then calculate the area outside of my shape, and afterwards subtract the calculated area from the area of the rectangle.

I'm quite confident that these methods would work; it's just a matter of efficiency.

share|improve this question
3  
What is the data given? If you are given the boundary curves, then maybe you can look at how a planimeter works. –  Willie Wong Jul 11 '12 at 13:19
    
Boundary curves are not given (at least not always) but I'm positive I can calculate them or at least approximate them. –  user769 Jul 11 '12 at 13:27
    
@Layne: in that case, as long as you finely sample the boundary of your shape, you can get a good approximation to the area using the method I gave. –  J. M. Jul 11 '12 at 13:37

3 Answers 3

up vote 4 down vote accepted

If you don't mind using a probabilistic algorithm, have a look at Monte Carlo integration. It's easy to implement and fairly efficient.

For area calculation, it works like this:

  1. Choose some large number N.
  2. Set n := 0, s := 0.
  3. Choose a random point p.
  4. Set n := n + 1.
  5. If p is inside the shape, set s := s + 1.
  6. If n < N, go to 2.
  7. The area is approximately s/n.
share|improve this answer
3  
Step 5 is a lot harder to program than it seems! –  picakhu Jul 11 '12 at 12:39
3  
A past article in American Scientist suggests that the way in which you choose the random numbers can improve your results; in particular, they introduce "quasi-random numbers" which, from what I recall, somewhat avoid clumping and improve the area calculations. americanscientist.org/issues/pub/quasirandom-ramblings –  James Fennell Jul 11 '12 at 12:49
    
@picakhu You usually say find a function for the top and bottom parts of the shape, so then you can make an if structure. You should note, however, that this method is VERY inefficient. See en.wikipedia.org/wiki/Monte_Carlo_integration –  Argon Jul 11 '12 at 13:26
1  
@Argon, I feel that is easier said than done. Think about what happens if the shape is exceptially convoluted and includes spirals etc. –  picakhu Jul 11 '12 at 13:29
    
Assuming you have a random point $(x,y)$ and a function, $f(x)$, you simply need to see if $$y > f(x)$$ or $$y \le f(x)$$. If you need many functions to make the shape, it would be very difficult, indeed. –  Argon Jul 11 '12 at 13:31

If you can convert your "bizarre shape" into a (non-self-intersecting) polygon (possibly replacing circle arcs with polygonal approximations), one thing you can do to approximate the area is to use the formula for the area of a polygon, given the coordinates of the vertices (a.k.a. the "shoelace formula").

share|improve this answer
    
+1 for the idea, never even thought about it. If I could I would mark this also an answer. Whether I'll use this or the monte carlo integration depends on the efficiency. I'll compare shoelace formula and monte carlo and see what works best for me. –  user769 Jul 11 '12 at 16:54
2  
"Monte Carlo is an extremely bad method; it should be used only when all alternative methods are worse." ~ Alan Sokal –  J. M. Jul 11 '12 at 17:03
    
@Layne: it should be clear that this is a far more efficient and accurate way to go. The only hitch is that it is some work to set up, but that work is almost always a good investment. –  Ron Gordon Apr 4 '13 at 14:55

As a practical implementation of @J.M.'s suggestion, I just wanted to post a link to this paper. In the Appendix, my colleague and I derive the Fourier transform of a function $m(\mathbb{x})$, $\mathbb{x} \in \mathbb{R}^2$, defined as

$$m(\mathbb{x}) = \begin{cases}\\1 & \mathbb{x} \in \mathcal{P}\\0 & \mathbb{x} \not\in \mathcal{P} \end{cases}$$

where $\mathcal{P} \subset \mathbb{R}^2$ is a polygon defined by a set of vertices $\mathbb{x}_k$, $k \in \{1,2,\ldots,n\}$. In actuality, $\mathcal{P}$ may be an approximation to a bizarrely shaped region, in which more vertices suggests a better approximation.

(NB, the paper is directed to optical applications and so the scaling and notation is a little different than what you might see posted here. The math is the same, though.)

This formulation is closed-form and very easy to code.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.