Cover circle with quads

Conceptually, I can think of two approaches to complete coverage. If you inscribe your circle in a square, you get maximal coverage with a minimum number of quads, but a very rough approximation. On the flip side, you can inscribe a square and then pad it out with infinitesimal trapzoids on each of the four sides to get perfect coverage but an infinite number of quads.

So what I suspect is a viable approach is to use a square that is somewhere between the inscribed and circumscribed sizes, and divide the remainder of the exposed circle into trapezoids based on how much error in the approximation you're willing to accept. The size of the central rectangle and the acceptable error would contorl the total number of quads, but basically this gives you 4n + 1 quads for a very good approximation with zero overlap.

You could modify the approach to use rectangles instead of trapezoids, and combine rectangles on opposite ends. This cuts the number of quads in half, at the cost of approximation accuracy and quite a bit of overlap.

I'm playing with some more diagrams but so far that's all I've got.

muahaha


We probably had greatly different requirements than you, but just felt like sharing that :P

I suggest you do what promit said, consider a box with side lenghts equal to the diameter of the circle and divide by the number of boxes you want to determine the box size. The more boxes you use, the more boxes you can reject, the more accurate the representation will be.

I realize now that our requirements are in fact COMPLETELY different.

You should be able to get by with 3 quads nicely. 1 all the way across, and one at the top and bottom, like a + sign. Or some arbitrary number of stacked rectangles.

  - -------- ---  -

[Edited by - bzroom on April 23, 2009 4:51:47 PM]

I had another, probably much better idea. If you inscribe the circle inside an 2*(N+1)-sided regular polygon, you can simply decompose it into N stacked trapezoids. That's a nice simple zero overlap coverage method and you can choose basically arbitrary levels of detail. It should require vastly less quads for a comparable level of detail than my original ideas, too.