PM1 Quadtree

The previous version of this specification gave a 1x1 limit on cell partitioning. In retrospect this seems rather silly, as it does nothing to decrease the complexity of the project while basically crippling your implementation. Not that you'll ever want to use a quadtree in real life, but if you did you probably would not want an arbitrary 1x1 limit. Instead, the INIT_QUADTREE function will be modified to take 3 arguments from the user- the size of the tree, the maximum recursion depth before aborting an insert, and the minimum distance between two lines at which point they should be considered to be intersecting. The last two parameters are mostly redundant, but I am including both explicitly so that you can chose which one to use. The purpose of the third parameter is to allow efficient intersection detection. Ideally, if an insert is going to fail it would be better to discover this before you start to modify the current tree. One acceptable way to do this is with a "trial run" before your actual insert. Basically, you use your insert algorithm to visit all the leaf nodes that the new segment will be inserted into, and then you check for intersection with the elements in those leaves. If you find an intersection (or two segments which are close enough together to be considered intersecting) then you abort. Otherwise you can procede with an unchecked insert since you know that no intersections will occur. There are tradeoffs between this and the "maximum depth rule". This method will add a certain overhead (extra intersection checking) to legal inserts. This would be especially bad if the user had specialized data that he knew a priori (ahead of time) would never contain interesections. If intersections are expected with some frequency, however, this extra check may present a significant overall speedup. You might consider a hybrid approach, where you only explicity check for intersections after a certain number of splits, or at a certain depth in the tree. Or you might not ;) As a side note, in the spirit of being generic, I recommend that you try to build your tree so that it can handle floating point coordinates as well as integer coordinates (even though Dots will always be integers). I am mandating that we all build our trees in a standardized way, so that the structure appears identical. Your tree and nodes will have to follow the following standard rules:

1. No two points can fall in the same node
2. A point cannot be contained in the same node as a segment, unless that point is an endpoint of that segment.
3. No two segments can fall in the same node, unless they intersect at a shared endpoint *and* that endpoint is contained in the *same* node.
4. If a point falls on the boundary between more than one node, then it must be added to every node that it intersects (a point may be contained in up to four leaf nodes).
5. If a single point of a segment falls on the boundary of more than one node then it must be added to all of those nodes as above. (A single segment can of course appear in a *lot* of nodes).
6. The tree must at all times be minimal- that is, there must never be a smaller tree which follows all of the above rules and still contains all of the same data. This should only be a complicated issue during deletion.

In no case should you try to attempt to solve any pm1 problems with brute force. All that is generally required is logical pruning- ie. "If the segment does not overlap my southeast child, then don't try adding it to that child!" And oh yes, unlike in the book, *our* skiplists have (0,0) at the southwest corner and *not* the northwest corner(the inverted coordinate system used by your monitor and most graphics apps). Since there are a lot of complexities in how you build your quadtree there will be less stringent speed requirements then there were in P1. Still, try to make it as efficient as you can! There will still be benchmarks, and many kudos at least for the fastest implementations(maybe extra credit, but I have no say in that). Don't brute force, please? :) That should be all you need to know to build a quadtree!

Web Accessibility