Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • World
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor
  • Default (No Skin)
  • No Skin
Collapse
Code Project
CODE PROJECT For Those Who Code
  • Home
  • Articles
  • FAQ
Community
  1. Home
  2. The Lounge
  3. Geometry!

Geometry!

Scheduled Pinned Locked Moved The Lounge
comdata-structureshelpquestion
30 Posts 11 Posters 0 Views 1 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • M 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

    R Offline
    R Offline
    Raj Lal
    wrote on last edited by
    #20

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

    1 Reply Last reply
    0
    • C 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

      A Offline
      A Offline
      Andy Brummer
      wrote on last edited by
      #21

      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

      1 Reply Last reply
      0
      • A 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

        C Offline
        C Offline
        Chris Losinger
        wrote on last edited by
        #22

        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

        A 1 Reply Last reply
        0
        • C 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

          B Offline
          B Offline
          Brian R
          wrote on last edited by
          #23

          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.

          1 Reply Last reply
          0
          • C 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

            A Offline
            A Offline
            Andy Brummer
            wrote on last edited by
            #24

            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

            C 1 Reply Last reply
            0
            • A 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

              C Offline
              C Offline
              Chris Losinger
              wrote on last edited by
              #25

              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

              R 1 Reply Last reply
              0
              • C 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

                R Offline
                R Offline
                Ryan Binns
                wrote on last edited by
                #26

                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"

                1 Reply Last reply
                0
                • C 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

                  C Offline
                  C Offline
                  code frog 0
                  wrote on last edited by
                  #27

                  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)

                  1 Reply Last reply
                  0
                  • M 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

                    C Offline
                    C Offline
                    Chris Maunder
                    wrote on last edited by
                    #28

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

                    CodeProject.com : C++ MVP

                    1 Reply Last reply
                    0
                    • R Raj Lal

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

                      C Offline
                      C Offline
                      Chris Losinger
                      wrote on last edited by
                      #29

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

                      1 Reply Last reply
                      0
                      • C 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

                        L Offline
                        L Offline
                        leppie
                        wrote on last edited by
                        #30

                        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)

                        **

                        1 Reply Last reply
                        0
                        Reply
                        • Reply as topic
                        Log in to reply
                        • Oldest to Newest
                        • Newest to Oldest
                        • Most Votes

                        • Login
                        • Don't have an account? Register
                        • Login or register to search.
                        • First post
                          Last post
                        0
                        • Categories
                        • Recent
                        • Tags
                        • Popular
                        • World
                        • Users
                        • Groups