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
According to Wikipedia:
The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows[1]:
1. Sort points along the x-coordinate (I did this)
2. Split the set of points into two equal-sized subsets by a vertical line x = xmid (I did this)
3. Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.
5. Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
6. The final answer is the minimum among dLmin, dRmin, and dLRmin.
I'm stuck on step 3. I don't get how I'm supposed to get the left-side and right-side minimal distances and then compare them without wasting a lot of runtime....:/
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.