Victoria Vancouver Saskatoon Calgary Edmonton Regina Ft. Simpson Whitehorse Yellowknife Echo Bay Dawson Lynn Lake Victoria Vancouver Saskatoon Calgary Edmonton Regina Ft. Simpson Whitehorse Yellowknife Echo Bay Dawson Lynn Lake Prince Rupert Dawson Creek Uranium City Uranium CityPrince Rupert Dawson Creek grizzly bear y x event point sj sk sl sm new neighbors p si sj si sj sk intersection detected sj sk sl sm sk sl sm si sk sl sm si sj sk sl sm sk si sl sj sj T T s3 T s8 s3 s1 s7 s8 s3 s1 s4 s5 s1 s2 s3 s7 s5 s4 s1 s8 s7 s7 s7 s3 s5 s4 s1 s2 s3 s1 s2 s1 s2 s3 s4 s5 face vertex edge disconnected subdivision e v w Twin(e) e Prev(e) Next(e) IncidentFace(e) Origin(e) Twin(e) e1,1 e1,2 e2,1 e2,2 e3,1 e3,2 e4,2 e4,1 v1 v2 v3 v4 f1 f2 =⇒ the geometric situation and the two doubly-connected edge lists before handling the intersection e v the doubly-connected edge list after handling the intersection e e e e first clockwise half-edge from e with v as its origin f C1 C∞ C2 C3 C4 C6 C5 C7 C1 C3 C6 C∞ C2 C5 C4 C7 G new arc C C f C C G fv P1 P2 P1 P2 P1 P2 union intersection difference p not visible