Newsgroups: comp.graphics
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!mgobbi
From: mgobbi@cs.ubc.ca (Mike Gobbi)
Subject: Re: Wanted: algorithm to compute intersection of square and circle
Message-ID: <1991Apr25.203916.11065@cs.ubc.ca>
Sender: usenet@cs.ubc.ca (Usenet News)
Organization: University of British Columbia, Vancouver, B.C., Canada
References: <1991Apr25.192400.8438@cfa203.harvard.edu>
Date: Thu, 25 Apr 91 20:39:16 GMT

In article <1991Apr25.192400.8438@cfa203.harvard.edu> dp@cfa.harvard.edu (Dave Plummer) writes:
>I am looking for an algorithm (C or Fortran code would be nice) that
>finds the area of intersection between a circle and a square of arbitrary
>position and size.  After thinking about it for a few minutes I realized
>that this is more complicated than it sounds.
>
>The intersecting area will vary from zero (no overlap) to the full area of
>the circle or square (one enclosed by the other).
>
>Please post any suggestions, references or code or e-mail them to:
>dp@cfa.harvard.edu
>
>- Dave Plummer


Here's a thought (I presume that you just want a number -- not a polygon):

Start with the area of the circle.  Call it A.

Take the "top" edge of the square and extend it into a line.  This line
will either
  (a) pass "below" the circle (tangency counts as a miss)
  (b) pass "above" the circle (ditto)
  (c) intersect the circle at exactly two points, P & Q

In case (a) A := 0
        (b) A := A
        (c) A := A - (pie + wedge) where
            conect P & Q to center of circle (point C)
            pie = area of pie-shape bounded by circumference, PC, QC and
                  lying "above" the line.
                  (this is an easily-computed fraction of the circle)
            wedge = area of triangle PCQ

repeat in a similar fashion for the other three sides of the square,
possibly reducing the value of A every time.


Note that this algorithm should work on a circle & any convex polygon, not
just squares.  As I said earlier, it won't give you the closed curve defined,
just the area (though it should be fairly simple to modify it to save the
points of intersection and determine which path (curved or straight) is the 
bound).


--
     __
    /..\      In quest of knowledge...
 --mm--mm--         Mike Gobbi