# Finding points with the shortest distance

This takes in a user specified number of points then finds the two points with the shortest distance.

import java.util.Scanner;
import java.lang.Math;

public class FindNearestPoints
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);

System.out.print("Enter the number of points: ");
final int numOfPoints = scan.nextInt();

double[][] points = new double[numOfPoints][2];
double shortestDistance=0;
double distance=0;
String closestPoint1="";
String closestPoint2="";

//enter x,y coords into the ix2 table points[][]
for (int i=0; i<numOfPoints; i++)
{
System.out.print("Enter point x" + i + ": ");
points[i][0] = scan.nextDouble();
System.out.print("Enter point y" + i + ": ");
points[i][1] = scan.nextDouble();
}

//get the distance between the point in the ith row and the (m+1)th row
//and check if it's shorter than the distance between 0th and 1st
for (int i=0; i<numOfPoints; i++)
{
//use m=i rather than 0 to avoid duplicate computations
for (int m=i; m<numOfPoints-1;m++)
{
double dx = points[i][0] - points[m+1][0];
double dy = points[i][1] - points[m+1][1];
distance = Math.sqrt(dx*dx + dy*dy);

//set shortestDistance and closestPoints to the first iteration
if (m == 0 && i == 0)
{
shortestDistance = distance;
closestPoint1 = "(" + points[0][0] + "," + points[0][1] + ")";
closestPoint2 = "(" + points[1][0] + "," + points[1][1] + ")";
}
//then check if any further iterations have shorter distances
else if (distance < shortestDistance)
{
shortestDistance = distance;
closestPoint1 = "(" + points[i][0] + "," + points[i][1] + ")";
closestPoint2 = "(" + points[m+1][0] + "," + points[m+1][1] + ")";
}
}
}
System.out.println("The shortest distance is: " + shortestDistance);
System.out.println("The closest points are " + closestPoint1 + " and " + closestPoint2);
}
}


## Algorithm

This is a classical problem in computational geometry and there are a lot of efficient approaches if you're interested. The longest distance problem (aka. diameter of a polygon) is more interesting though, and will introduce you to a really useful tool in computational geometry: the rotating calipers.

## Code

1. for (int m=i; m<numOfPoints-1;m++) is indeed an interesting optimization (x2 improvement). It would be more readable to make m go from i+1 to numOfPoints.
2. You can avoid computing Math.sqrt(dx*dx + dy*dy);. dx*dx + dy*dy is enough to compare the distances. When printing the distance, you can use Math.sqrt.
3. First set shortestDistance to Double.MAX_VALUE, this will avoid you the if (m == 0 && i == 0) case and the resulting duplication: you'll always find a distance shorter than infinity.
• Thank you! This is basically what I was looking for, very interesting stuff. – micah Mar 12 '12 at 21:33
• I don't think 'shortestDistance' should be set to Double.MAX_VALUE. The name suggests a short distance, not the maximum double value. – Max Nov 22 '13 at 11:57
• @user1021726 Which is why setting it first to the maximum double value is a safe way to make sure the next distance will be shorter. Think of it as infinity. Did I miss something? – Quentin Pradet Nov 22 '13 at 15:08
• Can you please fix the broken link, the rotating calipers please? – N00b Pr0grammer Dec 19 '16 at 5:03

For starters, this code should use a Point class, consisting of an x and y location. Your variable points would then be Point[] rather than a two dimensional array. The Point class should have a method for reading values, printing values and calculating the distance between two points.

Then, using the Point class, your code would be dramatically simpler and easier to read. It might even be easier to write from scratch rather than try and fix what you have.

• I purposefully neglected to mention that this lab required 2D arrays because I hoped there was a class like this. Thanks. :) – micah Mar 12 '12 at 21:30
• in the real world Point[] is apparently much less memory-efficient than a 2d array of Java primitives. teddziuba.com/2008/02/the-road-to-hell-is-64-bits-wi.html – Leonid Mar 12 '12 at 22:22
• Memory efficiency is very rarely an issue in the real world. The cost of the programmer's time is far more expensive than the cost in CPU cycles 98% of the time. Trying to optimize an algorithm without justifiable need is called "premature optimization" and is far more likely than not to be a mistake. – Donald.McLean Mar 13 '12 at 1:16
• @Leonid, Can you please fix the broken link? – N00b Pr0grammer Dec 19 '16 at 5:06
• @N00bPr0grammer Dziuba has deleted his blog. – Leonid Dec 20 '16 at 0:19
import java.util.Scanner;
import java.lang.Math;

public class FindNearestPoints
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);

System.out.print("Enter the number of points: ");
final int numOfPoints = scan.nextInt();

double[][] points = new double[numOfPoints][2];
double shortestDistance=0;
double distance=0;
String closestPoint1="";
String closestPoint2="";


Declare your variables close to where you use them, not all at the beginning.

        //enter x,y coords into the ix2 table points[][]
for (int i=0; i<numOfPoints; i++)
{
System.out.print("Enter point x" + i + ": ");
points[i][0] = scan.nextDouble();
System.out.print("Enter point y" + i + ": ");
points[i][1] = scan.nextDouble();
}

//get the distance between the point in the ith row and the (m+1)th row
//and check if it's shorter than the distance between 0th and 1st
for (int i=0; i<numOfPoints; i++)
{
//use m=i rather than 0 to avoid duplicate computations
for (int m=i; m<numOfPoints-1;m++)
{


Use for(m = i + 1; m < numOfPoints; m++) That way you don't have to m + 1 everywhere

                double dx = points[i][0] - points[m+1][0];
double dy = points[i][1] - points[m+1][1];
distance = Math.sqrt(dx*dx + dy*dy);

//set shortestDistance and closestPoints to the first iteration


I don't understand this comment.

                if (m == 0 && i == 0)
{
shortestDistance = distance;
closestPoint1 = "(" + points[0][0] + "," + points[0][1] + ")";
closestPoint2 = "(" + points[1][0] + "," + points[1][1] + ")";


I suggest storing the numbers associated with the closest points, not a string.

                }
//then check if any further iterations have shorter distances
else if (distance < shortestDistance)


You are doing the same thing you did above. Use || to combine the two conditions

                {
shortestDistance = distance;
closestPoint1 = "(" + points[i][0] + "," + points[i][1] + ")";
closestPoint2 = "(" + points[m+1][0] + "," + points[m+1][1] + ")";
}
}
}
System.out.println("The shortest distance is: " + shortestDistance);
System.out.println("The closest points are " + closestPoint1 + " and " + closestPoint2);
}
}


The whole thing would do better to split across several functions instead of all in one.

• I've read before that variables should be declared as you say, but I've noticed that my professor has all of the variables declared at the top when she gives sample code. I'm not sure why. – micah Mar 12 '12 at 21:38
• @micah, some older languages required declaring all your variables at the top and some programmers have never stopped doing it. I usually take it as a sign that somebody doesn't care enough about code readability. – Winston Ewert Mar 12 '12 at 21:51