Quadtree explanation and C implementation

Question

Please explain quadtrees and provide simple code (preferably in C) for insertion and searching.

Answer 1

Wikipedia has a good article on quadtrees. The quadtree section in these slides is very good.

Here are some C implementations (found via Googling for quadtree c -"c++" -"c#"):

• http://hyantes.gforge.inria.fr/doc/quadtree_8c-source.html
• http://xw2k.nist.gov/dads/html/quadtree.html
• http://www.informatik.uni-ulm.de/acm/Locals/1999/src/quadtree.C