2
$\begingroup$

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.

  • 0
    @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.2012-07-11

3 Answers 3

1

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.

8

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

  • 0
    @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.2013-04-04
5

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.
  • 0
    @picakhu - All you have to do is parameterize each shape so that you can shrink its width to zero. Then the formula for defining the shape will also give you a bound for points inside. (For example, spirals can be constricted to a zero-width spiral; you can measure the distance from the point to the closest two spiral arms, and then see if it's within the width of either actual spirals at that distance.) It's not _completely_ trivial, but if you have to express the complex shape anyway you've usually already done most of the work.2012-07-11