computational.geometry.hvsegmentswindowing
Class FastHVSegmentsWindowing

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

public class FastHVSegmentsWindowing
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

FastHVSegmentsWindowing

public FastHVSegmentsWindowing()
Method Detail

addSegment

public void addSegment(Segment s)
                throws PreconditionViolatedException
Adds a segment to the data structure

Specified by:
addSegment in class HVSegmentsWindowing
Throws:
PreconditionViolatedException

checkPreconditions

public void checkPreconditions()
                        throws PreconditionViolatedException
Throws:
PreconditionViolatedException

clear

public void clear()
Resets the data structure

Specified by:
clear in class HVSegmentsWindowing

getSegments

public java.util.List getSegments()
Method to return the segments currently in the data structure

Specified by:
getSegments in class HVSegmentsWindowing

query

public java.util.List query(Rectangle r)
Performs a query on the data structure implemented by this class. All of the segments having at least one point in common with the query rectangle given by argument r are returned in a list. An empty list is returned if no segments intersect the query rectangle.

Specified by:
query in class HVSegmentsWindowing

setSegments

public void setSegments(java.util.List segmentL)
                 throws PreconditionViolatedException
Sets the segments in the data structure

Specified by:
setSegments in class HVSegmentsWindowing
Throws:
PreconditionViolatedException

update

public void update()
Specified by:
update in class HVSegmentsWindowing