Манефестирующий генератор (da_forever) wrote in algorithms,

Divide a circle

Hi!
I've been member of this community for quite time, and now I need some advise.

Question is how do I devide given circle with radius R into N vertical segments with same area?
And by vertical I mean that devising lines should be parralell to the diametr line of that circle. One more thing - N is always even. Simple example is N = 2 : and we have circle divided vertically into two parts of equal area with deametr line.

I need this to speedup my litlle research on mathematical statistics with parallel GPU eval.

Any help In form of formula, or ref to the known algorithm (if it does exists) or some code on almost any programming language would be g8.

UPD
Illustration added. Case: R=1 N=6, areas of all segments are equal.
I need to know OX points marked with question marks.
Photobucket
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 7 comments

pstscrpt

May 11 2011, 14:30:38 UTC 3 years ago

The even number of parts means you're really just splitting half the circle. The top and bottom are the same, so you're left with a function for the arc in one quadrant -- if I'm remembering right, the formula for a circle centered at the origin is x^2 + y^2 = radius, so the function for the arc would be y=abs(sqrt(r-x^2)).

From there, the right answer from a math perspective would be to do the calculus to figure out the area of each section, and then algebra to see what value makes them even. Since I took Calc 2 sixteen years ago, I can't begin to do that anymore.

If this is for computer graphics, you're likely dealing with pixels, and you can just count a single pixel as one square unit and increase X by one pixel at a time until you pass the right fraction of the area.

lucky__man

May 11 2011, 14:44:08 UTC 3 years ago

Find once correct Yi values (assuming the diameter is Y=0) for every possible N, create a lookup table and use it later.

In order to find Yi you should solve equation 0.5*(x-sin(x))=a for some known a. It could be done by any convergence method: Newton, bisections, etc. "x" is the angle, Yi = cos(x) or something like this.
http://en.wikipedia.org/wiki/Arc_(geometry)

da_forever

May 11 2011, 18:28:21 UTC 3 years ago

Yup, already got it. I wanted more elegant and efficient way to do it. Thx anyway.

BTW www.gil-algorithms.com are kick-ass project. Envy you -)

lucky__man

May 12 2011, 10:25:44 UTC 3 years ago

Thank you very much! BTW, you are welcome to apply (we are expanding)
"Elegant" and "efficient" are often contradict to each other :)

Newton search is extremely fast, I think you will find Yi for N=1928474 with ease after 10-15 iterations. As far as I remember solving this problem analytically require using Elliptic integrals. They are extremely elegant but not so easy to program, and I am not sure the calculation will be faster than a primitive Newton convergence method.
http://en.wikipedia.org/wiki/Elliptic_integral

da_forever

May 11 2011, 14:53:41 UTC 3 years ago

It's not a graphics, it's a calculus, so I need my areas pretty close to equal. And perception must be much higher than in graphics.

Your solution are very close to what I've been thinking of. This is a good way, but it takes to mutch calculation to figure out what is values to, let's say 192 equal parts of circle. Shurly I have to figure out only 95 of them, but still.

In fact I'm looking for some elegant mathematical solution with minimal iterations count.

Deleted comment

da_forever

May 11 2011, 18:03:48 UTC 3 years ago

Actually only one point per vertical line - point of crossing with OX.
Please see post update.

Deleted comment

Oh, what a gr8 pls!

da_forever

July 9 2011, 05:02:49 UTC 3 years ago

Even robos here are interested in man.
Sand me 13 solved capthcas and we well talk about this -)