CODEWITHSUNDEEP
javaalgorithmfor-loopclosest-points
vallerie
vallerie

Reputation: 1

Finding the Closest Pair of Points Using basic functions

I'm tryin' to find the closest pair of points, but my code just won't work. I'm not expert in this field, please help me out. This is for my project T_T

my code goes like this:

import java.util.Scanner;
public class FindingClosestPair {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter the number of points: ");
        int nPoints = input.nextInt();

        System.out.print("Enter "+nPoints+" points: ");
        float [][] points = new float [nPoints][2];
        for(int r=0; r<points.length; r++){
            for(int c=0; c<points[0].length; c++){
                points[r][c] = input.nextFloat(); 
            }
        }

        for(int r=0; r<points.length; r++){
            for(float e : points[r]){
                System.out.print(e+" ");
            }
            System.out.println();
        }

        float p1=0, p2=0, shortestDistance=0, d1=0, d2=0, d=0;
        float x1=0, x2 = 0, x3=0, y1=0, y2 = 0, y3=0;
        float a1=0, a2=0, b1=0, b2=0;

        for(int r1=0; r1<points.length-2; r1++){
            x1 = points[r1][0];
            y1 = points[r1][1];
            for(int r2=r1+1; r2<points.length-1; r2++){
                x2 = points[r2][0];
                y2 = points[r2][1];
                d1 = (float) Math.sqrt((Math.pow(x2-x1, 2))+(Math.pow(y2-y1, 2)));
                for(int r3=r2+1; r3<points.length; r3++){
                    x3 = points[r3][0];
                    y3 = points[r3][1];
                    d2 = (float) Math.sqrt((Math.pow(x3-x1, 2))+(Math.pow(y3-y1, 2)));
                    if(d1<d2){
                        d=d1;
                        a1=x1; b1=y1;
                        a2=x2; b2=y2;
                    }else if(d2<d1){
                        d=d2;
                        a1=x1; b1=y1;
                        a2=x3; b2=y3;
                    }
                }
            }
        }

        System.out.println("The closest two points are ("+a1+","+b1+") and ("+a2+","+b2+")");
    }
}

So there. I'm pretty bad, right? T_T

Upvotes: 0

Views: 471

Answers (1)

Bart
Bart

Reputation: 547

Wouldn't it work with one loop less? pseudo code written in browser:

int clostestPointA = 0;
int clostestPointB = 1;
float closestDist = float.MAX_VALUE;

for(int pointA=0; pointA<points.length-1; pointA++){
    xA = points[pointA][0];
    yA = points[pointA][1];
    for(int pointB=pointA+1; pointB<points.length; pointB++){
        xB = points[pointB][0];
        yB = points[pointB][1];
        d1 = Math.pow(xA-xB, 2) + Math.pow(yA-yB, 2); //dist squared, squareroots are slow and not needed for the comparison
        if(d1 < closestDist){
            //set clostestPointA and clostestPointB
            closestPointA = pointA;
            closestPointB = pointB;
            closestDist = d1;
        }
    }
}

Upvotes: 1

Related Questions