Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class IntersectionDetection

java.lang.Object
  extended by algs.model.problems.segmentIntersection.IntersectionDetection
Direct Known Subclasses:
BruteForceAlgorithm, LineSweep, LineSweep, SlowLineSweep

public abstract class IntersectionDetection
extends java.lang.Object

This superclass has been designed to enable the side-by-side comparison of a number of line segment variations, where different data structures are used to support the core algorithm.

Note that one implication of using this structure is that the line state may not be emptied in between executions.

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

Field Summary
protected  java.util.Hashtable<IPoint,ILineSegment[]> report
          Reported intersections.
 
Constructor Summary
IntersectionDetection()
           
 
Method Summary
protected  void computeTime()
           
protected  void initialize()
          Initialize algorithm.
 java.util.Hashtable<IPoint,ILineSegment[]> intersections(java.util.Collection<ILineSegment> segments)
          Compute the intersection of all segments when given a Collection of segments.
abstract  java.util.Hashtable<IPoint,ILineSegment[]> intersections(ILineSegment[] segments)
          The subclass determines all intersections.
 java.util.Hashtable<IPoint,ILineSegment[]> intersections(java.util.Iterator<ILineSegment> it)
          Compute the intersection of all segments when given an Iterator of segments.
 void output(java.util.Hashtable<IPoint,ILineSegment[]> result)
          Convenient helper class to format the output from intersection algorithms.
protected  void record(IPoint p, ILineSegment il1, ILineSegment il2)
          Add the intersection to our report of these two segments.
protected  void record(IPoint p, List<ILineSegment>[] lists)
          Add the intersection to our report.
static boolean sameWithinEpsilon(java.util.Hashtable<IPoint,ILineSegment[]> result1, java.util.Hashtable<IPoint,ILineSegment[]> result2)
          Helper function (for debugging) to ensure that the two resulting computations are the same within an epsilon (for the intersection points).
protected  void startTime()
           
 long time()
          Return last time to complete algorithm (in Milliseconds).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

report

protected java.util.Hashtable<IPoint,ILineSegment[]> report
Reported intersections. key: IPoint with the intersection value: Array of the segments that intersect at that location.

Constructor Detail

IntersectionDetection

public IntersectionDetection()
Method Detail

intersections

public abstract java.util.Hashtable<IPoint,ILineSegment[]> intersections(ILineSegment[] segments)
The subclass determines all intersections.

Parameters:
segments - Segments that form the input set S.

intersections

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

Parameters:
segments -

initialize

protected void initialize()
Initialize algorithm.


record

protected void record(IPoint p,
                      ILineSegment il1,
                      ILineSegment il2)
Add the intersection to our report of these two segments. Take care that the same line segment is not added twice.

It is clear that the performance of this method can be improved upon. Note how it uses the inefficient pattern to only increase the size of the array by two with each discovered point. However, since this implementation affects equally the brute force implementation as well as the LineSweep implementation, it was left as is.

TODO: A proper rewrite would be to use an improved data structure for storing the intersection pairs to avoid duplicates.

Parameters:
p - an intersection point
il1 - a member of a line pair that intersects at that intersection point
il2 - the other member of a line pair that also intersects at that intersection point

record

protected void record(IPoint p,
                      List<ILineSegment>[] lists)
Add the intersection to our report.

Make sure that all reported intersections are merged with existing ones in the report, if this method is invoked multiple times with the same intersection point p.

Parameters:
p -
lists -

intersections

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

Parameters:
it - Iterator of line segments from which intersections are to be computed.

time

public long time()
Return last time to complete algorithm (in Milliseconds).


computeTime

protected void computeTime()

startTime

protected void startTime()

sameWithinEpsilon

public static boolean sameWithinEpsilon(java.util.Hashtable<IPoint,ILineSegment[]> result1,
                                        java.util.Hashtable<IPoint,ILineSegment[]> result2)
Helper function (for debugging) to ensure that the two resulting computations are the same within an epsilon (for the intersection points). Generates a meaningful report if all found intersections are close enough.


output

public void output(java.util.Hashtable<IPoint,ILineSegment[]> result)
Convenient helper class to format the output from intersection algorithms.


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.