presto-geospatial-toolkit/src/main/java/io/prestosql/geospatial/KdbTree.java/KdbTree/trySplit
class KdbTree:    private static Optional<SplitResult<Node>> trySplit(SplitDimension splitDimension, int maxItemsPerNode, int level, Rectangle extent, List<Rectangle> items, LeafIdAllocator leafIdAllocator)
    {
        checkArgument(items.size() > 1, "Number of items to split must be > 1");

        // Sort envelopes by xMin or yMin
        List<Rectangle> sortedItems = ImmutableList.sortedCopyOf(splitDimension.getComparator(), items);

        // Find a mid-point
        int middleIndex = (sortedItems.size() - 1) / 2;
        Rectangle middleEnvelope = sortedItems.get(middleIndex);
        double splitValue = splitDimension.getValue(middleEnvelope);
        int splitIndex = middleIndex;

        // skip over duplicate values
        while (splitIndex < sortedItems.size() && splitDimension.getValue(sortedItems.get(splitIndex)) == splitValue) {
            splitIndex++;
        }

        // all values between left-of-middle and the end are the same, so can't split
        if (splitIndex == sortedItems.size()) {
            return Optional.empty();
        }

        // about half of the objects are <= splitValue, the rest are >= next value
        // assuming the input set of objects is a sample from a much larger set,
        // let's split in the middle; this way objects from the larger set with values
        // between splitValue and next value will get split somewhat evenly into left
        // and right partitions
        splitValue = (splitValue + splitDimension.getValue(sortedItems.get(splitIndex))) / 2;

        SplitResult<Rectangle> childExtents = splitDimension.split(extent, splitValue);

        return Optional.of(new SplitResult<>(
                buildKdbTreeNode(maxItemsPerNode, level + 1, childExtents.getLeft(), sortedItems.subList(0, splitIndex), leafIdAllocator),
                buildKdbTreeNode(maxItemsPerNode, level + 1, childExtents.getRight(), sortedItems.subList(splitIndex, sortedItems.size()), leafIdAllocator)));
    }