Find the Closest distance between a pair of point among given n points in Java
In this Java tutorial, we are going to learn how to find the smallest distance between a pair of points in presence of many other points.
Problem statement: Find the closest distance between points in Java
Given points on any plane, you have to find the closest/smallest distance between a pair or between two different points.
Note: The logic for this problem is, first I’m plotting these points and then draw a line between the plane.
Step by Step Approach for this Problem:
- Sort the given points by their x-coordinates and then split the resulting sorted list into two halves S1 and S2 of size (n/2).
- By making a recursive call for each of the sets S1 and S2, we have to find the smallest distances d1 and d2 in them. Let = min{d1, d2}.
- We need to find the closest distance between points from the sets, one point from S1 and one from S2.
- And check, it is smaller than d or not.
- To perform that type of check, we have to remove the initial point set and keep only those points whose x-distance to the middle line does not exceed to the d.
- Now, we have to sort the set of points in the resulting strip by their y-coordinates and scan the resulting list of points.
- Now, we have to compute for each point that its distance to the seven subsequent points in this list and compute d’, the minimum distance that we encountered during this scan.
- Finally, we return min{d, d’}.
StringTokenizer class is used here.
You can also learn:
- How to implement an algorithm for the Fractional Knapsack Problem
- How to find Maximum Pairwise Product in Java using Naive approach
Here I’m providing the Java code to get the closest distance between the pair of points:
import java.io.*; import java.util.*; import static java.lang.Math.*; public class Closest { static class Point implements Comparable<Point> { long x, y; public Point(long x, long y) { this.x = x; this.y = y; } @Override public int compareTo(Point o) { return o.y == y ? Long.signum(x - o.x) : Long.signum(y - o.y); } } static double minimalDistance(int[] x, int y[]) { double ans = Double.POSITIVE_INFINITY; // write your code here return ans; } public static void main(String[] args) throws Exception { reader = new BufferedReader(new InputStreamReader(System.in)); writer = new PrintWriter(System.out); int input = nextInt(); int[] x = new int[input]; int[] y = new int[input]; for (int p = 0; p < input; p++) { x[p] = nextInt(); // user input y[p] = nextInt(); // user input } System.out.println(minimalDistance(x, y)); //print minimal distance writer.close(); } static BufferedReader reader; static PrintWriter writer; static StringTokenizer tok = new StringTokenizer(""); static String next() { while (!tok.hasMoreTokens()) { String w = null; try { w = reader.readLine(); } catch (Exception e) { e.printStackTrace(); } if (w == null) return null; tok = new StringTokenizer(w); } return tok.nextToken(); } static int nextInt() { return Integer.parseInt(next()); } }
Input
4 7 7 1 100 4 8 7 9
Output
2.00
How is it you can read my mind? I am brushing up my programming after a few years away. I have just finished building my robot and to control it i thought a room mapping algorithm will kick be into gear. Java the perfect language to use and here you have a basic program ready to use and modify, fantastic. You should think about a career in Government or Show business.
Many Thanks
Dr J