JAVA凸包算法

　　源碼一JarvisMarchjava

　　package nvex;

　　import static javalangMathabs;

　　import javautilIterator;

　　import javautilLinkedList;

　　import javautilList;

　　public class JarvisMarch {

　　private int count;

　　public int getCount() {

　　return count;

　　}

　　public void setCount(int count) {

　　unt = count;

　　}

　　private static int MAX_ANGLE = ;

　　private double currentMinAngle = ;

　　private List<Point> hullPointList;

　　private List<Integer> indexList;

　　private PointFactory pf;

　　private Point[] ps;

　　public Point[] getPs() {

　　return ps;

　　}

　　private int firstIndex;

　　public int getFirstIndex() {

　　return firstIndex;

　　}

　　public JarvisMarch() {

　　this();

　　}

　　public JarvisMarch(int count) {

　　pf = PointFactorygetInstance(count);

　　initialize();

　　}

　　public JarvisMarch(int[] x int[] y) {

　　pf = PointFactorygetInstance(x y);

　　initialize();

　　}

　　private void initialize() {

　　hullPointList = new LinkedList<Point>();

　　indexList = new LinkedList<Integer>();

　　firstIndex = pfgetFirstIndex();

　　ps = pfgetPoints();

　　addToHull(firstIndex);

　　}

　　private void addToHull(int index) {

　　indexListadd(index);

　　hullPointListadd(ps[index]);

　　}

　　public int calculateHull() {

　　for (int i = getNextIndex(firstIndex); i != firstIndex; i = getNextIndex(i)) {

　　addToHull(i);

　　}

　　showHullPoints();

　　return ;

　　}

　　private void showHullPoints() {

　　Iterator<Point> itPoint = erator();

　　Iterator<Integer> itIndex = erator();

　　Point p;

　　int i;

　　int index = ;

　　Systemoutprintln(The hull points is: > );

　　while (itPointhasNext()) {

　　i = itIndexnext();

　　p = itPointnext();

　　Systemoutprint(i + :( + pgetX() + + pgetY() + )  );

　　index++;

　　if (index % == )

　　Systemoutprintln();

　　}

　　Systemoutprintln();

　　Systemoutprintln(****************************************************************);

　　Systemoutprintln(The count of all hull points is + index);

　　}

　　public int getNextIndex(int currentIndex) {

　　double minAngle = MAX_ANGLE;

　　double pseudoAngle;

　　int minIndex = ;

　　for (int i = ; i < pslength; i++) {

　　if (i != currentIndex) {

　　pseudoAngle = getPseudoAngle(ps[i]getX() ps[currentIndex]getX()

　　ps[i]getY() ps[currentIndex]getY());

　　if (pseudoAngle >= currentMinAngle && pseudoAngle < minAngle) {

　　minAngle = pseudoAngle;

　　minIndex = i;

　　} else if (pseudoAngle == minAngle){

　　if((abs(ps[i]getX() ps[currentIndex]getX()) >

　　abs(ps[minIndex]getX() ps[currentIndex]getX()))

　　|| (abs(ps[i]getY() ps[currentIndex]getY()) >

　　abs(ps[minIndex]getY() ps[currentIndex]getY()))){

　　minIndex = i;

　　}

　　}

　　}

　　}

　　currentMinAngle = minAngle;

　　return minIndex;

　　}

　　public double getPseudoAngle(double dx double dy) {

　　if (dx > && dy >= )

　　return dy / (dx + dy);

　　if (dx <= && dy > )

　　return + (abs(dx) / (abs(dx) + dy));

　　if (dx < && dy <= )

　　return + (dy / (dx + dy));

　　if (dx >= && dy < )

　　return + (dx / (dx + abs(dy)));

　　throw new Error(Impossible);

　　}

　　}

　　源碼二Pointjava

　　package nvex;

　　public class Point {

　　//    定義點的xy坐標之所以是int類型是為了日後可以在計算機屏幕上進行可視化

　　private int x;

　　private int y;

　　//    xy的get方法

　　public int getX() {

　　return x;

　　}

　　public int getY() {

　　return y;

　　}

　　//    定義點到屏幕邊緣的距離

　　private static double PADDING = ;

　　//    點在屏幕中的范圍

　　private static double POINT_RANGE = ( PADDING * );

　　//    默認構造方法產生隨機點

　　public Point() {

　　thisx = (int) ((Mathrandom() * POINT_RANGE) + PADDING);

　　thisy = (int) ((Mathrandom() * POINT_RANGE) + PADDING);

　　}

　　//    帶參構造方法可以實現手動輸入固定點

　　public Point(int x int y) {

　　thisx = x;

　　thisy = y;

　　}

　　//    覆寫hashCode()和equals()方法實現比較和Hash

　　@Override

　　public int hashCode() {

　　final int prime = ;

　　int result = ;

　　result = prime * result + x;

　　result = prime * result + y;

　　return result;

　　}

　　@Override

　　public boolean equals(Object obj) {

　　Point other = (Point) obj;

　　if ((x == otherx) && (y == othery))

　　return true;

　　return false;

　　}

　　}

　　源碼三PointFactoryjava

　　package nvex;

　　public class PointFactory {

　　/**

　　* 單例模式大批量產生Point也可以手動產生Point

　　*/

　　private Point[] points = null;

　　private int newIndex;

　　private int firstIndex = ;

　　public Point[] getPoints() {

　　return points;

　　}

　　public int getFirstIndex() {

　　return firstIndex;

　　}

　　public static PointFactory getInstance() {

　　return new PointFactory();

　　}

　　public static PointFactory getInstance(int count) {

　　return new PointFactory(count);

　　}

　　public static PointFactory getInstance(int[] x int[] y) {

　　return new PointFactory(x y);

　　}

　　private PointFactory() {

　　this();

　　}

　　private PointFactory(int count) {

　　points = new Point[count];

　　for (int i = ; i < count; i++) {

　　points[i] = new Point();

　　newIndex = i;

　　validatePoints();

　　}

　　firstIndex = getFirstPoint();

　　}

　　public PointFactory(int[] x int[] y) {

　　points = new Point[ylength];

　　for (int i = ; i < ylength; i++) {

　　points[i] = new Point(x[i] y[i]);

　　}

　　firstIndex = getFirstPoint();

　　}

　　private void validatePoints() {

　　for(int i = ; i < newIndex; i++) {

　　if(points[i]equals(points[newIndex])) {

　　points[newIndex] = new Point();

　　validatePoints();

　　}

　　}

　　}

　　public int getFirstPoint() {

　　int minIndex = ;

　　for (int i = ; i < pointslength; i++) {

　　if (points[i]getY() < points[minIndex]getY()) {

　　minIndex = i;

　　} else if ((points[i]getY() == points[minIndex]getY())

　　&& (points[i]getX() < points[minIndex]getX())) {

　　minIndex = i;

　　}

　　}

　　return minIndex;

　　}

　　}

　　源碼四Testjava（主函數）

　　package nvex;

　　public class Test {

　　public static void main(String[] args) {

　　long start = SystemcurrentTimeMillis();

　　JarvisMarch j = new JarvisMarch();

　　Point[] points = jgetPs();

　　int firstIndex = jgetFirstIndex();

　　//        for (int i = ; i < pointslength; i++) {

　　//            Systemoutprint(i + :( + points[i]getX() + + points[i]getY() + )  );

　　//            if((i+) % == ) {

　　//                Systemoutprintln();

　　//            }

　　//        }

　　//        Systemoutprintln();

　　//        Systemoutprintln(*****************************************************************);

　　Systemoutprintln(the first point is: + firstIndex + :( +

　　points[firstIndex]getX() + + points[firstIndex]getY() + ));

　　Systemoutprintln(*****************************************************************);

　　jcalculateHull();

　　Systemoutprintln(The total running time is + (SystemcurrentTimeMillis() start) + millis);

　　}

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26948.html