computational.geometry.pointlocation
Class Kirkpatrick

java.lang.Object
  extended by computational.geometry.pointlocation.PointLocation
      extended by computational.geometry.pointlocation.Kirkpatrick

public class Kirkpatrick
extends PointLocation

Class implements Kirkpatrick's method for solving point location in planar triangulation with n points. Kirkpatrick's method has O(n log n) for preprocessing and O(log n) query cost.

Field Summary
 
Fields inherited from class computational.geometry.pointlocation.PointLocation
history, points
 
Constructor Summary
Kirkpatrick()
          Default constructor
Kirkpatrick(java.util.Collection ps)
          Constructor with collection of points
Kirkpatrick(java.util.Collection ps, LogManager history)
          Constructor with collection of points and history
 
Method Summary
 void checkPreconditions()
          Method used to verify if preconditions are satisfied
 java.util.List getPoints()
          Returns list of points of triangulation.
 java.util.Collection getSegments()
          Returns collection of segments that compose the triangulation.
 Triangle getTriangle(Point point)
          Method executes query - localizes triangle that contains point.
 void update()
          Method executed every time when is needed to update the structure used in Kirkpatrick's method.
 
Methods inherited from class computational.geometry.pointlocation.PointLocation
addPoint, clear, deletePoint, draw, draw, getLogManager, getPolygon, isUpdated, movePoint, setLogManager, setPoints, setUpdated
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Kirkpatrick

public Kirkpatrick()
Default constructor

Kirkpatrick

public Kirkpatrick(java.util.Collection ps)
Constructor with collection of points

Parameters:
ps - collection of input points

Kirkpatrick

public Kirkpatrick(java.util.Collection ps,
                   LogManager history)
Constructor with collection of points and history

Parameters:
ps - collection of input points
history - log used for tracking changes
Method Detail

checkPreconditions

public void checkPreconditions()
                        throws PreconditionViolatedException
Method used to verify if preconditions are satisfied

Specified by:
checkPreconditions in class PointLocation
Throws:
PreconditionViolatedException - this exception is thrown if some points is outside limiting box

getPoints

public java.util.List getPoints()
Returns list of points of triangulation. It DOESN'T return border points.

Overrides:
getPoints in class PointLocation
Returns:
list of points in triangulation

getSegments

public java.util.Collection getSegments()
Returns collection of segments that compose the triangulation. It DOESN'T return segment connecting border points.

Specified by:
getSegments in class PointLocation
Returns:
collection of segments in triangulation

getTriangle

public Triangle getTriangle(Point point)
Method executes query - localizes triangle that contains point.

Specified by:
getTriangle in class PointLocation
Parameters:
point - point for which query is executed

update

public void update()
Method executed every time when is needed to update the structure used in Kirkpatrick's method. It does preprocessing by creating rooted tree of triangles used later in queries to localize triangle.

Specified by:
update in class PointLocation