org.apache.lucene.geo

Class EdgeTree

java.lang.Object

org.apache.lucene.geo.EdgeTree

Direct Known Subclasses:

Polygon2D

public abstract class EdgeTree
extends Object

2D line/polygon geometry implementation represented as a balanced interval tree of edges.

Construction takes O(n log n) time for sorting and tree construction. relate() are O(n), but for most practical lines and polygons are much faster than brute force.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Field Summary

Fields

Modifier and Type	Field and Description
protected EdgeTree	left
double	maxLat maximum latitude of this geometry's bounding box area
double	maxLon maximum longitude of this geometry's bounding box area
protected double	maxX maximum longitude of this component or any of its children
protected double	maxY maximum latitude of this component or any of its children
double	minLat minimum latitude of this geometry's bounding box area
double	minLon minimum longitude of this geometry's bounding box area
protected EdgeTree	right
protected boolean	splitX which dimension was this node split on
protected org.apache.lucene.geo.EdgeTree.Edge	tree root node of edge tree

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	EdgeTree(double minLat, double maxLat, double minLon, double maxLon, double[] lats, double[] lons)

Method Summary

Modifier and Type	Method and Description
protected abstract PointValues.Relation	componentRelate(double minLat, double maxLat, double minLon, double maxLon) Returns relation to the provided rectangle for this component
protected abstract PointValues.Relation	componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) Returns relation to the provided triangle for this component
protected static EdgeTree	createTree(EdgeTree[] components, int low, int high, boolean splitX) Creates tree from sorted components (with range low and high inclusive)
protected PointValues.Relation	internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon) Returns relation to the provided rectangle for this component
protected static boolean	pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy) Compute whether the given x, y point is in a triangle; uses the winding order method
PointValues.Relation	relate(double minLat, double maxLat, double minLon, double maxLon) Returns relation to the provided rectangle
PointValues.Relation	relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) Returns relation to the provided triangle

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

minLat

public final double minLat

minimum latitude of this geometry's bounding box area

maxLat

public final double maxLat

maximum latitude of this geometry's bounding box area

minLon

public final double minLon

minimum longitude of this geometry's bounding box area

maxLon

public final double maxLon

maximum longitude of this geometry's bounding box area

maxY

protected double maxY

maximum latitude of this component or any of its children

maxX

protected double maxX

maximum longitude of this component or any of its children

splitX

protected boolean splitX

which dimension was this node split on

left

protected EdgeTree left

right

protected EdgeTree right

tree

protected final org.apache.lucene.geo.EdgeTree.Edge tree

root node of edge tree

Constructor Detail

EdgeTree

protected EdgeTree(double minLat,
                   double maxLat,
                   double minLon,
                   double maxLon,
                   double[] lats,
                   double[] lons)

Method Detail

relateTriangle

public PointValues.Relation relateTriangle(double ax,
                                           double ay,
                                           double bx,
                                           double by,
                                           double cx,
                                           double cy)

Returns relation to the provided triangle

relate

public PointValues.Relation relate(double minLat,
                                   double maxLat,
                                   double minLon,
                                   double maxLon)

Returns relation to the provided rectangle

componentRelate

protected abstract PointValues.Relation componentRelate(double minLat,
                                                        double maxLat,
                                                        double minLon,
                                                        double maxLon)

Returns relation to the provided rectangle for this component

componentRelateTriangle

protected abstract PointValues.Relation componentRelateTriangle(double ax,
                                                                double ay,
                                                                double bx,
                                                                double by,
                                                                double cx,
                                                                double cy)

Returns relation to the provided triangle for this component

internalComponentRelate

protected PointValues.Relation internalComponentRelate(double minLat,
                                                       double maxLat,
                                                       double minLon,
                                                       double maxLon)

Returns relation to the provided rectangle for this component

createTree

protected static EdgeTree createTree(EdgeTree[] components,
                                     int low,
                                     int high,
                                     boolean splitX)

Creates tree from sorted components (with range low and high inclusive)

pointInTriangle

protected static boolean pointInTriangle(double x,
                                         double y,
                                         double ax,
                                         double ay,
                                         double bx,
                                         double by,
                                         double cx,
                                         double cy)

Compute whether the given x, y point is in a triangle; uses the winding order method