Thread: Polygon Clipping Java, Help Please.

Hello, I am stuck on this Polygon Clipping Assignment.
This is what the result should look like.
clipTest.jpg

Here's the package I am working with. It's java so under the java folders. I am only allowed to edit the Clipper.java file.
cg1-clip.zip

This is what I have so far:

//
//  Clipper.java
//  
//
//  Created by Joe Geigel on 1/21/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//
 
/**
 * Object for performing clipping
 *
 */
 
public class clipper {
 
    /**
     * clipPolygon
     * 
     * Clip the polygon with vertex count in and vertices inx/iny
     * against the rectangular clipping region specified by lower-left corner
     * (x0,y0) and upper-right corner (x1,y1). The resulting vertices are
     * placed in outx/outy.  
     * 
     * The routine should return the with the vertex count of polygon
     * resultinhg from the clipping.
     *
     * @param in the number of vertices in the polygon to be clipped
     * @param inx - x coords of vertices of polygon to be clipped.
     * @param int - y coords of vertices of polygon to be clipped.
     * @param outx - x coords of vertices of polygon resulting after clipping.
     * @param outy - y coords of vertices of polygon resulting after clipping.
     * @param x0 - x coord of lower left of clipping rectangle.
     * @param y0 - y coord of lower left of clipping rectangle.
     * @param x1 - x coord of upper right of clipping rectangle.
     * @param y1 - y coord of upper right of clipping rectangle.
     *
     * @return number of vertices in the polygon resulting after clipping
     * 
     */
	public float intersectX;
	public float intersectY;
	public float clipXmin;
	public float clipYmin;
	public float clipYmax;
	public float clipXmax;
	public int clipBorder;
 
    public int clipPolygon(int in, float inx[], float iny[], float outx[],
                float outy[],  float x0, float y0, float x1, float y1)
    {
        int numberOfVerticies = 0;
        int n;
 
        float Lx,Ly,Cx,Cy;
 
        Lx = inx[in-1];
        Ly = iny[in-1];
 
        for (n = 0; n < in; n++){
			Cx = inx[n];
			Cy = iny[n];
 
 
 
		if(isInside(Cx, Cy, clipBorder)){
			if(isInside(Lx,Ly,clipBorder)){
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
 
 
			}
			else{
				isIntersect(Lx,Ly,Cx,Cy,clipBorder);
				outx[numberOfVerticies] = intersectX;
				outy[numberOfVerticies] = intersectY;
				numberOfVerticies++;
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
 
 
			}
		}
		else{
				if(isInside(Lx,Ly,clipBorder)){
					isIntersect(Lx,Ly,Cx,Cy,clipBorder);
					outx[numberOfVerticies] = intersectX;
					outy[numberOfVerticies] = intersectY;
					numberOfVerticies++;
 
					}
				}
			Lx = Cx;
			Ly = Cy;
 
 
			}
        return numberOfVerticies; // should return number of verricies in clipped poly.
    }
 
 
 
public boolean isInside(float newX, float newY, int clipBorder){
	if(clipBorder == 0 && newY > clipYmin){
		return true;
	}
	else if(clipBorder == 1 && newX > clipXmin){
		return true;
	}
	else if(clipBorder == 2 && newY < clipYmax){
		return true;
	}
	else if (clipBorder == 3 && newX < clipXmax){
		return true;
	}
	return false;
}
public void isIntersect(float x0, float x1, float y0, float y1, int clipBorder){
	float xDifference = x1 -x0;
	float yDifference = y1 - y0;
 
	if(xDifference == 0 || yDifference == 0){
 
		if(clipBorder == 0){
			intersectX = x0;
			intersectY = clipYmin;
		}
		else if(clipBorder == 1){
			intersectX = clipXmin;
			intersectY = y0;
		}
		else if(clipBorder == 2){
			intersectX = x0;
			intersectY = clipYmax;
		}
		else if(clipBorder == 3){
			intersectX = clipXmax;
			intersectY = y0;
		}
		return;
	}
	if(clipBorder == 0){
 
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmin - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0 + ((clipYmax - y0)/(y1-y0/x1-x0));
		intersectY = clipYmin;
	}
	else if(clipBorder == 1){
		intersectX = clipXmin;
		intersectY = (y1-y0/x1-x0)*(clipXmax-x0) + y0;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmin - (int)x0))<<8) / ((int)xDifference))>>8);  
	}
	else if(clipBorder == 2){
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmax - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0+((clipYmin-y0)/(y1-y0/x1-x0));
		intersectY = clipYmax;
	}
	else if(clipBorder == 3){
		intersectX = clipXmax;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmax - (int)x0))<<8) / ((int)xDifference))>>8);  
		intersectY = (y1-y0/x1-x0)*(clipXmax-x0) + y0;
	}
}
 
}

What is your question?

What am I doing wrong?

I'm trying to clip out of some of the parts in each polygon. I'm stuck on that and I been debugging since this post but somehow my method isIntersect isn't being called/used. What I have now is all the polygon is filled but I need to make it look like the first image I posted.

Originally Posted by Norm

The calls to that method are nested inside some if statements. Do some debugging to see why the conditions are not correct for the code with the method call to be executed.
One debug technique is to add lots of println() statements to print out the values of variables that are used to control logic flow in the code.


Suggestion: remove all but one of the calls to the clipping code to reduce the debugging output.
One way is to wrap the code to be skipped inside of an if statement that is never true:

if(false) {   //  skip following code
 .....
   code to be skipped
....
} //  end if(false)

sweet, i'll try it.

--- Update ---

Alright, the condition is always true, it seems. Do you have any ideas how to fix this algorithm then?

It's suppose to clip the polygons so it's half shaded. The image is the results.
I did do the println() and it didn't help me to figure out why it's always true.

Originally Posted by Norm

What values do the variables need to have for the method to return false?
How can the variables ever get those values?

Add more printlns to show the values of the variables being used to determine true or false results.

Post the code with the println statements you are using so we can see if they are useful to show you what the code is doing.

//
//  Clipper.java
//  
//
//  Created by Joe Geigel on 1/21/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//
 
/**
 * Object for performing clipping
 *
 */
 
public class clipper {
 
    /**
     * clipPolygon
     * 
     * Clip the polygon with vertex count in and vertices inx/iny
     * against the rectangular clipping region specified by lower-left corner
     * (x0,y0) and upper-right corner (x1,y1). The resulting vertices are
     * placed in outx/outy.  
     * 
     * The routine should return the with the vertex count of polygon
     * resultinhg from the clipping.
     *
     * @param in the number of vertices in the polygon to be clipped
     * @param inx - x coords of vertices of polygon to be clipped.
     * @param int - y coords of vertices of polygon to be clipped.
     * @param outx - x coords of vertices of polygon resulting after clipping.
     * @param outy - y coords of vertices of polygon resulting after clipping.
     * @param x0 - x coord of lower left of clipping rectangle.
     * @param y0 - y coord of lower left of clipping rectangle.
     * @param x1 - x coord of upper right of clipping rectangle.
     * @param y1 - y coord of upper right of clipping rectangle.
     *
     * @return number of vertices in the polygon resulting after clipping
     * 
     */
	private float intersectX;
	private float intersectY;
	private float clipXmin;
	private float clipYmin;
	private float clipYmax;
	private float clipXmax;
	private int clipBorder;
 
    public int clipPolygon(int in, float inx[], float iny[], float outx[],
                float outy[],  float x0, float y0, float x1, float y1)
    {
        int numberOfVerticies = 0;
        int n;
 
        float Lx,Ly,Cx,Cy;
 
        Lx = inx[in-1];
        Ly = iny[in-1];
 
        for (n = 0; n < in; n++){
			Cx = inx[n];
			Cy = iny[n];
 
 
 
		if(isInside(Cx, Cy, clipBorder)){
			System.out.println("true if the verticies are inside");
			if(isInside(Lx,Ly,clipBorder)){
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
				System.out.println("set verticies");
 
			}
			else{
 
				isIntersect(Lx,Ly,Cx,Cy,clipBorder);
				outx[numberOfVerticies] = intersectX;
				outy[numberOfVerticies] = intersectY;
				numberOfVerticies++;
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
				System.out.println("If the clipping window intersects the vertices");
 
			}
		}
		else{
				if(isInside(Lx,Ly,clipBorder)){
					isIntersect(Lx,Ly,Cx,Cy,clipBorder);
					outx[numberOfVerticies] = intersectX;
					outy[numberOfVerticies] = intersectY;
					numberOfVerticies++;
					System.out.println("Set new verticies if intersected");
					}
				}
			Lx = Cx;
			Ly = Cy;
 
 
			}
        return numberOfVerticies; // should return number of verricies in clipped poly.
    }
 
 
 
public boolean isInside(float newX, float newY, int clipBorder){
	if(clipBorder == 0 && newY > clipYmin){
		return true;
	}
	else if(clipBorder == 1 && newX > clipXmin){
		return true;
	}
	else if(clipBorder == 2 && newY < clipYmax){
		return true;
	}
	else if (clipBorder == 3 && newX < clipXmax){
		return true;
	}
	return false;
}
public void isIntersect(float x0, float x1, float y0, float y1, int clipBorder){
	float xDifference = x1 -x0;
	float yDifference = y1 - y0;
 
	if(xDifference == 0 || yDifference == 0){
 
		if(clipBorder == 0){
			intersectX = x0;
			intersectY = y0;
		}
		else if(clipBorder == 1){
			intersectX = x1;
			intersectY = y0;
		}
		else if(clipBorder == 2){
			intersectX = x0;
			intersectY = y1;
		}
		else if(clipBorder == 3){
			intersectX = x1;
			intersectY = y0;
		}
		return;
	}
	if(clipBorder == 0){
 
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmin - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0 + ((clipYmax - y0)/(y1-y0/x1-x0));
		intersectY = y1;
	}
	else if(clipBorder == 1){
		intersectX = x0;
		intersectY = (y1-y0/x1-x0)*(clipXmin-x0) + y0;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmin - (int)x0))<<8) / ((int)xDifference))>>8);  
	}
	else if(clipBorder == 2){
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmax - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0+((clipYmin-y0)/(y1-y0/x1-x0));
		intersectY = y0;
	}
	else if(clipBorder == 3){
		intersectX = x1;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmax - (int)x0))<<8) / ((int)xDifference))>>8);  
		intersectY = (y1-y0/x1-x0)*(clipXmax-x0) + y0;
	}
}
 
}

Originally Posted by Norm

Your printlns don't show the values of ANY of the variables used in the logic. You need to see the values of ALL the variables used in the logic so you see what the program is doing. For example, you need to print the values of all 3 of the variables used in this statement and others like it:

	if(clipBorder == 0 && newY > clipYmin){

//
//  Clipper.java
//  
 
//
 
/**
 * Object for performing clipping
 *
 */
 
public class clipper {
 
    /**
     * clipPolygon
     * 
     * Clip the polygon with vertex count in and vertices inx/iny
     * against the rectangular clipping region specified by lower-left corner
     * (x0,y0) and upper-right corner (x1,y1). The resulting vertices are
     * placed in outx/outy.  
     * 
     * The routine should return the with the vertex count of polygon
     * resultinhg from the clipping.
     *
     * @param in the number of vertices in the polygon to be clipped
     * @param inx - x coords of vertices of polygon to be clipped.
     * @param int - y coords of vertices of polygon to be clipped.
     * @param outx - x coords of vertices of polygon resulting after clipping.
     * @param outy - y coords of vertices of polygon resulting after clipping.
     * @param x0 - x coord of lower left of clipping rectangle.
     * @param y0 - y coord of lower left of clipping rectangle.
     * @param x1 - x coord of upper right of clipping rectangle.
     * @param y1 - y coord of upper right of clipping rectangle.
     *
     * @return number of vertices in the polygon resulting after clipping
     * 
     */
	private float intersectX;
	private float intersectY;
	private float clipXmin;
	private float clipYmin;
	private float clipYmax;
	private float clipXmax;
	private int clipBorder;
 
    public int clipPolygon(int in, float inx[], float iny[], float outx[],
                float outy[],  float x0, float y0, float x1, float y1)
    {
        int numberOfVerticies = 0;
        int n;
 
        float Lx,Ly,Cx,Cy;
 
        Lx = inx[in-1];
        Ly = iny[in-1];
 
        for (n = 0; n < in; n++){
			Cx = inx[n];
			Cy = iny[n];
 
		System.out.println(intersectX);	
		System.out.println(intersectY);
		System.out.println(Lx);
		System.out.println(Ly);
		System.out.println(Cx);
		System.out.println(Cy);
		System.out.println(numberOfVerticies);
 
 
 
		if(isInside(Cx, Cy)){
 
			if(isInside(Lx,Ly)){
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
 
 
			}
			else{
 
				isIntersect(x0, x1, y0, y1);
				outx[numberOfVerticies] = intersectX;
				outy[numberOfVerticies] = intersectY;
				numberOfVerticies++;
				outx[numberOfVerticies] = Cx;
				outy[numberOfVerticies] = Cy;
				numberOfVerticies++;
				System.out.println("If the clipping window intersects the vertices");
 
			}
		}
		else{
				if(isInside(Lx,Ly)){
					isIntersect(x0, x1, y0, y1);
					outx[numberOfVerticies] = intersectX;
					outy[numberOfVerticies] = intersectY;
					numberOfVerticies++;
					System.out.println("Set new verticies if intersected");
					}
				}
			Lx = Cx;
			Ly = Cy;
 
 
			}
        return numberOfVerticies; // should return number of verricies in clipped poly.
    }
 
 
 
public boolean isInside(float newX, float newY){
	System.out.println(newY);
	System.out.println(newX);
	System.out.println(clipBorder);
	System.out.println(clipYmin);
	System.out.println(clipYmax);
	System.out.println(clipXmax);
	System.out.println(clipXmin);
 
	if(clipBorder == 0 && newY > clipYmin){
		return true;
	}
	else if(clipBorder == 1 && newX > clipXmin){
		return true;
	}
	else if(clipBorder == 2 && newY < clipYmax){
		return true;
	}
	else if (clipBorder == 3 && newX < clipXmax){
		return true;
	}
	return false;
}
public void isIntersect(float x0, float x1, float y0, float y1){
	float xDifference = x1 -x0;
	float yDifference = y1 - y0;
 
	if(xDifference == 0 || yDifference == 0){
 
		if(clipBorder == 0){
			intersectX = x0;
			intersectY = y0;
		}
		else if(clipBorder == 1){
			intersectX = x1;
			intersectY = y0;
		}
		else if(clipBorder == 2){
			intersectX = x0;
			intersectY = y1;
		}
		else if(clipBorder == 3){
			intersectX = x1;
			intersectY = y0;
		}
		return;
	}
	if(clipBorder == 0){
 
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmin - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0 + ((clipYmax - y0)/(y1-y0/x1-x0));
		intersectY = y1;
	}
	else if(clipBorder == 1){
		intersectX = x0;
		intersectY = (y1-y0/x1-x0)*(clipXmin-x0) + y0;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmin - (int)x0))<<8) / ((int)xDifference))>>8);  
	}
	else if(clipBorder == 2){
		//intersectX = x0 + ((((((int)xDifference) * ((int)clipYmax - (int)y0))<<8) / ((int)yDifference))>>8);
		intersectX = x0+((clipYmin-y0)/(y1-y0/x1-x0));
		intersectY = y0;
	}
	else if(clipBorder == 3){
		intersectX = x1;
		//intersectY = y0 + ((((((int)yDifference) * ((int)clipXmax - (int)x0))<<8) / ((int)xDifference))>>8);  
		intersectY = (y1-y0/x1-x0)*(clipXmax-x0) + y0;
	}
}
 
}

Originally Posted by Norm

What is being printed out? Does the output show you why the methods are always returning true?
What variable's values need to be changed for the method to return false?

The printed vaubles does not tell me what's going on. The intersectx and y are always 0 since i never instaniated that. LyxCxy are always changing.

Originally Posted by Norm

The changes in the values of the variables IS WHAT IS GOING ON. If the values of the variables never change, then there is nothing happening.

How would I do the intersect method? If clipBorder isn't working for me.

Originally Posted by Norm

Please explain what "isn't working" means.


What do you mean by "do the intersect method"?
What is the name of the method you are talking about? I don't see a method named: intersect()

I believe there is 2 types of polygons. I am using to clip with and the other is the polygon i need to clip. How am i suppose to clip with that polygon, I believe it's the x0,x1,y0,y1.

As for the intersect, I mean the method isIntersect().

Originally Posted by Norm

Are you saying that you don't know what clipping means or how one polygon clips another?

What happens with the first test where one polygon is inside the other?
What should the clipPolygon() method return and what values should it put into the two arrays: outx and outy?

Have you worked out why the isInside() method never returns false?
What is that method testing and what does it mean for it to return true or to return false?
It has 3 args. What are each of them used for?

I don't know how one polygon clips another is what i'm saying. The clipPolygon() should return the new vertices.
isInside is always true because there is no clipBorder value to compare it too?
The new X and Y variables are a temp variables to hold the new vertices, while the clipBorder should be the clip window that is comparing it too.

Well my professor taught us what clipping means but the thing is that I don't know how to implement it into code.

That's what i'm trying to do. Clip many sided polygons