|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.problems.segmentIntersection.IntersectionDetection
algs.model.problems.segmentIntersection.LineSweep
public class LineSweep
Contains LineSweep algorithm to detect all intersections among an array of line segments.
Note that the LineState uses an augmented binary tree in which the internal nodes store (min, max) values that reflect the leftmost segment in the left sub-tree and the rightmost segment in the right sub-tree. The keys of the nodes in the tree are the segments themselves.
As the algorithm progresses, there may be errors that occur because of problems inherent in the floating point calculations. At times, the aglorithm can actually detect when these occur. The algorithm simply outputs the error to stderr but does not fail or throw an exception. This is an agreeable compromise given the challenges in using floating point computations accurately.
The EventQueue is able to insert a new EventPoint in O (log n) as well as locate a previous EventPoint in the event queue with the same performance.
Field Summary |
---|
Fields inherited from class algs.model.problems.segmentIntersection.IntersectionDetection |
---|
report |
Constructor Summary | |
---|---|
LineSweep()
|
Method Summary | |
---|---|
void |
initialize()
Initialize algorithm. |
java.util.Hashtable<IPoint,ILineSegment[]> |
intersections(ILineSegment[] segs)
Compute the intersection of all segments when given an array of segments. |
Methods inherited from class algs.model.problems.segmentIntersection.IntersectionDetection |
---|
computeTime, intersections, intersections, output, record, record, sameWithinEpsilon, startTime, time |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public LineSweep()
Method Detail |
---|
public void initialize()
IntersectionDetection
initialize
in class IntersectionDetection
public java.util.Hashtable<IPoint,ILineSegment[]> intersections(ILineSegment[] segs)
Returns the report which is maintained by the superclass
intersections
in class IntersectionDetection
segs
- Line segments to be checked for intersections.
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |