find closest point from users coordinates

Question

I would like to know how to use find the closes point using coordinates. i am using a Hashmap which holds coordinates and strings. i have allowed the user to input an x and y axis and store them as int a and int b but i don't know where to go from there. thanks for looking

import java.util.HashMap;
import java.util.Scanner;

public class Coordinate {

static class Coords {
    int x;
    int y;

    public boolean equals(Object o) {
        Coords c = (Coords) o;
        return c.x == x && c.y == y;
    }

    public Coords(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    public int hashCode() {
        return new Integer(x + "0" + y);
    }

    public String toString()
    {
        return x + ";" + y;
    }


}

public static void main(String args[]) {

    HashMap<Coords, String> map = new HashMap<Coords, String>();

    map.put(new Coords(250, 140), "Clifton street");
    map.put(new Coords(195, 115), "twoli");
    map.put(new Coords(165, 95), "Jacobs well");
    map.put(new Coords(140, 90), "moxbridge");
    map.put(new Coords(55, 95), "parkway");
    map.put(new Coords(15, 120), "easton");
    map.put(new Coords(260, 25), "Weston on shore");
    map.put(new Coords(250, 60), "newbridge");
    map.put(new Coords(185, 85), "central");
    map.put(new Coords(140, 100), "stdennis");
    map.put(new Coords(85, 140), "trim bridge");
    map.put(new Coords(170, 35), "windmill hill");
    map.put(new Coords(150, 60), "shakespeare court");
    map.put(new Coords(95, 50), "temple fields");
    map.put(new Coords(55, 125), "pirac cresent");
    map.put(new Coords(150, 155), "st judes hill");

    Scanner input = new Scanner(System.in);
    int i;
    int a;
    int b;

    System.out.println(map.size());
    System.out.println(map.toString());
    Coords c = new Coords(65,72);
    System.out.println(c + " - " + map.get(c));

    System.out.println("choose from the following");
    System.out.println("find closest station = 1");
    System.out.println("plan train route = 2");
    i = input.nextInt();

    if (i==1){
        System.out.println("enter your x axis ");
        a = input.nextInt();
        System.out.println("enter your y axis");
        b = input.nextInt();

        System.out.println("the nearest station is");
    }
    else if (i==2){
        System.out.println("route planner");
    }
    else {
        System.out.println("entered incorrect number");

    }
}
}

Solution

First, I advise you take KevinMangold's advice, seeing as Java provides a perfectly suitable Point class for you to use.

---

This is a minimization problem. Essentially, you want to compute the distance between the entered point and every known station using some metric (perhaps Euclidean distance?). Then, you pick the station corresponding to the minimum distance found.

Here's some example code using Collections.min:

final Map<Point, String> names = ...;
final Set<Point> stations = names.keySet();
final Point source = ...;
final Point nearest = Collections.min(stations, new Comparator<Point>() {

  public int compare(final Point p1, final Point p2) {
    return (int) p1.distanceSq(p2);
  }
});
final String name = names.get(nearest);

Comments

[Agostino]

Using this method the same distances will be recalculated many times. If you need to maximize the speed, you may want to adopt an alternative solution.

[obataku]

@Agostino the distances could just be cached with a few more lines of code