Untitled

mail@pastecode.io avatar
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){
                        stripL.add(p);
                    }
                    else if(p.xCord > xOrd[mid].xCord && xOrd[mid].xCord - p.xCord <= dist){
                        stripR.add(p);
                    }
                }

                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;
            }
        }