|
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.LineState
public class LineState
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.
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 |
---|
public java.util.Comparator<ILineSegment> seg_order
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 |
---|
public LineState()
Method Detail |
---|
public AugmentedNode<ILineSegment> root()
public void determineIntersecting(EventPoint p, AugmentedNode<ILineSegment> left, AugmentedNode<ILineSegment> right)
These left and right are the first segments that match.
p
- left
- right
- public void setSweepPoint(IPoint pt)
pt
- the sweep point to usepublic void insertSegments(List<ILineSegment> list)
It is worth noting that each of these segments being inserted is guaranteed to be on the sweep point.
list
- list of ILineSegments to insert.public AugmentedNode<ILineSegment> leftNeighbor(EventPoint ep)
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.
ep
- public AugmentedNode<ILineSegment> rightNeighbor(EventPoint ep)
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.
ep
- public AugmentedNode<ILineSegment> successor(AugmentedNode<ILineSegment> n)
We can be guaranteed to be called with a LEAF node, since interior nodes are only guiding the process.
n
-
public AugmentedNode<ILineSegment> pred(AugmentedNode<ILineSegment> n)
We can be guaranteed to be called with a LEAF node, since interior nodes are only guiding the process.
n
-
public void deleteRange(AugmentedNode<ILineSegment> left, AugmentedNode<ILineSegment> right)
All of these line segments potentially need to be reorganized once the sweep point advances.
left
- right
- public IPoint getSweepPoint()
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |