﻿ JAVA凸包算法_電腦知識網

# JAVA凸包算法

2022-06-13   來源: Java核心技術

源碼一JarvisMarchjava

package nvex;

import static javalangMathabs;

import javautilIterator;

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() {

firstIndex = pfgetFirstIndex();

ps = pfgetPoints();

}

}

public int calculateHull() {

for (int i = getNextIndex(firstIndex); i != firstIndex; i = getNextIndex(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