| 588 | } |
| 589 | |
| 590 | private RNode<V> splitNode(RNode<V> toSplit) |
| 591 | { |
| 592 | //Quadratic Split |
| 593 | /* |
| 594 | * [Pick first entry for each group ] |
| 595 | * Apply Algorithm PickSeeds to choose |
| 596 | * two entries to be the first elements |
| 597 | * of the groups Assign each to a |
| 598 | * group |
| 599 | */ |
| 600 | double d = Double.MIN_VALUE; |
| 601 | int e1 = 0, e2 = 0; |
| 602 | //PickSeeds |
| 603 | /** |
| 604 | * PSl [Calculate inefficiency of grouping |
| 605 | * entries together] For each pair of |
| 606 | * entries El and E2, compose a rectangle |
| 607 | * J including El I and E2 I Calculate |
| 608 | * d = area(J) - area(El I) - area(E2 I) |
| 609 | */ |
| 610 | for(int i = 0; i < toSplit.size(); i++) |
| 611 | for(int j = 0; j < toSplit.size(); j++) |
| 612 | { |
| 613 | if(j == i) |
| 614 | continue; |
| 615 | Rectangle E1Bound = toSplit.nthBound(i); |
| 616 | Rectangle E2Bound = toSplit.nthBound(j); |
| 617 | Rectangle J = new Rectangle(E1Bound, E2Bound); |
| 618 | double dCandidate = J.area() - E1Bound.area() - E2Bound.area(); |
| 619 | if(dCandidate > d)//PS2 [Choose the most wasteful pm ] Choose the pair with the largest d |
| 620 | { |
| 621 | e1 = i; |
| 622 | e2 = j; |
| 623 | d = dCandidate; |
| 624 | } |
| 625 | |
| 626 | } |
| 627 | {//Make sure that e1 < e2, makes removing easier |
| 628 | int maxE = Math.max(e1, e2); |
| 629 | e1 = Math.min(e1, e2); |
| 630 | e2 = maxE; |
| 631 | } |
| 632 | |
| 633 | if(toSplit.isLeaf()) |
| 634 | { |
| 635 | List<V> group1 = new ArrayList<V>(m+1); |
| 636 | List<V> group2 = new ArrayList<V>(m+1); |
| 637 | |
| 638 | List<V> toAsign = toSplit.points;//toSplit.points will get overwritten |
| 639 | |
| 640 | group2.add(toAsign.remove(e2)); |
| 641 | group1.add(toAsign.remove(e1)); |
| 642 | |
| 643 | Rectangle rec2 = new Rectangle(group2.get(0)); |
| 644 | Rectangle rec1 = new Rectangle(group1.get(0)); |
| 645 | |
| 646 | while(!toAsign.isEmpty()) |
| 647 | { |