Quadtrees For Spatial Partitioning

Introduction: -

In spatial partitioning representations, a solid is decomposed into a collection of adjoining, nonintersecting solids. A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split into four sub quadrants, etc. In the quadtree, a parent node represents the image, while four child nodes, in a predetermined order, represent the four quadrants.

The following are different spatial partitioning techniques:

1.Cell Decomposition

2.Spatial Occupancy Enumeration

3.Quadtrees and Octrees

4.Binary space partitioning Trees

Objective: -

To demonstrate the spatial partitioning technique using quadtrees.

Description: -

The project can be described as follows

Given a set of polygons obtain the spatial organization of the polygons.

Input: -

Set of vertex coordinates of the polygons.

Output: -

1. Display the input polygons.

2. Display the partitioned space.

This is just an example not the exact output of the partitioned space, still more partitioning required.

References:

1. Computer Graphics principles and practices by Foley (page no : 550).

2. http://www.delphi3d.net/articles/printarticle.php?article=octrees.htm

For more details, mail to deepti@cse.iitm.ernet.in