Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class LineState

java.lang.Object
  extended by algs.model.problems.segmentIntersection.LineState

public class LineState
extends java.lang.Object

Manages the state of segments in a balanced binary tree whose leaf nodes are used to store segments while the interior nodes are used to guide searches and insertions to the appropriate leaf nodes.

Defines a comparator seg_order which compares line segments that are known to have x-values on the sweepPt y-value horizontal line.

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

Field Summary
 java.util.Comparator<ILineSegment> seg_order
          The key point about this comparator is that it is only called when both line segments intersect the horizontal line defined by the y-value of the sweep pt.
 
Constructor Summary
LineState()
           
 
Method Summary
 void deleteRange(AugmentedNode<ILineSegment> left, AugmentedNode<ILineSegment> right)
          Delete everything from the successor of left until the successor of left is right.
 void determineIntersecting(EventPoint p, AugmentedNode<ILineSegment> left, AugmentedNode<ILineSegment> right)
          Only intersections are allowed with neighboring segments in the line state.
 IPoint getSweepPoint()
          Retrieve sweep point.
 void insertSegments(List<ILineSegment> list)
          Insert the segments into the line state.
 AugmentedNode<ILineSegment> leftNeighbor(EventPoint ep)
          Find node within the state that is the closest neighbor (on the left) to the given event point.
 AugmentedNode<ILineSegment> pred(AugmentedNode<ILineSegment> n)
          Return predececessor leaf in the tree.
 AugmentedNode<ILineSegment> rightNeighbor(EventPoint ep)
          Find segment within the state that is the closest neighbor (on the right) to the given event point.
 AugmentedNode<ILineSegment> root()
          Helper debugging method to return root of the state.
 void setSweepPoint(IPoint pt)
          Set where the sweep line is to appear.
 AugmentedNode<ILineSegment> successor(AugmentedNode<ILineSegment> n)
          Return successor leaf in the tree.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

seg_order

public java.util.Comparator<ILineSegment> seg_order
The key point about this comparator is that it is only called when both line segments intersect the horizontal line defined by the y-value of the sweep pt. If the above is not true, then the two line segments are actually incomparable.

One last point. This method is only invoked from within the insert method where o1 already has been placed in the tree. Thus we know that o2 contains the sweep point. Perhaps this optimization is unnecessary...

Once this point is clear, then it is simple how to order the segments.

Constructor Detail

LineState

public LineState()
Method Detail

root

public AugmentedNode<ILineSegment> root()
Helper debugging method to return root of the state.


determineIntersecting

public void determineIntersecting(EventPoint p,
                                  AugmentedNode<ILineSegment> left,
                                  AugmentedNode<ILineSegment> right)
Only intersections are allowed with neighboring segments in the line state. Thus we check from the successor of left, right through (but not including) right.

These left and right are the first segments that match.

Parameters:
p -
left -
right -

setSweepPoint

public void setSweepPoint(IPoint pt)
Set where the sweep line is to appear.

Parameters:
pt - the sweep point to use

insertSegments

public void insertSegments(List<ILineSegment> list)
Insert the segments into the line state.

It is worth noting that each of these segments being inserted is guaranteed to be on the sweep point.

Parameters:
list - list of ILineSegments to insert.

leftNeighbor

public AugmentedNode<ILineSegment> leftNeighbor(EventPoint ep)
Find node within the state that is the closest neighbor (on the left) to the given event point. Make a line from the given point to the x-intersection on the sweep line.

If we find multiple with same point, we have to keep on going to the left. Specifically, if compare returns 0, we keep going to the left.

Parameters:
ep -

rightNeighbor

public AugmentedNode<ILineSegment> rightNeighbor(EventPoint ep)
Find segment within the state that is the closest neighbor (on the right) to the given event point.

If we find multiple with same point, we have to keep on going to the right. Specifically, if compare returns 0, we keep going to the right.

Parameters:
ep -

successor

public AugmentedNode<ILineSegment> successor(AugmentedNode<ILineSegment> n)
Return successor leaf in the tree.

We can be guaranteed to be called with a LEAF node, since interior nodes are only guiding the process.

Parameters:
n -
Returns:
leaf in the tree that is the next segment to the right (or null if no such node exists).

pred

public AugmentedNode<ILineSegment> pred(AugmentedNode<ILineSegment> n)
Return predececessor leaf in the tree.

We can be guaranteed to be called with a LEAF node, since interior nodes are only guiding the process.

Parameters:
n -
Returns:
leaf in the tree that is the next segment to the right (or null if no such node exists).

deleteRange

public void deleteRange(AugmentedNode<ILineSegment> left,
                        AugmentedNode<ILineSegment> right)
Delete everything from the successor of left until the successor of left is right.

All of these line segments potentially need to be reorganized once the sweep point advances.

Parameters:
left -
right -

getSweepPoint

public IPoint getSweepPoint()
Retrieve sweep point.


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.