/**
 * Copyright 2017-present Palantir Technologies
 * @license MIT
 */
import { Bounds, IEntityBounds, Point } from "../core/interfaces";
import { IRTreeSplitStrategy } from "./rTreeSplitStrategies";
/**
 * The return result of predicates used with `RTree.queryNodes`.
 *
 * The `PASS_AND_OVERWRITE` value will overwrite previous results
 * when the predicate finds a more optimal result.
 */
export declare enum QueryPredicateResult {
    PASS = 0,
    FAIL = 1,
    PASS_AND_OVERWRITE = 2,
}
/**
 * Returns the absolute distance to the nearest point on the edge of bounds or 0
 * if the point is in bounds.
 */
export declare type IDistanceFunction = (bounds: RTreeBounds, p: Point) => number;
/**
 * Creates a node predicate for use with `RTree.queryNodes`
 *
 * @param point - the query point
 * @param nearFn - an `IDistanceFunction` from the query point to the nearest
 * point on the node bounds
 * @param farFn - an `IDistanceFunction` from the query point to the farthest
 * point on the node bounds
 */
export declare function createMinimizingNodePredicate<T>(point: Point, nearFn: IDistanceFunction, farFn: IDistanceFunction): (node: RTreeNode<T>) => QueryPredicateResult;
/**
 * Create a `Array.sort` function from a query point and a distance function.
 */
export declare function createNodeSort<T>(point: Point, distanceFn: IDistanceFunction): (a: RTreeNode<T>, b: RTreeNode<T>) => number;
/**
 * R-Tree is a multidimensional spatial region tree. It stores entries that have
 * arbitrarily overlapping bounding boxes and supports efficient point and
 * bounding box overlap queries.
 *
 * Average search time complexity is O(log_M(N)) where M = max children per node
 * and N is number of values stored in tree.
 *
 * It is similar in purpose to a quadtree except quadtrees can only store a
 * single point per entry. Also, the space-partitioning structure of quadtrees
 * provides guarantees that any given value has no neighbors closer than its
 * node's bounds, whereas r-trees provide no such guarantees.
 */
export declare class RTree<T> {
    private maxNodeChildren;
    private splitStrategy;
    private root;
    private size;
    constructor(maxNodeChildren?: number, splitStrategy?: IRTreeSplitStrategy);
    getRoot(): RTreeNode<T>;
    clear(): void;
    insert(bounds: RTreeBounds, value: T): RTreeNode<T>;
    locate(xy: Point): T[];
    /**
     * Returns an array of `T` values that are the "nearest" to the query point.
     *
     * Nearness is measured as the absolute distance from the query point to the
     * nearest edge of the node bounds. If the node bounds contains the query
     * point, the distance is 0.
     */
    locateNearest(xy: Point): T[];
    /**
     * Returns an array of `T` values that are the "nearest" to the query point.
     *
     * Nearness is measured as the 1-dimensional absolute distance from the
     * query's x point to the nearest edge of the node bounds. If the node
     * bounds contains the query point, the distance is 0.
     *
     * The results are sorted by y-coordinate nearness.
     */
    locateNearestX(xy: Point): T[];
    /**
     * Returns an array of `T` values that are the "nearest" to the query point.
     *
     * Nearness is measured as the 1-dimensional absolute distance from the
     * query's y point to the nearest edge of the node bounds. If the node
     * bounds contains the query point, the distance is 0.
     *
     * The results are sorted by x-coordinate nearness.
     */
    locateNearestY(xy: Point): T[];
    intersect(bounds: RTreeBounds): T[];
    intersectX(bounds: RTreeBounds): T[];
    intersectY(bounds: RTreeBounds): T[];
    query(predicate: (b: RTreeBounds) => boolean): T[];
    queryNodes(predicate: (b: RTreeNode<T>) => QueryPredicateResult): RTreeNode<T>[];
}
export declare class RTreeNode<T> {
    leaf: boolean;
    static valueNode<T>(bounds: RTreeBounds, value: T): RTreeNode<T>;
    bounds: RTreeBounds;
    entries: RTreeNode<T>[];
    parent: RTreeNode<T>;
    value: T;
    constructor(leaf: boolean);
    /**
     * Returns `true` iff this node has more children than the `maxNodeChildren`
     * parameter.
     */
    overflow(maxNodeChildren: number): boolean;
    /**
     * Inserts a child node and updates the ancestry bounds.
     */
    insert(node: RTreeNode<T>): this;
    /**
     * Removes a child node and updates the ancestry bounds.
     *
     * If the node argument is not a child, do nothing.
     */
    remove(node: RTreeNode<T>): this;
    /**
     * Chooses an node from then entries that minimizes the area difference that
     * adding the bounds the each entry would cause.
     */
    subtree(bounds: RTreeBounds): RTreeNode<T>;
    /**
     * Splits this node by creating two new nodes and dividing the this node's
     * children between them. This node is removed from its parent and the two
     * new nodes are added.
     *
     * If this node is the root, a new parent node is created.
     *
     * Returns the parent node.
     */
    split(strategy: IRTreeSplitStrategy): RTreeNode<T>;
    /**
     * Returns the difference in area that adding an entry `bounds` to the node
     * would cause.
     */
    unionAreaDifference(bounds: RTreeBounds): number;
    /**
     * Returns the depth from this node to the deepest leaf descendant.
     */
    maxDepth(): number;
}
export declare class RTreeBounds {
    xl: number;
    yl: number;
    xh: number;
    yh: number;
    static xywh(x: number, y: number, w: number, h: number): RTreeBounds;
    static entityBounds(bounds: IEntityBounds): RTreeBounds;
    static bounds(bounds: Bounds): RTreeBounds;
    static pointPair(p0: Point, p1: Point): RTreeBounds;
    static points(points: Point[]): RTreeBounds;
    static union(b0: RTreeBounds, b1: RTreeBounds): RTreeBounds;
    static unionAll(bounds: RTreeBounds[]): RTreeBounds;
    /**
     * Returns true if `a` overlaps `b` in the x and y axes.
     *
     * Touching counts as overlap.
     */
    static isBoundsOverlapBounds(a: RTreeBounds, b: RTreeBounds): boolean;
    /**
     * Returns true if `a` overlaps `b` in the x axis only.
     *
     * Touching counts as overlap.
     */
    static isBoundsOverlapX(a: RTreeBounds, b: RTreeBounds): boolean;
    /**
     * Returns true if `a` overlaps `b` in the y axis only.
     *
     * Touching counts as overlap.
     */
    static isBoundsOverlapY(a: RTreeBounds, b: RTreeBounds): boolean;
    /**
     * Returns the orthogonal absolute distance in the x-dimension from point
     * `p` to the nearest edge of `bounds`.
     *
     * If `p.x` is inside the bounds returns `0`.
     */
    static absoluteDistanceToNearEdgeX(bounds: RTreeBounds, p: Point): number;
    /**
     * Returns the orthogonal absolute distance in the y-dimension from point
     * `p` to the nearest edge of `bounds`.
     *
     * If `p.y` is inside the bounds returns `0`.
     */
    static absoluteDistanceToNearEdgeY(bounds: RTreeBounds, p: Point): number;
    /**
     * Returns the orthogonal absolute distance in the x-dimension from point
     * `p` to the farthest edge of `bounds`.
     *
     * If `p.x` is inside the bounds returns `0`.
     */
    static absoluteDistanceToFarEdgeX(bounds: RTreeBounds, p: Point): number;
    /**
     * Returns the orthogonal absolute distance in the y-dimension from point
     * `p` to the farthest edge of `bounds`.
     *
     * If `p.y` is inside the bounds returns `0`.
     */
    static absoluteDistanceToFarEdgeY(bounds: RTreeBounds, p: Point): number;
    /**
     * Returns the distance squared from `p` to the nearest edge of `bounds`. If
     * the point touches or is inside the bounds, returns `0`;
     *
     * https://gamedev.stackexchange.com/questions/44483/how-do-i-calculate-distance-between-a-point-and-an-axis-aligned-rectangle
     */
    static distanceSquaredToNearEdge(bounds: RTreeBounds, p: Point): number;
    static distanceSquaredToFarEdge(bounds: RTreeBounds, p: Point): number;
    width: number;
    height: number;
    private areaCached;
    constructor(xl: number, yl: number, xh: number, yh: number);
    area(): number;
    contains(xy: Point): boolean;
}