Hints for using PM pseudocode

Now, naturally it's up to you to fill in the ellipsis (the parameter lists) with whatever you need. You will need info about the depth of tree, primarily, so you can figure out how to make the rectangles for the gray. Note that you don't necessarily have to store those regions. I do it as an efficiency issue (space vs. time). You could compute the rectangles on the fly each time, but I think that's wasteful; so I chose to store them.

Also note: the key to making your PM Quadtree a PM1, PM3, etc is the line in Black.add() regarding node validity :

  if (this node is valid) ...

This is the only part of the code that differs among the PM1 and PM3 (well, the ``validity check'' is done in the Gray.remove() also, but you get the idea). A PM3, for instance, is valid as long as it only has zero or one vertices in it. It is allowed to have any number of q-edges as long as they don't intersect each other. When you attempt to insert a second dot into this list, however, the node becomes invalid, and you must partition the node into 4 nodes, each corresponding to one fourth of the original block.

The key to doing this efficiently is to use OO design here. is key. There are some details I omitted from the pseudocode. For instance, the way I setup my code to allow for easily adapting the generic PM Quadtree into a PM1 and PM3 was not straight subclassing as you might expect. The reason for this becomes apparent when you try.

Suppose you subclass PMQuadtree into PM1Quadtree and PM3Quadtree. The problem here is that the PMQuadtree class is not the one that changes, its inner classes do. What you really need to subclass is the black and gray nodes, since they are the ones that contain the valid() code. The easiest way to do that to prevent you from having to rewrite the entire add() and remove() methods of Black and Gray respectively to change only a few of its lines would be to isolate the validation operation into a method, say valid(), that you can override and let dynamic dispatch handle it. But there's a problem with subclassing the inner classes.

The Gray and Black classes refer to each other. Also, presuming you write the methods for PMQuadtree itself (such as add, remove, etc. - I showed only the add and remove for the node classes), you will refer to Gray and Black by name in the base class. This former is really the bigger problem because, suppose you subclass Gray and Black and only change their valid() method, for instance in a PM1Gray and PM1Black class. If you only changed the PM1Black.valid() method, then when it calls partition() it will return a new Gray, not a new PM1Gray. You'd have to override that method to change the type it instantiates when it partitions, and now you'll quickly realize that you're rewriting the code.