From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Area of Collection of Circles?
Date: 9 Sep 1995 16:28:58 GMT
In article <42etul$5ns@news.cs.tcd.ie>,
Jonathan Rice wrote:
>I need to calculate the area of a collection of intersecting circles.
>I haven't managed to find any refs on doing this, so I've written my
>own algorithm. However, the problem seems (just) sufficiently non-trivial
>that I do wonder what has been published on it. Does this ring a bell with
>anyone?
I first thought this problem was too cumbersome, but I've now decided it's
kind of cool. The area may be found without too much fuss using
Stokes' Theorem, but there's an easy geometric argument too. Here's both.
Let me suppose for simplicity that the boundary of this set is connected.
(Four barely touching circles leaving a curly diamond in the middle show
that this need not always be the case, but the general situation may be
handled with this technique too, assuming at least that there are only
finitely many circles involved.)
By Stokes' Theorem, the area of the region is the line integral
Integral -y dx
taken around the boundary counterclockwise. This integral is the sum of
the line integrals around each of the circular arcs. An arc from the
circle of radius r centered at P may be parameterized by
(x,y) = P + r (cos t, sin t)
so that the line integral is just
Integral -(P_y + r sin t ) ( - r sin t ) dt,
whose antiderivative is
-P_y r cos t + (r^2/2)( -sin t cos t + t)
Observe that evaluating this antiderivative at the endpoints t0 and t1
is for the most part quite easy if the Cartesian coordinates of the endpoints
of the arcs are known, since then (r cost t0) = x0 - P_x and
(r sin t0) = y0 - P_y; likewise for t1. Thus, when all the line integrals
are summed, the formula for the area will be a quadratic polynomial in
the Cartesian coordinates of the endpoints of the arcs and the centers of
the circle, except for the terms r^2/2 t in each line integral.
I suppose it is most straightforward as a computational matter to
compute the t coordinates for both endpoints and subtract, but it is
perhaps of theoretical interest to note that r t1 - r t0 is the length
of the arc. So for example if all the circles have the same radius r,
then these terms just sum to (r/2)*(circumference of the figure).
As is often the case with Stokes' theorem, it is possible after the
work is done to reinterpret the result differently: the area of the union
is the area of the polygon traced out by the arc endpoints, together
with the areas of the circular sections sticking beyond that polygon.
The quadratic polynomial described above measures the area of the
polygon (and so the P's ough to drop out) and the arc-length part
measures the areas of the circular sections.
dave
==============================================================================
To: Jonathan.Rice@tcd.ie, rusin@washington.math.niu.edu
Subject: Area of Collection of Circles?
Date: Wed, 13 Sep 1995 17:20:58 -0700
From: David Eppstein
>I need to calculate the area of a collection of intersecting circles.
>I haven't managed to find any refs on doing this, so I've written my
>own algorithm. However, the problem seems (just) sufficiently non-trivial
>that I do wonder what has been published on it. Does this ring a bell with
>anyone?
I assume that what you want is the area of their union?
This can be found efficiently by a method of Edelsbrunner,
involving constructing a generalized Delaunay triangulation
and using a simple inclusion-exclusion formula with
terms coming from the features of the triangulation.
(You need to combine areas of intersections at most 3 circles).
Similar techniques generalize to higher-dimensional unions of balls.
The reference is:
H. Edelsbrunner, The Union of Balls and its Dual Shape,
9th ACM Symp. Computational Geometry, 1993, pp. 218-231.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/