Liang - Barsky Plygon clipping Algorithm

algorithm for Clipping Polygon Segments
INPUT : HSA=<h1,h2,...hn> (Half-segment Array)
 w = Rectangle
OUTPUT: cHSA = clipped half-segments and the half-segments
 resulting from the evaluation of turning points
cHSA = Ø;
turningPointSets = Ø;
FOR i=1 TO n DO
 IF (hi has left dominating point) THEN
 IF (SutherlandCohenLineClipping(hi, w, clippedhs, intersection-point,
 isIntersectionPoint)) THEN
 IF (isIntersectionPoint) THEN
 EvaluateTurningPoint(w, intersectionPoint, turningPointSets, hi);
 ELSE
 cHSA.Add(clippedhs);

algorithm to  EvaluateTurningPoint 
INPUT : w = a rectangle described by the coordinates (xmin, ymin) and (xmax, ymax)
 p = Point
 turningPointSets = for each window egde there is a set recording the
 turning point of the edge
 h = halfsegment that the point p belongs to
OUTPUT: If the point is evaluated as a turning point it is added to the Turning
 Point Set of the edge
 tp = p;
IF (p.x = w.xmin) THEN //left edge
 IF (h.insideAbove) THEN
 tp.direction = UP;
 ELSE
 Tp. direction = DOWN;
 END-IF;
 turningPointSets[LEFT].add(tp);
ELSE //right edge
 IF (h.insideAbove) THEN
 tp. direction = UP;
 ELSE
 tp. direction = DOWN;
 END-IF;
 turningPointSets[RIGHT].add(tp);
END-IF;
IF (p.y = w.ymin) THEN //bottom edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
ELSE
 IF (p.y = w.ymax) THEN //top edge
 IF (h.leftPoint > w.ymin) THEN
 tp.direction = GetDirection(p, h.leftPoint, xmin, ymin, h.insideAbove);
 ELSE
 tp.direction = GetDirection(p, h.rightPoint, xmin, ymin, h.insideAbove);
 END-IF;
 turningPointSets[BOTTOM].add(tp);
 END-IF;
END-IF;

algorithm to Get Direction 
INPUT: tp = turning point
 p = point of the same half segment that the turning point tp belongs
 and is above tp
 (x, y) = the left coordinate of the vertex of the window edge
 insideAbove = insideAbove flag’s value
IF (insideAbove) THEN
 IF (tp.x > p.x) THEN
 return RIGHT;
 ELSE
 return LEFT;
 END-IF;
ELSE
 IF (tp.x > p.x) THEN
 return LEFT;
 ELSE
 return RIGHT;
 END-IF;

algorithm to Create NewSegments
INPUT: edge = indicates which edge is been handled(LEFT, RIGHT, TOP or
 BOTTOM)
 bPoint,ePoint = end points of the edge
 turningPointSet = a set of the turning points of the edge
 cHSA = set of half segments in which the new half segments will be added

OUTPUT: cHSA with the new half segments
 IF edge == TOP or edge == LEFT THEN
 InsideAbove = false;
 ELSE /*RIGHT or BOTTOM edges*/
 InsideAbove = true;
 END-IF;
 begin = 0;
 end = turningPointSet.size();
 tp = turningPointSet[begin];
 IF (tp.Direction== LEFT or tp.Direction == DOWN) and not tp.Rejected THEN
 cHSA.addHalfSegments(tp,bPoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, tp, ASCENDIN_GORDER, begin);
 END-IF;
 tp = turningPointSet[end];
 IF (tp.Direction== RIGHT or tp.Direction == UP) and not tp.Rejected
 and there is no rejected turning point equals to tp THEN
 cHSA.addHalfSegments(tp,ePoint,InsideAbove);
 DiscardTurningPoints(turningPointSet, DESCENDING_ORDER, end);
 END-IF;
 WHILE (begin<end) DO
tp1 = GetNotRejectedTurningPoint(turningPointSet, ASCENDING_ORDER, begin);
IF tp1 == NULL THEN
 return;
END-IF;
tp2 = GetNotRejectedTurningPoint(turningPointSet, DESCENDING_ORDER, end);
IF tp2 == NULL THEN
 return;
END-IF;
cHSA.addHalfSegments(tp1,tp2,InsideAbove);
END-WHILE;

algorithm for  Polygon Reconstruction 

INPUT: HSA=<h1,h2,...hn> (Halfsegment Array) 

OUTPUT: HSA = each halfsegment has the face, cycle, and edge numbers set 

VARIABLES: face = array that stores in position i the last cycle number of the 

 face i 

 hsSet = array that stores in the position i if the half segment hi 

 had already the face number, the cycle number and the edge 

 number set. This array is initialized with values false. 

 IF HSA is not sorted in halfsegment order THEN 

 Sort HSA in halfsegment order; 

END-IF; 

IF the halfsegments of HSA do not have the partner number set THEN 

 Set partner number of the halfsegments of HSA; 

END-IF; 

face[0] = 0; /*0 is assigned to the first cycle of the first face */ 

lastFaceNumber = 0; 

isFirstHS = true; 

 FOR i=1 TO n DO 

 IF hi has left dominating point and not hsSet[i] THEN 

 IF isFirstHS THEN 

 isFirstHS = false; 

 hi.faceNumber = 0; 

 hi.cycleNumber = 0; 

 ELSE 

 existingFaceNumber = GetFaceNumber(HSA, hi, hsSet, i); 

 IF existingFaceNumber is equal to -1 THEN 

 lastFaceNumber++; 

 hi.faceNumber = lastFaceNumber; 

 hi.cycleNumber = 0; 

 /*to store the first cycle number of the face lastFace*/ 

 face[faceNumber-1]=0; 

 ELSE 

 hi.faceNumber = existingFaceNumber; 

 face[faceNumber]++; 

 hi.cycleNumber = face[faceNumber]; 

 END-IF; 

 END-IF; 

 hi.edgeNumber = 0; 

 ComputeCycle(HSA, hi, hsSet); 

 END-IF; 

 END-FOR; 

window clipping in 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingin( _, _ ) 

Meaning: computes the part of the object that is inside the window. 

Example: query Flaechen feed extend[InWindow: windowclippingin( 

 .geoData, bbox(thecenter))] project[InWindow] 

 filter[not(isempty(.InWindow))] consume 

 window clipping out 

Signature: (line x rect) -> line, (region x rect) --> region 

Syntax: windowclippingout( _, _ ) 

Meaning: computes the part of the object that is outside the window. 

Example: query windowclippingout(trajectory(train7), bbox(thecenter))