Fix My Bugs

If you’d like to see this code tidied up slightly and working in an example, see my post Liang-Barsky Polygon Clipping Example.

	//
	// This routine uses the Liang-Barsky algorithm for polygon clipping as
	// desribed in Foley & van Dam.  It's more efficient than the above
	// Sutherland-Hodgman, but produces redundent turning vertices at the
	// corners of the clip region.  This makes rendering as a series of
	// triangles very awkward.
	//

	public static final int INFINITY = 2147483647;

	public int LiangBarskyPolygonClip(
		int n,
		int [] x, int [] y,		// vertices of input polygon
		int [] u, int [] v) {	// vertices of output polygon

		int outCount = 0;

		int xIn, xOut, yIn, yOut;					// Coordinates of entry and exit points
		int tOut1, tIn2, tOut2;						// Parameter values of same
		int tInX, tOutX, tInY, tOutY;				// Parameter values for intersection
		int deltaX, deltaY;							// Direction of edge
		int i;

		// Assume polygon is closed
		x[n] = x[0];
		y[n] = y[0];

		for(i = 0; i < n; i++) {	// for each edge 

			deltaX = x[i+1] - x[i];	// determine direction of edge
			deltaY = y[i+1] - y[i];	

			// use this to determine which bounding lines for the clip region the
			// containing line hits first
			if((deltaX > 0) || (deltaX == 0 && x[i] > clip_x_max)) {
				xIn = clip_x_min; xOut = clip_x_max;
			} else {
				xIn = clip_x_max; xOut = clip_x_min;
			}
			if((deltaY > 0) || (deltaY == 0 && y[i] > clip_y_max)) {
				yIn = clip_y_min; yOut = clip_y_max;
			} else {
				yIn = clip_y_max; yOut = clip_y_min;
			}

			// find the t values for the x and y exit points
			if(deltaX != 0) {
				tOutX = ((xOut - x[i])<<8) / deltaX;
			} else if(x[i] <= clip_x_max && clip_x_min <= x[i])
				tOutX = INFINITY;
			else
				tOutX = -INFINITY;

			if(deltaY != 0) {
				tOutY = ((yOut - y[i])<<8) / deltaY;
			} else if(y[i] <= clip_y_max && clip_y_min <= y[i])
				tOutY = INFINITY;
			else
				tOutY = -INFINITY;

			// Order the two exit points
			if(tOutX < tOutY) {
				tOut1 = tOutX; tOut2 = tOutY;
			} else {
				tOut1 = tOutY; tOut2 = tOutX;
			}

			if(tOut2 > 0) {

				if(deltaX != 0)
					tInX = ((xIn - x[i])<<8) / deltaX;
				else
					tInX = -INFINITY;

				if(deltaY != 0)
					tInY = ((yIn - y[i])<<8) / deltaY;
				else
					tInY = -INFINITY;

				if(tInX < tInY)
					tIn2 = tInY;
				else
					tIn2 = tInX;

				if(tOut1 < tIn2) {	// no visible segment
					if(0 < tOut1 && tOut1 <= (1<<8)) {
						// line crosses over intermediate corner region
						if(tInX < tInY) {
							u[outCount] = xOut;
							v[outCount] = yIn;
						} else {
							u[outCount] = xIn;
							v[outCount] = yOut;
						}
						outCount++;
					}

				} else {

					// line crosses though window
					if(0 < tOut1 && tIn2 <= (1<<8)) {
						if(0 <= tIn2) {	// visible segment
							if(tInX > tInY) {
								u[outCount] = xIn;
								v[outCount] = y[i] + ((tInX * deltaY)>>8);
							} else {
								u[outCount] = x[i] + ((tInY * deltaX)>>8);
								v[outCount] = yIn;
							}
							outCount++;
						}

						if((1<<8) >= tOut1) {
							if(tOutX < tOutY) {
								u[outCount] = xOut;
								v[outCount] = y[i] + ((tOutX * deltaY)>>8);
							} else {
								u[outCount] = x[i] + ((tOutY * deltaX)>>8);
								v[outCount] = yOut;
							}
							outCount++;
						} else {
							u[outCount] = x[i+1];
							v[outCount] = y[i+1];
							outCount++;
						}
					}

				}

				if(0 < tOut2 && tOut2 <= (1<<8)) {
					u[outCount] = xOut;
					v[outCount] = yOut;
					outCount++;
				}

			}
		} 

		return outCount;
	}