Finding points with the shortest distance

Question

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

Answer 1

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

It's easy to read, but three improvements can be made:

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.

• micah: Thank you! This is basically what I was looking for, very interesting stuff.
• Max: I don't think 'shortestDistance' should be set to Double.MAX_VALUE. The name suggests a short distance, not the maximum double value.
• Quentin Pradet: @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?
• N00b Pr0grammer: Can you please fix the broken link, the rotating calipers please?

Answer 2

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.

• micah: I purposefully neglected to mention that this lab required 2D arrays because I hoped there was a class like this. Thanks. :)
• Leonid: 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
• Donald.McLean: 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.
• N00b Pr0grammer: @Leonid, Can you please fix the broken link?
• Leonid: @N00bPr0grammer Dziuba has deleted his blog.

Answer 3

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.

• micah: 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.
• Winston Ewert: @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.