createParentBoundables method

List createParentBoundables(
  1. List childBoundables,
  2. int newLevel
)
override

Creates the parent level for the given child level. First, orders the items by the x-values of the midpoints, and groups them into vertical slices. For each slice, orders the items by the y-values of the midpoints, and group them into runs of size M (the node capacity). For each run, creates a new (parent) node.

Implementation

List createParentBoundables(List childBoundables, int newLevel) {
  Assert.isTrue(!childBoundables.isEmpty);
  int minLeafCount =
      ((childBoundables.length / getNodeCapacity().toDouble())).ceil();
  List sortedChildBoundables = List.from(childBoundables);
  sortedChildBoundables.sort(xComparator);
  List<List> verticalSlicesList =
      verticalSlices(sortedChildBoundables, (math.sqrt(minLeafCount)).ceil());
  return createParentBoundablesFromVerticalSlices(
      verticalSlicesList, newLevel);
}