import java.util.ArrayList; import java.util.Collections; import java.text.*; class ConvexHull{ /* * Given N Numbers of Two Dimensional Coordinate * Find the Convex Hull */ class Node{ private int x; private int y; private boolean bool; //Methods for Node public void setX(int x){ this.x = x; } public void setY(int y){ this.y = y; } public void setConvex(boolean bool){ this.bool = bool; } public int getX(){ return this.x; } public int getY(){ return this.y; } public boolean onConvexHull(){ return this.bool; } public boolean isCoordinate(int cx, int cy){ if( this.x==cx && this.y==cy ) return true; else return false; } } class Line{ private Node pointOne; private Node pointTwo; private float slope; //Methods for Line public void setPointOne(Node one){ this.pointOne = one; } public void setPointTwo(Node two){ this.pointTwo = two; } public void setSlope(float slope){ this.slope = slope; } public Node getPointOne(){ return this.pointOne; } public Node getPointTwo(){ return this.pointTwo; } public float getSlope(){ return this.slope; } } //===================================== //===================================== public static void main(String[] args){ ConvexHull main = new ConvexHull(); Node[] coordinates = new Node[10]; // The numbers of coordinate ArrayList lineList = new ArrayList<>(); main.initCoordinate(coordinates); //main.printCoordinate(coordinates); main.sortNodes(coordinates); main.printGraph(coordinates); //main.printCoordinate(coordinates); main.findConvexHull(coordinates, lineList); main.printLine(lineList); } //===================================== //===================================== private void initCoordinate(Node[] coordinates){ for(int i = 0; i < coordinates.length; i++){ coordinates[i] = new Node(); coordinates[i].setX((int)(Math.random()*10+1)); coordinates[i].setY((int)(Math.random()*10+1)); } } private void findConvexHull(Node[] coordinates, ArrayList lineList){ ArrayList convexList = new ArrayList<>(); convexList.add(coordinates[0]); findLowerHull(coordinates, convexList); //printConvexList(convexList); findUpperHull(coordinates, convexList); //printConvexList(convexList); pointToConvex(convexList, lineList); //System.out.println("The First Index from Left:"+firstNode); } private void findLowerHull(Node[] coordinates, ArrayList convexList){ //From left to right ==> Lower Hull int nextIndex = 0; do{ float minSlope = 101; int mainIndex = nextIndex; for(int i = nextIndex; i < coordinates.length-1; i++){ float tmpSlope = slope(coordinates[mainIndex], coordinates[i+1]); //System.out.println("minSlope:"+minSlope); //System.out.println("tmpSlope:"+tmpSlope); if(tmpSlope < minSlope){ minSlope = tmpSlope; nextIndex = i+1; } } //System.out.println("nextIndex:"+nextIndex); convexList.add(coordinates[nextIndex]); coordinates[nextIndex].setConvex(true); }while(nextIndex < coordinates.length-1); } private void findUpperHull(Node[] coordinates, ArrayList convexList){ //From right to left ==> Upper Hull int nextIndex = coordinates.length-1; do{ float minSlope = 101; int mainIndex = nextIndex; for(int i = nextIndex; i > 0; i--){ float tmpSlope = slope(coordinates[mainIndex], coordinates[i-1]); if(tmpSlope < minSlope){ minSlope = tmpSlope; nextIndex = i-1; } } //System.out.println("nextIndex:"+nextIndex); convexList.add(coordinates[nextIndex]); coordinates[nextIndex].setConvex(true); }while(nextIndex > 0); } private float slope(Node x, Node y){ if(y.getX()==x.getX())return 100; return (float)(y.getY()-x.getY())/(float)(y.getX()-x.getX()); } private void sortNodes(Node[] coordinates){ //For Andrew's Monotone Chain //Sort from left to right and from bottom to top for(int i = 0; i < coordinates.length; i++){ for(int j = i+1; j < coordinates.length; j++){ if(coordinates[j].getX() < coordinates[i].getX()){ swap(coordinates, i, j); }else if(coordinates[j].getX() == coordinates[i].getX()){ if(coordinates[j].getY() < coordinates[i].getY()){ swap(coordinates, i, j); } } } } } private void swap(Node[] coordinates, int a, int b){ Node tmp = coordinates[a]; coordinates[a] = coordinates[b]; coordinates[b] = tmp; } private void pointToConvex(ArrayList convexList, ArrayList lineList){ for(int i = 0; i < convexList.size()-1; i++){ Line line = new Line(); line.setPointOne(convexList.get(i)); line.setPointTwo(convexList.get(i+1)); lineList.add(line); } } private double getDistance(Node a, Node b){ return Math.sqrt((a.getX()-b.getX())*(a.getX()-b.getX())+(a.getY()-b.getY())*(a.getY()-b.getY())); } private void printCoordinate(Node[] coordinates){ for(int i = 0; i < coordinates.length; i++){ System.out.print("("+coordinates[i].getX()+","); System.out.print(coordinates[i].getY()+")"); System.out.println(" onConvexHull:"+coordinates[i].onConvexHull()); } } private void printConvexList(ArrayList convexList){ System.out.print("ConvexList:"); convexList.forEach((node)->System.out.print("("+node.getX()+","+node.getY()+")")); System.out.println(); } private void printLine(ArrayList lineList){ System.out.println("Convex Hull"); lineList.forEach((line)->System.out.println("("+line.getPointOne().getX()+","+line.getPointOne().getY()+")->"+"("+line.getPointTwo().getX()+","+line.getPointTwo().getY()+")")); } private void printGraph(Node[] coordinates){ //System.out.println("All coordinate"); for(int j = 10; j >= 0; j--){ if(j>=10){ System.out.print(j); }else{ System.out.print(" "+j); } for(int i = 0; i < 11; i++){ boolean hasPoint = false; for(int k = 0; k < coordinates.length; k++){ hasPoint = coordinates[k].isCoordinate(i,j); if(hasPoint)break; } if(hasPoint) System.out.print("-o-"); else System.out.print("-|-"); } System.out.println(); } System.out.println(" 0 1 2 3 4 5 6 7 8 9 10"); } }

Convex Hull 2018/11/08