Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class LineSweep

java.lang.Object
  extended by algs.model.problems.segmentIntersection.IntersectionDetection
      extended by algs.model.problems.segmentIntersection.LineSweep

public class LineSweep
extends IntersectionDetection

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.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

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

LineSweep

public LineSweep()
Method Detail

initialize

public void initialize()
Description copied from class: IntersectionDetection
Initialize algorithm.

Overrides:
initialize in class IntersectionDetection

intersections

public java.util.Hashtable<IPoint,ILineSegment[]> intersections(ILineSegment[] segs)
Compute the intersection of all segments when given an array of segments.

Returns the report which is maintained by the superclass

Specified by:
intersections in class IntersectionDetection
Parameters:
segs - Line segments to be checked for intersections.

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.