CS 535
WEILER-ATHERTON

PROBLEM

Implement Weiler-Atherton. You should draw each polygon in a different color and fill the clip areas generated with a third color.

NOTES:

The Weiler-Atherton algorithm is the most general of the clipping algorithms. We have two 2D polygons (may be convex or concave and they both may have holes). The polygon to be clipped is called the SUBJECT polygon and the polygon defining the clipping area is called the CLIP polygon. To make the algorithm work easier (in the data structures, etc.) we usually assume that the exterior vertices are given clockwise and the hole vertices are given counterclockwise. In clipping we usually want to find the parts of the subject polygon that are inside the clip polygon. However, this algorithm can be used in modeling to find the "union", "intersection", and "difference" of the polygons.

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.

STEP 1:

The first phase of the building of the data structures occurs when we input the edges and put them in two linked lists - the SUBJ list and the CLIP list. The vertices are place in order from input (thus clockwise). There are separate lists for the exterior and for each hole. Thus, the initial build is a standard queue insert (input a vertex - insert it at end of list). Note that this creates a list in which a standard list traversal is equivalent to "walking around" the polygon edge visiting the vertices in order.

STEP 2:

The second phase of the list building is computing and inserting the "real" INTERSECTION points (a point on both line segments). If we have a SUBJECT polygon edge (SV_i to SV_i+1) that intersects a CLIP polygon edge (CV_j to CV_j+1) at a point INTER. Note that the edges form straight lines that may intersect, we are assuming that the line segments SV_i to SV_i+1 intersects the line segment CV_j to CV_j+1. The intersection point INTER is then inserted on BOTH of the linked lists - SUBJ and CLIP. It is inserted BETWEEN SV_i and SV_i+1 on the SUBJ list and CV_j and CV_j+1 on the CLIP list. The idea is still that traversing the list using a standard list traversal we would encounter the points in their geometric order. Note that there may be several intersection points between any given pair of vertices and they must be inserted in the correct order in the lists. This is done by using the t and u values computed in the vector line intersection subprogram. Each intersection point thus has TWO nodes - one on each list (SUBJ and CLIP). We link these two entries together which provides a way of getting from one list to the other.

STEP 2.5:

Any straight line divides the plane into two half-planes. Thus each polygon edge (extended to a line) will divide the plane into two half-planes. Because we listed the vertices clockwise, we consider the half-plane to the right as containing the interior of the polygon. Thus the right half-plane is called the interior half-plane. If we consider ourselves as "walking along" a polygon edge, then we can categorize each of the INTERSECTION points as "entering" or "exiting". This is usually done from the SUBJ polygon's point of view. Thus, as we walk along the SUBJ polygon edge SV_i to SV_i+1 and we encounter intersection point INTER, we can ask the question - am I "entering" the CLIP polygon or am I "exiting" the CLIP polygon? The second part of computing the intersection point is to classify them as "entering" or "exiting". We create one or two lists - one for entering intersections and one for exiting intersections.

STEP3:

Once the lists are built the basic idea to do the clipping is as follows

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.

Remark: For the exterior, try starting with an EXITING point. Start the traversal on the SUBJ list (same direction as the Interior). At what point do you need to use the double link and to traverse in the opposite direction? (Hint: look at the CLIP polygon list).

IMPLEMENTATION:

In the below data structures we place all of the vertices and intersection points in a 1D array and use the subscript instead of the actual coordinates.

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();
}

CS 535 WEILER-ATHERTON