Bentley–Ottmann algorithm: Difference between revisions

Revision as of 21:15, 15 November 2011

Revision as of 16:28, 6 December 2011

Line 55:

==Notes==

{{reflist}}

==Pseudo-Code==

Initialize event queue x = all segment endpoints;

Sort x by increasing x and y;

Initialize sweep line SL to be empty;

Initialize output intersection list L to be empty;

While (x is nonempty) {

Let E = the next event from x;

If (E is a left endpoint) {

Let segE = E's segment;

Add segE to SL;

Let segA = the segment above segE in SL;

Let segB = the segment below segE in SL;

If (I = Intersect( segE with segA) exists)

Insert I into x;

If (I = Intersect( segE with segB) exists)

Insert I into x;

}

Else If (E is a right endpoint) {

Let segE = E's segment;

Let segA = the segment above segE in SL;

Let segB = the segment below segE in SL;

Remove segE from SL;

If (I = Intersect( segA with segB) exists)

If (I is not in x already) Insert I into x;

}

Else { // E is an intersection event

Add E to the output list L;

Let segE1 above segE2 be E's intersecting segments in SL;

Swap their positions so that segE2 is now above segE1;

Let segA = the segment above segE2 in SL;

Let segB = the segment below segE1 in SL;

If (I = Intersect(segE2 with segA) exists)

If (I is not in x already) Insert I into x;

If (I = Intersect(segE1 with segB) exists)

If (I is not in x already) Insert I into x;

}

remove E from x;

}

return L;

}

==References==