|
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
public abstract class IntersectionDetection
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.
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 |
---|
protected java.util.Hashtable<IPoint,ILineSegment[]> report
Constructor Detail |
---|
public IntersectionDetection()
Method Detail |
---|
public abstract java.util.Hashtable<IPoint,ILineSegment[]> intersections(ILineSegment[] segments)
segments
- Segments that form the input set S.public java.util.Hashtable<IPoint,ILineSegment[]> intersections(java.util.Collection<ILineSegment> segments)
segments
- protected void initialize()
protected void record(IPoint p, ILineSegment il1, ILineSegment il2)
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.
p
- an intersection pointil1
- a member of a line pair that intersects at that intersection pointil2
- the other member of a line pair that also intersects at that intersection pointprotected void record(IPoint p, List<ILineSegment>[] lists)
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.
p
- lists
- public java.util.Hashtable<IPoint,ILineSegment[]> intersections(java.util.Iterator<ILineSegment> it)
it
- Iterator of line segments from which intersections are to be computed.public long time()
protected void computeTime()
protected void startTime()
public static boolean sameWithinEpsilon(java.util.Hashtable<IPoint,ILineSegment[]> result1, java.util.Hashtable<IPoint,ILineSegment[]> result2)
public void output(java.util.Hashtable<IPoint,ILineSegment[]> result)
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |