java.lang.Object computational.geometry.hvsegmentswindowing.HVSegmentsWindowing computational.geometry.hvsegmentswindowing.FastHVSegmentsWindowing
public class FastHVSegmentsWindowing
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 |
---|
public FastHVSegmentsWindowing()
Method Detail |
---|
public void addSegment(Segment s) throws PreconditionViolatedException
addSegment
in class HVSegmentsWindowing
PreconditionViolatedException
public void checkPreconditions() throws PreconditionViolatedException
PreconditionViolatedException
public void clear()
clear
in class HVSegmentsWindowing
public java.util.List getSegments()
getSegments
in class HVSegmentsWindowing
public java.util.List query(Rectangle r)
query
in class HVSegmentsWindowing
public void setSegments(java.util.List segmentL) throws PreconditionViolatedException
setSegments
in class HVSegmentsWindowing
PreconditionViolatedException
public void update()
update
in class HVSegmentsWindowing