import java.util.*;
//You may assume that all Points are unique.
public class PointSet {
private ArrayList<Point> list;
private Comparator<Point> compareMethod;
//default constructor
public PointSet(){
list = new ArrayList<Point>();
}
//copy constructor for a point
public PointSet(PointSet l){
list = new ArrayList<Point>();
for(Point p: l.list){
this.add(p);
}
}
//randomly generating a Point to add to the PointSet based on the parameter ranges
public PointSet(int xMax, int yMax, int num){
list = new ArrayList<Point>();
Random r = new Random();
for(int i = 1; i <= num; i++){
int x = r.nextInt(xMax + 1);
int y = r.nextInt(yMax + 1);
this.add(new Point(x,y));
}
}
//number of elements in the list
public int numElements(){
return list.size();
}
//checks if list has no Points
public boolean isEmpty(){
return (list.size() == 0);
}
//checks if list contains specific point
public boolean contains(Point p){
return list.contains(p);
}
//returns a Point at a given index
public Point get(int index){
if(index < 0 || index > list.size()-1){
throw new IndexOutOfBoundsException("problem with index");
}
return list.get(index);
}
//adds a point to Pointset
public void add(Point p){
list.add(p);
}
//removes a point from PointSet
public void remove(Point p){
list.remove(p);
}
//string representation
public String toString(){
String temp="";
for(Point p: list){
temp+= p.toString();
temp+="\n";
}
return temp;
}
//adds all Points from a set in this PointSet
public PointSet merge(PointSet set){
PointSet ret = new PointSet(set);
for(Point p: list){
ret.add(p);
}
return ret;
}
//Creates pointset with the Points that this set and the parameter have in common
public PointSet intersection(PointSet set){
PointSet ret = new PointSet();
for(Point p : list){
if(set.contains(p))
ret.add(p);
}
return ret;
}
/*This will examine all the different combinations of point pairs within the calling object
* and determine which pairs of points have the smallest distance. This will build and return
* a PointPairSet of all PointPairs with the closest distance. This method will run in
* quadratic time. Assume that the PointPairSetís add method is constant time. */
public PointPairSet closestPointBF(){
PointPairSet smallestDistances = new PointPairSet();//set of smallest pairs to return
PointPair closestPair=new PointPair(new Point(0,0), new Point(Integer.MAX_VALUE,Integer.MAX_VALUE));
double minDist = Integer.MAX_VALUE;
for(int i =0; i < this.list.size(); i++){
for(int j =0; j<this.list.size(); j++){
PointPair compare = new PointPair(this.list.get(i),this.list.get(j));//two points to compare
//not comparing the point to itself, distance between the two points is smaller than distance with
//any other point so far
if(i != j && compare.distance() < minDist){
minDist = compare.distance();//that distance is now saved as smallest
closestPair = new PointPair(this.list.get(i), this.list.get(j));
}
}
minDist= Integer.MAX_VALUE;//RESET
smallestDistances.add(closestPair);//add small distance pair
}
return smallestDistances;
}
//returns a set of points with closest distance using ologn runtime
public PointPairSet closestPointsDC(){
qsort(0);//nlogn time
PointSet sortedX = new PointSet(this);
qsort(1);
PointSet sortedY = new PointSet(this);
return closestPoints(sortedX, sortedY, 0, this.list.size());
}
//
private PointPairSet closestPoints(PointSet xOrder, PointSet yOrder, int left, int right){
//System.out.print("XOrder:" + xOrder.toString());
//System.out.print("YOrder size is:" + yOrder.list.size() + yOrder.toString());
System.out.println("Right is: " + right + "Left is:" + left);
Point[] closestPair = new Point[2];
if(yOrder.list.size() <= 3){
System.out.print("USED BRUTE FORCE");
//then do brute force by comparing them
return closestPointBF();
}
//set is larger than 3, using divide and conquer
else{
System.out.println("IN ELSE!");
int imaginaryLine = yOrder.list.size()/2;//separating X logically
//PointPair closestSoFar;//closest pair found so far
double distanceBetweenClosest = Integer.MAX_VALUE;
//physically splitting up y
PointSet yLeft= new PointSet();
PointSet yRight = new PointSet();
for(int i =0; i <imaginaryLine; i ++ )
yLeft.add(yOrder.get(i));
for(int j = imaginaryLine; j < yOrder.list.size(); j++)
yRight.add(yOrder.get(j));
//make two recursive calls
PointPairSet leftRecursive = closestPoints(xOrder, yLeft, 0, imaginaryLine);//left side examined
PointPairSet rightRecursive = closestPoints(xOrder, yRight, imaginaryLine, right);//right side examined
double closestLeft = Integer.MAX_VALUE;
double closestRight = Integer.MAX_VALUE;
for(int k = 0; k <leftRecursive.numElements(); k++){
if(leftRecursive.get(k).distance() < closestLeft)
closestLeft = leftRecursive.get(k).distance();
}
for(int k = 0; k <rightRecursive.numElements(); k++){
if(rightRecursive.get(k).distance() < closestRight)
closestRight = rightRecursive.get(k).distance();
}
for(int i =0; i < yOrder.list.size(); i++){
//if outside range delete
if(yOrder.list.get(i).getX()<left || yOrder.list.get(i).getX() > right){
//discard all points from ylist that are not in the strip
System.out.print("Removed from y:" + yOrder.list.get(i));
yOrder.remove(yOrder.list.get(i));
}
}
//These points are now examined in linear time to determine the closest pair
return closestPointBF();
}
}
// type == 0 implies X
public void qsort(int type){
if(type == 0)
compareMethod = new XComparator();
else
compareMethod = new YComparator();
quickSort(0,list.size()-1);
}
// sorts list of Points
private void quickSort(int from, int to){
if(from >= to)
return;
int pivot = (from + to)/ 2;
int i = from;
int j = to;
while(i <= j){
if(compareMethod.compare(list.get(i), list.get(pivot)) < 1)
i++;
else if( compareMethod.compare(list.get(j),list.get(pivot)) > -1)
j--;
else{
Point temp = list.set(i, list.get(j));
list.set(j, temp);
i++;
j--;
}
}
if( pivot < j){
Point temp = list.set(j, list.get(pivot));
list.set(pivot, temp);
pivot = j;
}
else if(pivot > i){
Point temp = list.set(i, list.get(pivot));
list.set(pivot, temp);
pivot = i;
}
quickSort(from, pivot-1);
quickSort(pivot+1,to);
}
public static void main(String[] args){
PointSet set = new PointSet();
set.add(new Point(2, 1));
set.add(new Point(3, 2));
set.add(new Point(4, 3));
set.add(new Point(5, 4));
set.add(new Point(6, 5));
/*set.add(new Point(5, 5));
set.add(new Point(3, 3));
set.add(new Point(3, 2));
set.add(new Point(4, 1));*/
//PointPairSet t = new PointPairSet();
//t.add(new PointPair(new Point(1, 1), new Point(3, 55)));
set.closestPointBF();
PointPairSet returned = set.closestPointsDC();
System.out.print(returned.toString());
// PointSet tester = set.closestPointBF();
//System.out.println(set);
//set.qsort(1);
//System.out.println(set);
}
}
sariberri 1 Light Poster
sariberri 1 Light Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.