Geometry!

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^

Andy Brummer

Simplification of my previous answer. First use symetry to consider only a 45degree/(pi/4) radian section. The solution can be applied ot other sections with various reflections about the axies. Assume box of side d and circle of radius r. The first box would intersect at r*r/sqrt(r*r-d*d). The entire strip would contain an area of asin(d). Subtract d*floor(r*r/sqrt(r*r-d*d)) to get the smaller box. So for box n it would be r*(asin(n*d)-asin((n-1)*d))-d*floor(r*r/sqrt(r*r-n*d*n*d)) for the simple case There is also a more complicated case where the circle actualy splits one of the edges. For the top square the formula is close: r(asin(n*d)-asin(intersection point))-((intersection point) -(n*d))*intersection height for the other part it would be r(asin(intersection point)-asin(n-1)*d))-d*floor(r*r/sqrt(r*r-n*d*n*d)) + d*(intersection point - n*d)) For both of those the intersetion point is r*sqrt(1-r*r/h) This would only work until you hit the 45 degree mark, and I did the integral correctly. That is for a 1 based index a zero based index has more n+1 terms then the 1 based index has n-1 terms. Whew. Corrected for formula for r and added additional cases for circle intersecting the bottom or top of the square.

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 19:19 Monday 8th May, 2006

Chris Losinger

Andy Brummer wrote:

Yeah, I suspect that this is for an anti-aliased rendering of a circle.

correct... rounded-rectangle, actually. but that's just a circle broken into quarters.

Andy Brummer wrote:

In that case an exact or even close to exact result is over kill.

you'd be surprised at how picky some people can be... :) i'd say it has to be 'right' within two decimal places to convince nit-pickers.

Andy Brummer wrote:

I'm sure there is a close enough algorithm that would work well enough.

if i could find it, i'd use it. but i've been searching for a while and came up empty. so, it looks like i have to do it the hard way... still it's an interesting (to me) problem regardless of the application. Cleek | Image Toolkits | Thumbnail maker

Brian R

Here is a site with general intersection algorithm implementations, including circle with a rectangle (slighly more general case of circle and square) www.geometrictools.com/Intersection.html C++ implementations.

Andy Brummer

I'd have to bust out with my handy Graphics programming in C from back in '88 and modify their circle alorithm by adding a little fuzzyness. It's good for the basics like that and even better for direct access of CGA, EGA and Hercules hardware for ultimate speed. I've been playing around with the anti-grain geometry library which will defnintely do it, I'd say look there to see how they do it, but I'd bet that code is obtuse and optimized.

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

yeah, i have some generic ellipse drawing code, but it's all integer math, so there aren't any good fractional values to use for anti-aliasing. Cleek | Image Toolkits | Thumbnail maker

Ryan Binns

The AGG library does antialiasing on circles using integer math and it's really high quality. I believe it also has a rounded rectangle class, although don't quote me on that...

Ryan

"Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"

code frog 0

Maybe I'm missing something but figure it out for one known circle and you have all of them. As the circle expands the number of squares encompassed by the circle will increase in proportion with those on the edge and outside (if the circle grows in a uniform expansion). You would just need to derive the area of the known circle, subtract it from the w*h of the square and this will give you a number. As the circle grows are shrinks that number should almost always be the same or very close.

The enemy's gate is down.:cool:
Welcome to CP in your language. Post the unicode version in My CP Blog [ ^ ] now.

People who don't understand how awesome Firefox is have never used CPhog. The act of using CPhog alone doesn't make Firefox cool. It opens your eyes to the possibilities and then you start looking for other things like CPhog and your eyes are suddenly open to all sorts of useful things all through Firefox. - (Self Quote)

Chris Maunder

And I thought trying to clarify the options of a weekly poll was hard... :rolleyes: cheers, Chris Maunder

CodeProject.com : C++ MVP

Chris Losinger

could be... i don't really know :) Cleek | Image Toolkits | Thumbnail maker

leppie

GraphicsPath c = new GraphicsPath();
c.AddCircle(rec);

GraphicsPath s = new GraphicsPath();
s.AddRectangle(rec2);

Region i = s.GetRegion().Intersect(c.GetRegion());

g.FillRegion(Brushes.Black, i);

Then simply count the black pixels :laugh::laugh::laugh:**

xacc.ide-0.1.3.12 - Now a whole lot faster (and better)
Consolas size screenshots (see how fractional font sizes look)

**