[PythonCAD] Data structure question

Art Haas ahaas at airmail.net
Wed Aug 6 10:03:10 EDT 2003

On Sat, Aug 02, 2003 at 09:28:17AM -0500, Art Haas wrote:
> Hi.
> As inidicated in my last mail, I am looking at ways of storing the
> enties in a drawing in a better manner. After "Google"ing around I bit I
> found a number of papers dealing with things like R-trees, R*-trees, and
> PMR Quadtrees. The little bit I've read suggest that PMR Quadtrees would
> offer an improved means of storing the drawing objects, as this
> structure works by dividing up spatial regions and storing references to
> objects that are found in that region. In this manner it would be very
> quick to see if a mouse click is on a certain object because the
> spatial divisions occur when a certain number of objects are found in
> its boundary, so then that area of space is sub-divided into four
> smaller areas.

I've looked around for more info on quadtrees, and they seem to be
commonly used for storing and retrieving 2-D data. The papers I've found
discuss using these structures for applications that process data for
mapmaking and similiar large-scale data processing. Quadtrees also seem
to pop up in image enhancement applications as well.

I haven't been able to find anything Python related to quadtrees though,
so that is a bit discouraging. FYI, he Vaults of Parnassus link on the
Python home page has links to various Python web pages with lots of
example code, modules, and Python tips and techniques, so if you are
looking for some hints as to how to perform some task with Python, I'd
suggest browsing the link. Don't go there looking for quadtree info,
though ... 

I'd still like to hear from someone on the list who has any experience
with quadtrees as I've had no replies to my earlier posting. Thanks in

Man once surrendering his reason, has no remaining guard against absurdities
the most monstrous, and like a ship without rudder, is the sport of every wind.

-Thomas Jefferson to James Smith, 1822

More information about the PythonCAD mailing list