熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

JAVA凸包算法

2013-11-23 19:29:16  來源: 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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.