Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection.linkedlist
Class LineSweep

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

public class LineSweep
extends IntersectionDetection

Implementation using linkedList for lineState to show performance degradation as the size of the state increases.

Used as a benchmark, of sorts, to show how the wrong choice of data structure can damage the overall effectiveness of an algorithm.

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()
          Construct a sweep object.
 
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()
Construct a sweep object.

Method Detail

initialize

public void initialize()
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.