Approximation of circle with rectangles
Quad tree is an interesting data structure. It is used for solving various geometrical problems, such as fast collision detection, indexing of geospacial data, etc. I am going to show how it might be used for approximation of different 2D shapes. (There is also 3D version of quad trees, called octal tree).
Let’s start with a final result of the algorithm:
Small white rectangles approximate circle’s border. Red rectangles form an inner area of the circle. Yellow does not belong to the circle and might be removed.
Building quad tree is simple. We start from the bounding rectangle. Then it will be split into four smaller rectangles of the equal size. Let’s say, input rectangle is defined by following points (x1,y1) -> (x2,y2). Then rules for splitting it into four smaller rectangles are following:
This procedure might be recursively applied to all leafs in the tree until new leaf rectangles reach certain size.
In order to make a decision if given leaf rectangle should be split, we need a function f, which for a given rectangle r will return how many of its verteces belong to the figure. There are obviously four cases:
For a circle, function f is quite simple:
There is a C# solution that shows this basic algorithm: Download.
By modifying function f, one can adopt this algorithm for other 2D figures.