computational.geometry.hvsegmentswindowing
Class SegIntervalTree

java.lang.Object
  computational.geometry.hvsegmentswindowing.SegIntervalTree

public class SegIntervalTree
extends java.lang.Object

This file contains the implementation of a data structure called segment interval tree. It is a modification of the interval tree data structure and is used to store objects (we will call them segments) having two values for their first key (a left value and a right value) and also having a second key value. The first and second keys are independent. The only restrictions are that the two keys must be totally ordered and that the left value for the first key must be less than or equal to the right value for the first key. This data structure can be used to represent horizontal segments in the plane where the first key values are the abscissas of the segment extremes and the second key is the common ordinate of the extremes. The two values pertaining the first key are used to build the tree structure as in an ordinary interval tree. The difference between an interval tree and this data structure lies in the contents of each node of the tree. Instead of having two lists the nodes of this data structure contain two layered range trees built on the first and second keys of the "left extremes" of the segments and on the "right extremes" of the segments that contain a given first key split value. The query on this data structure allows to request all the stored segments intersecting a given "vertical" segment. The query is specified by supplying a first key key1 and two values for the second key: key2L and key2R. The result of the query will be all the segments stored in the data structure containing at least one of the key values specified by the two dimensional range key1 * [key2L, key2R]. The construction of this data structure can be carried out in O(n * log(n)) time (preprocessing) using O(n * log(n)) space. The query can be carried out in O(log(n)^2 + k) time. Here n is the number of segments stored in the tree while k is the number of segments that satisfy the query. Once the structure is built it cannot be modified (new segments cannot be added nor existing segments can be removed) but it supports multiple (successive) queries. The data structure also support multiple segments having the same key values (extremes).

SegIntervalTree

public SegIntervalTree(java.lang.Object[] lKeys1,
                       java.lang.Object[] rKeys1,
                       java.lang.Object[] keys2,
                       java.lang.Object[] data,
                       java.util.Comparator key1Comp,
                       java.util.Comparator key2Comp)

Constructor. It builds the segment interval tree data structure on the objects given in array data. The corresponding left first keys and right first keys are given in arrays lKeys1 and rKeys1 while the second keys are given in array keys2. Comparators key1Comp and key2Comp are used to compare first keys and second keys respectively. The input arrays are assumed to be of the same size and non empty. Also for each input element the left first key is supposed to be less than or equal to its right first key.

query

public java.util.List query(java.lang.Object key1,
                            java.lang.Object key2L,
                            java.lang.Object key2R)

This method performs a query on the data structure implemented by this class. key1 is a first key value while key2L and key2R are values for the second key. An object stored in the data structure is returned if the "segment" defined by its first key values and its second key value intersects (i.e. has one point in common with) the "vertical segment" key1 * [key2L, key2R]. Key2L can be greater than key2R: in this case an empty list is returned since the query range is considered to be empty; otherwise all those elements satisfying the query are returned in a list.