Algorithms in a Nutshell

LineSweep | 275

Computational

Geometry

intersections (ILineSegment[] segs){

// construct Event Queue from segments. Ensure that only unique

// points appear by combining all information as it is discovered

for (ILineSegment ils : segs) {

EventPoint ep = new EventPoint(ils.getStart( ));

EventPoint old = eq.event(ep);

if (old == null) { eq.insert(ep); } else { ep = old; }

// add upper line segments to ep (the object in the queue)

ep.addUpperLineSegment(ils);

ep = new EventPoint(ils.getEnd( ));

old = eq.event(ep);

if (old == null) { eq.insert(ep); } else { ep = old; }

// add lower line segments to ep (the object in the queue)

ep.addLowerLineSegment(ils);

}

// Sweep top to bottom, processing each Event Point in the queue

while (!eq.isEmpty( )) {

EventPoint p = eq.min( );

handleEventPoint(p);

}

// return report of all computed intersections

return report;

}

// Process events by updating line state and reporting intersections.

private void handleEventPoint (EventPoint ep) {

// Find segments, if they exist, to left (and right) of ep in

// linestate Intersections can only happen between neighboring

// segments. Start with nearest ones because as line sweeps down

// we will find any other intersections that (for now) we put off.

AugmentedNode<ILineSegment> left = lineState.leftNeighbor(ep);

AugmentedNode<ILineSegment> right = lineState.rightNeighbor(ep);

// determine intersections 'ints' from neighboring line segments and

// get upper segments 'ups' and lower segments 'lows' for this event

// point. An intersection exists if > 1 segment is associated with

// event point

lineState.determineIntersecting(ep, left, right);

List<ILineSegment> ints = ep.intersectingSegments( );

List<ILineSegment> ups = ep.upperEndpointSegments( );

List<ILineSegment> lows = ep.lowerEndpointSegments( );

if (lows.size() + ups.size( ) + ints.size( ) > 1) {

record (ep.p, new List[]{lows,ups,ints});

}

// Delete everything after left until left's successor is right.

// Then update the sweep point, so insertions will be ordered. Only

// ups and ints are inserted because they are still active.

Example 9-3. LineSweep Java implementation (continued)

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use