Geometry!

Chris Losinger

here's a puzzle... 1. you have a piece of graph paper. 2. on that graph paper, there is circle of radius r, centered at the (0,0). 3a. some squares on the graph paper will lie completely inside the circle. 3b. some will lie completely outside the circle. 3c. some will have only a fraction of their area inside the circle (these are squares where the circle passes through the square on two sides). the problem: how can you determine the area that the circle occupies inside an arbitrary square ? Cleek | Image Toolkits | Thumbnail maker -- modified at 17:42 Monday 8th May, 2006

Raj Lal

Chris Losinger wrote:

inside an arbitrary square

which sqr and how will that affect the area of circle. can you add a picture to make it clear --- My Unedited article^

Daniel Turini

Chris Losinger wrote:

how can you determine the area that the circle occupies inside an arbitrary square ?

The radius (R) will be half the side of the square. So, A=Pi * R * R From the Churchdown Parish Magazine: "Would the Congregation please note that the bowl at the back of the Church, labelled 'For The Sick,' is for monetary donations only."

Andy Brummer

Chris Losinger wrote:

how can you determine the area that the circle occupies inside an arbitrary square ?

Calculus.

I can imagine the sinking feeling one would have after ordering my book, only to find a laughably ridiculous theory with demented logic once the book arrives - Mark McCutcheon

Chris Losinger

Quartz... wrote:

which sqr

any square. you have a circle on a piece of graph paper. pick any square - it can be inside the circle, outside the circle, or the circle can pass through it (in which case there will be some fraction inside and 1 - (that fraction) outside). the first two cases are easy. the question is really : how to find the area that the circle covers, in squares where the circle passes-through ? Cleek | Image Toolkits | Thumbnail maker -- modified at 17:18 Monday 8th May, 2006

Chris Losinger

Did I understand it right:? i don't think so. ;) Cleek | Image Toolkits | Thumbnail maker

Michael A Barnhart

My first engineering response is to ask what accuracy is needed. If not a purist question. (i.e. I could allow the circle to be the approximation of the line segments connecting the intersection of the radius to lines that formed boundaries of lines of squares.) Then I would considers rectangles of width R and height y (the edge one square.) x the intersection point would be sqrt(R^2 - (ny)^2) where n went from 0 to R/2y. I would only do this for 0 to 45 degrees. Again accuracy needs; if simplistic you could average the values of the top and bottom. If a purist question then first need to decide the accuracy of PI needed which is an approximation. So you will never be exactly correct, Admit it. (ok this is Chris, correct my spelling :) -- modified at 17:35 Monday 8th May, 2006

Marc Clifton

I can understand clearly all the steps, but I can never understand "the problem"? It seems this is a common thing when I read these math puzzles. Everything is clear until the problem. I've had this problem since they gave me these things in school. For example:

Chris Losinger wrote:

how can you determine the area that the circle occupies inside an arbitrary square ?

The circle isn't inside an arbitrary square. That doesn't make any sense! And what you mean, arbitrary square? A square where? Inside the circle? Outside the circle? How can an individual square tell you anything about the area of the circle? Because, you see, when you say "graph paper", I'm imagining all these little arbitrary squares. Marc Pensieve Some people believe what the bible says. Literally. At least [with Wikipedia] you have the chance to correct the wiki -- Jörgen Sigvardsson -- modified at 17:43 Monday 8th May, 2006

Andy Brummer

Forum bug. I replied to myself. You can get the intersection of the circle with the lines making the boxes by substituting the x or y value of the side into the equation x*x+y*y=r*r and solving for the other value. That will tell you if you are entirely in our out of the square and where the intersection point is. If you don't care about accuracy you can estimate the area as a triangle or quatralateral with straight sides based on the intersection. If you need an exact result you can reduce the problem to finding the area under a section of the curve 1/sqrt(r*r-x*x), which I think is r*(asin(a)-asin(b)) where a and b are the start and end points of the section. If you are doing this to draw a anti-aliased circle, there has got to be some simple algorithm out there to do this. [edit]Left off the factor of r for the area calculation[/edit]

I can imagine the sinking feeling one would have after ordering my book, only to find a laughably ridiculous theory with demented logic once the book arrives - Mark McCutcheon

-- modified at 17:53 Monday 8th May, 2006

Chris Losinger

Marc Clifton wrote:

The circle isn't inside an arbitrary square.

no, it isn't. i'll try to explain it better: 1. get some graph paper[^]. see all the squares between the lines ? those are the squares i'm talking about. 2. draw a circle with radius 10. 3. now, some of those graph paper squares are inside the circle you just drew, and some are outside. and the squares where the circle passes-through have some area that is inside the circle, and some area that isn't.

Marc Clifton wrote:

I'm imagining all these little arbitrary squares.

arbitrary in the sense that your 'solution' should be able to give the area of the (graph paper) square that's occupied by the circle, no matter which (graph paper) square i point at. or: for all x,y, how much of the square (x,y,x+1,y+1) is covered by the circle ? so, the 'problem; is to find a way to know what percent of a square is covered by the circle. Cleek | Image Toolkits | Thumbnail maker -- modified at 17:52 Monday 8th May, 2006

Michael A Barnhart

Andy Brummer wrote:

into the equation x*x+y*y=r*r

Umm, "sqrt(R^2 - (ny)^2)" was in my explaination.

Andy Brummer

Sorry about that. I replied to myself and the forum stuck it under your correct response. Let's see where this one ends up.

I can imagine the sinking feeling one would have after ordering my book, only to find a laughably ridiculous theory with demented logic once the book arrives - Mark McCutcheon

Marc Clifton

Chris Losinger wrote:

should be able to give the area of the (graph paper) square that's occupied by the circle

It would be more accurate to say, the area of square bounded by inner edge(s) of the square and the arc of the circle, bounded by the radius segment on the extents of the square. Or something like that. But when you say "occupied by the circle", I really don't know what you mean. If you had said "arc", I would have understood a lot better. In any case, it area of the square depends on the size of the squares on your graph paper. So you need to know that too. Marc Pensieve Some people believe what the bible says. Literally. At least [with Wikipedia] you have the chance to correct the wiki -- Jörgen Sigvardsson

Michael A Barnhart

NO problem. Again what is this really for. If a simple approximation then you can do a step approximation and be fairly simple and quick. If really exact then the biggest issue is handling squares who have a corner cut off (inside or outside). The case where you have an arc going side to side (or top to bottom) is much simpler. You still have to work out the condition each square sees. Usually much more work than it is worth. I guess this is a soapbox issue of mine; designers insisting on exact answers when it is impossible to manufacture the part anywhere close to what they insist the design accuracy must be (and hence much higher costs.) "Every new day begins with possibilities. It's up to us to fill it with things that move us toward progress and peace.” (Ronald Reagan)

Michael A Barnhart

Marc Clifton wrote:

depends on the size of the squares

You may assume the squares have an edge length of "y". "Every new day begins with possibilities. It's up to us to fill it with things that move us toward progress and peace.” (Ronald Reagan)

Raj Lal

is the solution in geometry ? --- My Unedited article^

Andy Brummer

Yeah, I suspect that this is for an anti-aliased rendering of a circle. In that case an exact or even close to exact result is over kill. I'm sure there is a close enough algorithm that would work well enough.

Michael A. Barnhart wrote:

I guess this is a soapbox issue of mine; designers insisting on exact answers when it is impossible to manufacture the part anywhere close to what they insist the design accuracy must be (and hence much higher costs.)

I would have thought that most designers and engineers would look at the tolerences of materials and equipment vs. cost and take that into account with their design. But then again people assume that software is actually built based on plans and specs. My only experience with that type of thing was using a machine shop to build parts for a physics experiment. Working with lathes and milling machines to build custom precision parts was a lot of fun.

I can imagine the sinking feeling one would have after ordering my book, only to find a laughably ridiculous theory with demented logic once the book arrives - Mark McCutcheon

-- modified at 18:13 Monday 8th May, 2006

Raj Lal

if the area of the arc which you are looking for it will be ( Pi * r * r) - sqrt(2 * r * r) Area of the circle minus the area of the square which is made by joining the perpendicular diameter EDGES of the circle. And also the area of the circle will always be pi * r * r, no matter how many squares it includes or touches or cuts or what ever. --- My Unedited article^ -- modified at 18:25 Monday 8th May, 2006

Chris Losinger

Marc Clifton wrote:

In any case, it area of the square depends on the size of the squares on your graph paper. So you need to know that too.

physical units aren't important. assume each square is 1x1. Cleek | Image Toolkits | Thumbnail maker

Raj Lal

MORE EXACT VALUE OF PI HERE >[^] :cool: --- My Unedited article^