JAVA language convex hull algorithm to achieve

Source 1: JarvisMarch.java package mtn.uis.xaltin.convex; import static java.lang.Math.abs; import java.util.Iterator; import java.util.LinkedList; imp ...
Source 1: JarvisMarch.java

package mtn.uis.xaltin.convex;

import static java.lang.Math.abs;

import java.util.Iterator;



import java.util.LinkedList;

import java.util.List;

public class JarvisMarch (

private int count;

public int getCount () (

return count;

)

public void setCount (int count) (

this.count = count;

)

private static int MAX_ANGLE = 4;

private double currentMinAngle = 0;

private List hullPointList;

private List indexList;

private PointFactory pf;

private Point [] ps;

public Point [] getPs () (

return ps;

)

private int firstIndex;

public int getFirstIndex () (

return firstIndex;

)

public JarvisMarch () (

this (10);

)

public JarvisMarch (int count) (

pf = PointFactory.getInstance (count);

initialize ();

)

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

pf = PointFactory.getInstance (x, y);

initialize ();

)

private void initialize () (

hullPointList = new LinkedList ();

indexList = new LinkedList ();

firstIndex = pf.getFirstIndex ();

ps = pf.getPoints ();

addToHull (firstIndex);

)

private void addToHull (int index) (

indexList.add (index);

hullPointList.add (ps [index]);

)

public int calculateHull () (

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

addToHull (i);

)

showHullPoints ();

return 0;

)

private void showHullPoints () (

Iterator itPoint = hullPointList.iterator ();

Iterator itIndex = indexList.iterator ();

Point p;

int i;

int index = 0;

System.out.println ("The hull points is: ->");

while (itPoint.hasNext ()) (

i = itIndex.next ();

p = itPoint.next ();

System.out.print (i + ": (" + p.getX () + "," + p.getY () + ")");

index + +;

if (index% 10 == 0)

System.out.println ();

)

System.out.println ();

System.out.println ("******************************************* *********************");

System.out.println ("The count of all hull points is" + index);

) Public int getNextIndex (int currentIndex) (
double minAngle = MAX_ANGLE;

double pseudoAngle;

int minIndex = 0;

for (int i = 0; i

if (i! = currentIndex) (

pseudoAngle = getPseudoAngle (ps [i]. getX () - ps [currentIndex]. getX (),

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

if (pseudoAngle> = currentMinAngle & & pseudoAngle

minAngle = pseudoAngle;

minIndex = i;

) Else if (pseudoAngle == minAngle) (

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

]. 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> 0 & & dy> = 0)
return dy / (dx + dy);
if (dx <= 0 & & dy> 0)
return 1 + (abs (dx) / (abs (dx) + dy));
if (dx <0 & & dy <= 0)
return 2 + (dy / (dx + dy));
if (dx> = 0 & & dy <0)
return 3 + (dx / (dx + abs (dy)));
throw new Error ("Impossible");
)
)
Source 2: Point.java
package mtn.uis.xaltin.convex;
public class Point (
/ / Define points x, y coordinates, the reason is the int type, is for the future can be visualized on the computer screen.
private int x;
private int y;
/ / X, y of the get method
public int getX () (
return x;
)
public int getY () (
return y;
)
/ / Define the distance between points to the edge of the screen
private static double PADDING = 20;
/ / Point range in the screen
private static double POINT_RANGE = (800 - PADDING * 2);
/ / Default constructor method to generate random points
public Point () (
this.x = (int) ((Math.random () * POINT_RANGE) + PADDING);
this.y = (int) ((Math.random () * POINT_RANGE) + PADDING);
)
/ / Constructor with parameters, you can manually enter the fixed-point implementation
public Point (int x, int y) (
this.x = x;
this.y = y;
)
/ / Override hashCode () and equals () method, to achieve more and Hash
@ Override
public int hashCode () (
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
)
@ Override
public boolean equals (Object obj) (
Point other = (Point) obj;
if ((x == other.x) & & (y == other.y))
return true;
return false;
)
)Source 3: PointFactory.java
package mtn.uis.xaltin.convex;
public class PointFactory (
/ **
* Singleton pattern, mass produced Point, you can manually create Point
* /
private Point [] points = null;
private int newIndex;
private int firstIndex = 0;
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 (10);
)
private PointFactory (int count) (
points = new Point [count];
for (int i = 0; i
points [i] = new Point ();
newIndex = i;
validatePoints ();
)
firstIndex = getFirstPoint ();
)
public PointFactory (int [] x, int [] y) (
points = new Point [y.length];
for (int i = 0; i
points [i] = new Point (x [i], y [i]);
)
firstIndex = getFirstPoint ();
)
private void validatePoints () (
for (int i = 0; i
if (points [i]. equals (points [newIndex])) (
points [newIndex] = new Point ();
validatePoints ();
)
)
)
public int getFirstPoint () (
int minIndex = 0;
for (int i = 1; i
if (points [i]. getY ()
minIndex = i;
) Else if ((points [i]. GetY () == points [minIndex]. GetY ())
& & (Points [i]. GetX ()
minIndex = i;
)
)
return minIndex;
)
)
Source 4: Test.java (main function)
package mtn.uis.xaltin.convex;
public class Test (
public static void main (String [] args) (
long start = System.currentTimeMillis ();
JarvisMarch j = new JarvisMarch (100000);
Point [] points = j.getPs ();
int firstIndex = j.getFirstIndex ();
/ / For (int i = 0; i
/ / System.out.print (i + ": (" + points [i]. GetX () + "," + points [i]. GetY () + ")");
/ / If ((i +1)% 10 == 0) (
/ / System.out.println ();
/ /)
/ /)
/ / System.out.println ();
/ / System.out.println ("***************************************** ************************");
System.out.println ("the first point is:" + firstIndex + ": (" +
points [firstIndex]. getX () + "," + points [firstIndex]. getY () + ")");
System.out.println ("******************************************* **********************");
j.calculateHull ();
System.out.println ("The total running time is" + (System.currentTimeMillis () - start) + "millis.");
)
)