Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class EventPoint

java.lang.Object
  extended by algs.model.problems.segmentIntersection.EventPoint
All Implemented Interfaces:
java.util.Comparator<EventPoint>

public class EventPoint
extends java.lang.Object
implements java.util.Comparator<EventPoint>

The EventPoint is the basic element of the EventQueue.

Each EventPoint is fully ordered according to the Horizontal Sweep Line. Specifically, e1 < e2 if and only if (a) e1.y > e2.y or (b) e1.y == e2.y and e1.x < e2.x

Note that even points store information about the line segments being processed, including: (a) upper segments that begin at the given event point; (b) lower segments that end at the given event point; and (c) segments that intersect at the event point.

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

Field Summary
static java.util.Comparator<EventPoint> eventPointSorter
          Globally useful sorter, sorts points based on a horizontal sweep line moving vertically down the Cartesian plane.
 IPoint point
          The point.
static java.util.Comparator<IPoint> pointSorter
          Globally useful sorter, sorts points based on a horizontal sweep line moving vertically down the Cartesian plane.
 
Constructor Summary
EventPoint(IPoint p)
          Constructor for the Event Point when not an upper (start) endpoint.
 
Method Summary
 void addIntersectingLineSegment(ILineSegment ints)
          Add this line segment as an intersecting one.
 void addLowerLineSegment(ILineSegment lower)
          Add this line segment but only if its Lower (i.e., End) is reflective of this eventPoint.
 void addUpperLineSegment(ILineSegment upper)
          Add this line segment but only if its Upper (i.e., Start) is reflective of this eventPoint.
 void addUpperLineSegments(List<ILineSegment> list)
          Batch process a set of upper insertions here.
 int compare(EventPoint o1, EventPoint o2)
          Comparison assumes a horizontal sweep line starting from the top and sweeping down the plane.
 boolean equals(java.lang.Object o)
          Need equals method if this class is ever to be used within the collection classes.
 List<ILineSegment> intersectingSegments()
          Return the set of Line segments that intersect this eventPoint.
 List<ILineSegment> lowerEndpointSegments()
          Return the set of Line segments whose lower (i.e., End) endpoint is this EventPoint.
 java.lang.String toString()
          Useful representation.
 List<ILineSegment> upperEndpointSegments()
          Return the set of Line segments whose upper (i.e., Start) endpoint is this EventPoint.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

point

public final IPoint point
The point.


pointSorter

public static java.util.Comparator<IPoint> pointSorter
Globally useful sorter, sorts points based on a horizontal sweep line moving vertically down the Cartesian plane.


eventPointSorter

public static java.util.Comparator<EventPoint> eventPointSorter
Globally useful sorter, sorts points based on a horizontal sweep line moving vertically down the Cartesian plane.

Constructor Detail

EventPoint

public EventPoint(IPoint p)
Constructor for the Event Point when not an upper (start) endpoint.

Parameters:
p - point of interest
Method Detail

compare

public int compare(EventPoint o1,
                   EventPoint o2)
Comparison assumes a horizontal sweep line starting from the top and sweeping down the plane.

Specified by:
compare in interface java.util.Comparator<EventPoint>
Parameters:
o1 - point 1 under comparison
o2 - point 2 under comparison

addUpperLineSegment

public void addUpperLineSegment(ILineSegment upper)
Add this line segment but only if its Upper (i.e., Start) is reflective of this eventPoint.

Parameters:
upper -

addLowerLineSegment

public void addLowerLineSegment(ILineSegment lower)
Add this line segment but only if its Lower (i.e., End) is reflective of this eventPoint.

Parameters:
lower -

addIntersectingLineSegment

public void addIntersectingLineSegment(ILineSegment ints)
Add this line segment as an intersecting one.

Parameters:
ints -

upperEndpointSegments

public List<ILineSegment> upperEndpointSegments()
Return the set of Line segments whose upper (i.e., Start) endpoint is this EventPoint. In the algorithm, this return value is denoted U(p)


lowerEndpointSegments

public List<ILineSegment> lowerEndpointSegments()
Return the set of Line segments whose lower (i.e., End) endpoint is this EventPoint. In the algorithm, this return value is denoted L(p)


intersectingSegments

public List<ILineSegment> intersectingSegments()
Return the set of Line segments that intersect this eventPoint. In the algorithm, this return value is denoted C(p)


addUpperLineSegments

public void addUpperLineSegments(List<ILineSegment> list)
Batch process a set of upper insertions here.

Parameters:
list - list of line segments

equals

public boolean equals(java.lang.Object o)
Need equals method if this class is ever to be used within the collection classes.

Specified by:
equals in interface java.util.Comparator<EventPoint>
Overrides:
equals in class java.lang.Object

toString

public java.lang.String toString()
Useful representation.

Overrides:
toString in class java.lang.Object

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.