| Hide textShow text Hide pseudo-codeShow pseudo-code | |
|
Insert the given points to the PR-quadtree. A quadtree is a structure for storing spatial objects for efficient search. The space is divided into four regions each time a new object is added to the structure. Each region corresponds to a node in a search tree. The root corresponds to the whole area and the depth in the tree tells the size of the corresponding region. Your task is to insert the points one by one to their correct nodes in the PR quadtree. Note that sometimes you need to move elements lower in the tree. An element can be moved in the tree with the mouse. There are four visualizations in the exercise. On the left the input stream is visualized both as an area and as a queue where the foremost element of the queue is shown. On the right is the PR-quadtree visualized both as an area and as a tree. Only the tree visualization can be modified. | 1. Let root be the root node of the PR-quad tree and p a point to be inserted 2. insert(root, p) INSERT(Node node, Point p) 1. if (node.isNotEmpty()) 2. SPLIT(node) 3. nextNode = CHOOSE_LEAF(node, p) 4. INSERT(nextNode, p) 5. else if (node.isLeaf()) 6. node.setKey(p) 7. else 8. nextNode = CHOOSE_LEAF(node, p) 9. INSERT(nextNode, p) SPLIT(Node node) 1. Split the region occupied by node into four equally-sized regions SW, NW, SE and NE. 2. Create four children for node and assign them to occupy the quadrants SW, NW, SE and NE in that order. 3. p = node.getKey() 4. node.deleteKey() 5. leaf = CHOOSE_LEAF(node, p) 6. leaf.setKey(p) CHOOSE_LEAF(Node node, Point p) 1. Let x be the child of node whose region contains p. 2. return x |