| 532 | |
| 533 | |
| 534 | private RNode<V> chooseLeaf(Vec v) |
| 535 | { |
| 536 | /* |
| 537 | * CL1 [Intialize ] Set N to be the root node |
| 538 | */ |
| 539 | RNode<V> N = root; |
| 540 | |
| 541 | /* |
| 542 | * CL2 [Leaf check ] If N 1s a leaf, return N. |
| 543 | */ |
| 544 | while(!N.isLeaf()) |
| 545 | { |
| 546 | /* |
| 547 | * CL3 [Choose subtree ] If N 1s not a leaf, |
| 548 | * (1) let F be the entry in N whose rectangle |
| 549 | * FI needs least enlargement to |
| 550 | * include EI. |
| 551 | * |
| 552 | * (2) |
| 553 | * Resolve ties by choosmg |
| 554 | * the entry with the rectangle of smallest |
| 555 | * area |
| 556 | */ |
| 557 | double leastEnlargment = N.children.get(0).bound.increasedArea(v); |
| 558 | int ind = 0; |
| 559 | for(int i = 1; i < N.children.size(); i++) |
| 560 | { |
| 561 | //Part (1) of CL3 |
| 562 | double nb = N.children.get(i).bound.increasedArea(v); |
| 563 | if(nb < leastEnlargment)//Found a better one |
| 564 | { |
| 565 | leastEnlargment = nb; |
| 566 | ind = i; |
| 567 | } |
| 568 | else if(nb == leastEnlargment)//Most likely when 2 or more rectangles intersect this new point |
| 569 | {//Part (2) of CL3 |
| 570 | //Only pic the new one if it has a smaller area |
| 571 | if(N.children.get(i).bound.area() < N.children.get(ind).bound.area()) |
| 572 | { |
| 573 | leastEnlargment = nb; |
| 574 | ind = i; |
| 575 | } |
| 576 | } |
| 577 | } |
| 578 | |
| 579 | /* |
| 580 | * CL4 [Descend until a leaf 1s reached.] Set |
| 581 | * N to be the cMd node pomted to by |
| 582 | * Fp and repeat from CL2 |
| 583 | */ |
| 584 | N = N.children.get(ind); |
| 585 | } |
| 586 | |
| 587 | return N; |
| 588 | } |
| 589 | |
| 590 | private RNode<V> splitNode(RNode<V> toSplit) |
| 591 | { |