HRPlusTreeUtils

java.lang.Object
- org.geogit.api.HRPlusTreeUtils

Direct Known Subclasses:

HRPlusTree, HRPlusTreePartition
```
public class HRPlusTreeUtils
extends java.lang.Object
```
Base class for HRPlus tree implementation of the spatial index. This class contains utility methods for manipulating HRPlus trees. Utilities are factored out because we distinguish between a plain HRPlus tree and an HRPlus tree partition. The latter is used to speed up insertions. For the original idea, see [1] http://www.cs.ust.hk/faculty/dimitris/PAPERS/ssdbm01.pdf and for details on insertion, see Section 4 of: [2] http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf

Constructor Summary

Constructors
Constructor and Description

HRPlusTreeUtils()

Constructors
Constructor and Description
`HRPlusTreeUtils()`

Method Summary

Methods
Modifier and Type	Method and Description
`protected static Envelope`	`boundingBoxOf(java.util.List<HRPlusNode> nodes)` Create an envelope covering all the points in @param nodes.
`protected static double`	`getOverlap(java.util.List<HRPlusNode> firstGroup, java.util.List<HRPlusNode> secondGroup)` Find the overlap between bounding boxes surrounding two groups of nodes.
`protected static double`	`getTotalAreaOfTwoRegions(java.util.List<HRPlusNode> firstGroup, java.util.List<HRPlusNode> secondGroup)` Get total area of the envelopes covering two groups of nodes.
`protected static double`	`marginOf(Envelope envelope)` margin = perimeter
`protected static java.util.List<HRPlusNode>`	`maxXSort(java.util.List<HRPlusNode> nodes)` Sort a list of nodes by their maximum x coordinate
`protected static java.util.List<HRPlusNode>`	`maxYSort(java.util.List<HRPlusNode> nodes)` Sort a list of nodes by their maximum y coordinate.
`protected static java.util.List<HRPlusNode>`	`minXSort(java.util.List<HRPlusNode> nodes)` Sort a list of nodes by their minimum x coordinate.
`protected static java.util.List<HRPlusNode>`	`minYSort(java.util.List<HRPlusNode> nodes)` Sort a list of nodes by their minimum y coordinate.
`protected static java.util.List<HRPlusNode>`	`partitionByMinOverlap(java.util.List<HRPlusNode> minSort, java.util.List<HRPlusNode> maxSort)` Take a list of nodes, sorted by position on a one-dimensional axis.
`protected static double`	`sumOfMargins(java.util.List<HRPlusNode> nodes)` Sum many perimeters.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - HRPlusTreeUtils
```
public HRPlusTreeUtils()
```
- Method Detail
  - boundingBoxOf
```
protected static Envelope boundingBoxOf(java.util.List<HRPlusNode> nodes)
```
    Create an envelope covering all the points in @param nodes. Used to create a container node for the HRPlus tree.
    
    Parameters:
    nodes -
    
    Returns:
  - getOverlap
```
protected static double getOverlap(java.util.List<HRPlusNode> firstGroup,
                java.util.List<HRPlusNode> secondGroup)
```
    Find the overlap between bounding boxes surrounding two groups of nodes.
    
    Parameters:
    firstGroup -
    secondGroup -
    
    Returns:
    the area of the enclosing bounding box
  - getTotalAreaOfTwoRegions
```
protected static double getTotalAreaOfTwoRegions(java.util.List<HRPlusNode> firstGroup,
                              java.util.List<HRPlusNode> secondGroup)
```
    Get total area of the envelopes covering two groups of nodes.
    
    Parameters:
    firstGroup -
    secondGroup -
    
    Returns:
    combined area of the two envelopes
  - marginOf
```
protected static double marginOf(Envelope envelope)
```
    margin = perimeter
    
    Parameters:
    envelope -
    
    Returns:
    the perimeter of the envelope
  - sumOfMargins
```
protected static double sumOfMargins(java.util.List<HRPlusNode> nodes)
```
    Sum many perimeters. I do not entirely understand the implementation. It's based off the algorithm presented in [2], and that paper suggests minimizing perimeters as a useful way to optimize an index.
    
    Parameters:
    nodes -
    
    Returns:
  - partitionByMinOverlap
```
protected static java.util.List<HRPlusNode> partitionByMinOverlap(java.util.List<HRPlusNode> minSort,
                                               java.util.List<HRPlusNode> maxSort)
```
    Take a list of nodes, sorted by position on a one-dimensional axis. Return a subset of these nodes. Specifically, the subset of nodes that is closest together based on the one-dimensional axis and the total perimeter and area of their enclosing envelope.
    
    Parameters:
    minSort - nodes sorted by minimum position along some axis
    maxSort - same nodes, sorted by maximum position along the same axis.
    
    Returns:
    sublist containing the nodes closest together
  - minXSort
```
protected static java.util.List<HRPlusNode> minXSort(java.util.List<HRPlusNode> nodes)
```
    Sort a list of nodes by their minimum x coordinate.
    
    Parameters:
    nodes -
    
    Returns:
  - minYSort
```
protected static java.util.List<HRPlusNode> minYSort(java.util.List<HRPlusNode> nodes)
```
    Sort a list of nodes by their minimum y coordinate.
    
    Parameters:
    nodes -
    
    Returns:
  - maxXSort
```
protected static java.util.List<HRPlusNode> maxXSort(java.util.List<HRPlusNode> nodes)
```
    Sort a list of nodes by their maximum x coordinate
    
    Parameters:
    nodes -
    
    Returns:
  - maxYSort
```
protected static java.util.List<HRPlusNode> maxYSort(java.util.List<HRPlusNode> nodes)
```
    Sort a list of nodes by their maximum y coordinate.
    
    Parameters:
    nodes -
    
    Returns:

Class HRPlusTreeUtils

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

HRPlusTreeUtils

Method Detail

boundingBoxOf

getOverlap

getTotalAreaOfTwoRegions

marginOf

sumOfMargins

partitionByMinOverlap

minXSort

minYSort

maxXSort

maxYSort