Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!sdd.hp.com!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!alberta!herald.usask.ca!ccu.umanitoba.ca!ccu.umanitoba.ca!lambert From: lambert@silver.cs.umanitoba.ca (Tim Lambert) Newsgroups: comp.graphics Subject: Re: Wanted: algorithm to compute intersection of square and circle Message-ID: Date: 26 Apr 91 01:56:33 GMT References: <1991Apr25.192400.8438@cfa203.harvard.edu> <1991Apr25.203916.11065@cs.ubc.ca> Sender: news@ccu.umanitoba.ca Organization: Department of Computer Science, University of Manitoba Lines: 33 In-Reply-To: mgobbi@cs.ubc.ca's message of Thu, 25 Apr 91 20:39:16 GMT >>>>> On Thu, 25 Apr 91 20:39:16 GMT, mgobbi@cs.ubc.ca (Mike Gobbi) said: > In article <1991Apr25.192400.8438@cfa203.harvard.edu> dp@cfa.harvard.edu (Dave Plummer) writes: >>I am looking for an algorithm that finds the area of intersection >>between a circle and a square of arbitrary position and size. Let's call the piece of a circle formed by cutting a piece of along a line a "segment" (is there an official name for this?) I've edited down Mike's method. > 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 > (c) intersect the circle at exactly two points, P & Q > In case (c) A := A - (segment) > repeat in a similar fashion for the other three sides of the square, > possibly reducing the value of A every time. The trouble with this is that after cutting off one piece what you have left is no longer a circle, and if on the next step you cut off a segment that intersects one that you already cut off, you will subtract the area of the intersection between the two segments twice. Hmmm.... Maybe you could fix this by adding the area of the intersection of two segents back on. You can easily detect this situation, because it only happens if you have a corner of the square inside the circle. Tim