/** ChainHull Method **/ import java.awt.*; import java.io.*; import java.util.*; import java.net.*; import ciips.animation.*; import ciips.animation.graph.*; public class StackConvex { private DrawingPanel dp; public Point H[],cloneP[]; int a_size; Font font = new Font("Dialog", Font.PLAIN, 12); private static String pointstack = "Stack : "; AlgThread alg; static final boolean DEBUG = true; public StackConvex( AlgThread alg, DrawingPanel gp ) { this.alg = alg; dp = gp; } // chainHull_2D(): Andrew's monotone chain 2D convex hull algorithm // Input: P[] = an array of 2D points // presorted by increasing x- and y-coordinates // n = the number of points in P[] // Output: H[] = an array of the convex hull vertices (max is n) // Return: the number of points in H[] /*------------------------*/ public int ChainHull_2D( Point[] P, int n ) { H = new Point[n]; /*-*/cloneP = new Point[n]; /*-*/a_size = n; /*-*/for (int i =0 ; i < n ; i++) /*-*/{ /*-*/ cloneP[i] = P[i]; /*-*/} /*-*/ alg.frame.setText(0, "Running ChainHull Algorithm..."); // the output array H[] will be used as the stack /*-*/GraphDraw gd = new GraphDraw( P,n); /*-*/dp.addDrawingObj(gd); int bot=0, top=(-1); // indices for bottom and top of the stack int i; // array scan index // Get the indices of points with min x-coord and min|max y-coord int minmin = 0, minmax; float xmin = P[0].x; for (i=1; i=0; i--) if (P[i].x != xmax) break; maxmin = i+1; // Compute the lower hull on the stack H H[++top] = P[minmin]; // push minmin point onto stack i = minmax; /*-*/ alg.frame.setText(1, "Finding minmin, minmax, maxmin, maxmax...."); /*-*/dp.delay(); /*-*/ alg.frame.setText(1, "Finding minmin : P"+minmin+" , minmax : P"+minmax+", maxmin : P"+maxmin+"maxmax : P"+maxmax+"...."); /*-*/AlgAnimFrame.pauseStep(); /*-*///선 두개 그리기 /*-*/gd.setpointDraw(true); /*-*/gd.drawPLine(minmin, maxmin); /*-*/gd.drawPLine(minmax, maxmax); /*-*/AlgAnimFrame.pauseStep(); /*-*/printtStack(top); while (++i <= maxmin) { /*-*/dp.shuffleDown(); /*-*///여지까지 그린 선 다 그리고 여기서 한번 그리고 // the lower line joins P[minmin] with P[maxmin] if (isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin) { /*-*/ComBox above = new ComBox(P[i].x*5, 420 - P[i].y*5 + 15 , "Above the lower line", font); /*-*/dp.addCom(above); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); continue; // ignore P[i] above or on the lower line } while (top > 0) // there are at least 2 points on the stack { // test if P[i] is left of the line at the stack top if (isLeft( H[top-1], H[top], P[i]) > 0) { /*-*/String lefts = "P"+i+" is left of the line"; /*-*/ComBox left = new ComBox(P[i].x*5 , 405 - P[i].y * 5,lefts,font); /*-*/dp.addCom(left); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); break; // P[i] is a new hull vertex } else { /*-*/String lefts = "P"+i+" is right of the line, POP OFF FROM STACK"; /*-*/ComBox left = new ComBox(P[i].x*5 , 405 - P[i].y * 5,lefts,font); /*-*/dp.addCom(left); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/gd.erasePLine(); /*-*/dp.redraw(); /*-*/top--; // pop top point off stack /*-*/printtStack(top); } /*-*/AlgAnimFrame.pauseStep(); } /*-*/H[++top] = P[i]; // push P[i] onto stack /*-*/gd.drawPLine(findStack(H[top]),findStack(H[top-1])); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); /*-*/printtStack(top); /*-*/dp.shuffleDown(); } // Next, compute the upper hull on the stack H above the bottom hull if (maxmax != maxmin) // if distinct xmax points H[++top] = P[maxmax]; // push maxmax point onto stack bot = top; // the bottom point of the upper hull stack i = maxmin; /*-*/gd.drawPLine(findStack(H[top]),findStack(H[top-1])); while (--i >= minmax) { /*-*/dp.shuffleDown(); // the upper line joins P[maxmax] with P[minmax] if (isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax) { /*-*/ComBox below = new ComBox(P[i].x*5, 420 - P[i].y*5 + 15 , "below the upper line", font); /*-*/dp.addCom(below); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); continue; // ignore P[i] below or on the upper line } while (top > bot) // at least 2 points on the upper stack { // test if P[i] is left of the line at the stack top if (isLeft( H[top-1], H[top], P[i]) > 0) { /*-*/String lefts = "P"+i+" is left of the line"; /*-*/ComBox left = new ComBox(P[i].x*5 , 405 - P[i].y * 5,lefts,font); /*-*/dp.addCom(left); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); break; // P[i] is a new hull vertex } else { /*-*/String lefts = "P"+i+" is right of the line, POP OFF FROM STACK"; /*-*/ComBox left = new ComBox(P[i].x*5 , 405 - P[i].y * 5,lefts,font); /*-*/dp.addCom(left); /*-*/dp.redraw(); /*-*/dp.delay(); /*-*/dp.removeAllCom(); /*-*/gd.erasePLine(); /*-*/dp.redraw(); top--; // pop top point off stack /*-*/printtStack(top); } /*-*/AlgAnimFrame.pauseStep(); } H[++top] = P[i]; // push P[i] onto stack /*-*/printtStack(top); /*-*/gd.drawPLine(findStack(H[top]),findStack(H[top-1])); /*-*/dp.removeAllCom(); /*-*/dp.redraw(); /*-*/dp.shuffleDown(); } if (minmax != minmin) H[++top] = P[minmin]; // push joining endpoint onto stack /*-*/gd.drawPLine(findStack(H[top]),findStack(H[top-1])); /*-*/printtStack(top); return top+1; } //---------------- public float isLeft(Point P0, Point P1, Point P2) { float ans = (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y); return ans; } private void printtStack(int size) { String output=""; for (int i = size ;i>0 ;i-- ) { output ="P"+findStack(H[i])+" "+output; } alg.frame.setText(3, output); } private int findStack(Point toFind) { for(int i =0 ; i < a_size;i++) { if(toFind.equals(cloneP[i])) return i; } return 100; } }