FastHVSegmentsWindowing

computational.geometry.hvsegmentswindowing
Class FastHVSegmentsWindowing

java.lang.Object
  computational.geometry.hvsegmentswindowing.HVSegmentsWindowing
      computational.geometry.hvsegmentswindowing.FastHVSegmentsWindowing

public class FastHVSegmentsWindowing
extends HVSegmentsWindowing
extends HVSegmentsWindowing

This file contains the implementation of a data structure that can be used to store a set of horizotal and vertical segments in the plane. The segments may intersect and may share one or both endpoints. The data structure is built with the aid of the layered tree data structure and the segment interval tree data structure in O(n * log(n)) time (preprocessing) and takes up O( n * log(n)) space. Here n is the number of segments to store. Once the structure is built it cannot be modified (by inserting or deleting segments). The only operation that is allowed on the data structure is a query. The query is defined by an axis parallel rectangle and is carried out by returning all the segments in the data structure that intersect the query rectangle. This query can be carried out in O(log(n)^2 + k) time where k is the number of segments satisfying the query. Multiple (successive) queries can be performed on the data structure.

Constructor Summary
`FastHVSegmentsWindowing()`

Method Summary
`void`	`addSegment(Segment s)` Adds a segment to the data structure
`void`	`checkPreconditions()`
`void`	`clear()` Resets the data structure
`java.util.List`	`getSegments()` Method to return the segments currently in the data structure
`java.util.List`	`query(Rectangle r)` Performs a query on the data structure implemented by this class.
`void`	`setSegments(java.util.List segmentL)` Sets the segments in the data structure
`void`	`update()`

Methods inherited from class computational.geometry.hvsegmentswindowing.HVSegmentsWindowing
`isUpdated, setUpdated`

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

Constructor Detail