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/