# Untitled

unknown
java
2 years ago
3.4 kB
5
Indexable
Never
```        public static Pair bruteDistance(Point[] arrayPoints){
double minDist = Double.MAX_VALUE;
Pair closest = null;
for (int i = 0; i < 3; i++){
for (int k = i+1; k<3; k++){
if(distance(arrayPoints[i], arrayPoints[k]) < minDist){
minDist = distance(arrayPoints[i], arrayPoints[k]);
closest = new Pair(arrayPoints[i], arrayPoints[k]);
}
}

}
return closest;
}

public static Pair distance(Point[] xOrd, int low, int high, Point[] yOrd) {
//base cases: We can have 1 Point to look at, 2 Points, or 3 Points
if (high - low <= 3){
return bruteDistance(xOrd);
}

else{
Pair closestPair = null;
double dist;
int mid = (low+high) / 2;
// Point[] distLeft = Arrays.copyOfRange(xOrd, low, mid+1);
// Point[] distRight = Arrays.copyOfRange(xOrd, mid + 1, high);
Pair distLeft = distance(xOrd, low, mid, yOrd);
Pair distRight = distance(xOrd, mid+1, high, yOrd);

//idk why distLeft is null but it is an error I am getting so lets address it
//same with dist right
if (distLeft == null && distRight == null) {
dist = 0;
closestPair = null;
}

else if (distRight == null && distLeft != null) {
dist = distLeft.getDistance();
closestPair = distLeft;
}

else if (distLeft == null && distRight != null) {

dist = distRight.getDistance();
closestPair = distRight;
}
else{
dist = Math.min(distLeft.getDistance(), distRight.getDistance());
if (distLeft.getDistance() == dist) {
closestPair = distLeft;

}
else{
closestPair = distRight;
}
}

ArrayList<Point> stripL = new ArrayList<Point>();
ArrayList<Point> stripR = new ArrayList<Point>();

for (Point p: yOrd){
if (p.xCord <= xOrd[mid].xCord && xOrd[mid].xCord-p.xCord <= dist){
}
else if(p.xCord > xOrd[mid].xCord && xOrd[mid].xCord - p.xCord <= dist){
}
}

int r = 0;
for (Point p: stripL){
while (r< stripR.size() && stripR.get(r).yCord <= p.yCord - dist){
r++;
}
int r1 = r;
while (r1 < stripR.size() && Math.abs(stripR.get(r1).yCord - p.yCord)<= dist){
if (distance(stripR.get(r1), p)< dist){
dist = distance(stripR.get(r1),p);
closestPair = new Pair(stripR.get(r1),p);
}
r1++;
}
}
return closestPair;
}
}```