The ``first'' endpoint is an arbitrary choice and, at this first instant, no lists of active arcs exist. Therefore, a second sweep will have to be performed to take into account all the purple intersections with arcs that are still active after the last endpoint.
The first node corresponds to a BEGIN event. Arc h is included in the blue list.
The second node is the END of arc e. As no arc was in the red list, no action is taken.
In the fourth time instant, the END of arc h occurs. This arc is extracted from the blue list.
The sixth event is a BEGIN node, but still no intersections are registered.
In the fifteenth instant, arc a BEGINs, and the first intersection (with arc b) is registered.
Two events later BEGIN(e), a second purple intersection is detected (also with arc b).
The end of the first sweep occurs at the END of arc h.
The second sweep begins again at the BEGIN node of b, and the third purple intersection is detected.
The fourth and last bichromatic intersection happens in the 24th instant, where g BEGINs. The sweep continues until completing the second turn.
Unlike the situation depicted in the example, the normal situation will be that several arcs begin and others end at the same node. However, this fact does not affect the performance of the algorithm: simply treat each arc independently, the order is not relevant.
As for node-in-region inclusions, they are computed during the same sweeping operation: each region defines an interval on the sweep-line and it has to be determined which intervals of the opposite colour include the current endpoint. Each interval is defined by the upper and lower arcs bounding the region at every instant. Regions begin and end at given (not necessarily all) endpoints. The regions a, say, red node belongs to are computed by determining the blue arcs that cut the sweep-line above this node and then finding out if the regions underneath these arcs are bounded by arcs that cut the sweep-line below that node.
Last modified on friday, 15 February, 2002