WEILER-ATHERTON

The data structures are several circular linked lists of vertices which are also linked together and the clipping is done by traversing these. The lists could be doubly linked. This enables the traversal in either direction at any node in the list. Starting at a particular node and traversing in one direction will produce the interior polygon(s) while starting at a different node and traversing can produce the outside. Note that producing the exterior does need the doubly linking and care must be taken in performing the traversal.

- Pick an entry from the ENTERING list - it will be an intersection point (and delete it)
- Locate that point on the SUBJ list
- Traverse the current (SUBJ) list until you find the next intersection point - it should be an exiting or entering point. Output each vertex encountered to some data structure, say POLY
- Follow the link from the current (SUBJ) list to the other (CLIP) list and
- Continue the traversal until you find the next intersection (Note: delete each entering intersection from the ENTERING list - not the linked lists. By deleting it we will get the distinct intersecting polygons and not duplicate a polygon multiple times).
- Terminate the traversal when you get to an intersection that is the SAME as the initial one that you removed from the ENTERING list. At this point POLY will have one of the clip regions and can be output.
- REPEAT the construction and output of POLY until the ENTERING list is empty.

const int MAXVERT = 500; const int MAXPOLYV = 50; const int MAXH = 10; struct Point2D {float x,y; }; typedef Point2D Vertices[MAXVERT]; enum VerType = {Polygon, Intersection}; typedef struct ClipListRec * ClipPtr; struct ClipListRec { int Vindex; ClipPtr next; VerType Kind; float t; ClipPtr otherList; } struct Polygon { int nVertex; int vert[MAXPOLYV]; ClipPtr list; } struct GenPolygon { Polygon exterior; int numHoles; Polygon Holes[MAXH]; } GenPolygon Sub,Clip; int entering[MAXVERT],exiting[MAXVERT]; Vertices V; int numVertex = 0; // size of the array of verticies int clipPoly[MAXVERT]; // a clip polygon int readPoint(); { cin >> inX; cin >> inY; if (numVertex < MAXVERT) { V[numVertex].x = inX; V[numVertex].y = inY; idNo = numVertex; numVertex++; } else idNo = -1; return idNo; } void readPolygon (GenPolygon p) { cin >> p.exterior.nVertex; for (i = 0; i < p.exterior.nVertex; i++) { newId = readPoint(); if (newId < 0) error else { insertAtRear (p.exterior.list,newId); p.exterior.vert[i] = newId; } } // now do the holes basically the same way . . . } // the "main" program loop would then be (pseudocode) while (!EMPTY(entering)) { nextInter = delete (entering); SEARCH (SubjectPolygon,nextInter,ptr1); AddToOutputList (ptr1->. . .) StartPoint = ptr1->. . . ptr1 = prt1->next; while (ptr1->. . . != StartPoint) { AddToOutputList (ptr1->. . .); if (ptr1-> . . == INTERSECTION) ptr1 = prt1->otherList->next; else ptr1 = ptr1->next; } FixListForOutput(); DrawPolygon(); EmptyOutputList(); }