CODEWITHSUNDEEP
javaalgorithmspatial
Jeevi
Jeevi

Reputation: 3042

Find coordinate at minimum distance from list of coordinates

I have a list of coordinates in 2D space (xi, yi). How can I find a coordinate (X, Y) such that the distance between it and the other given coordinates is minimum? Is there a mathematical formula to solve for (X, Y)?

Let me give an example.. Lets say i have list of co.ordinates (0,0);(1,0);(0,1);(-1,0);(0,-1); Now i have to findout possible co.ordinate(s)(one or many) such that the resulting co.ordinate is at minimun distance from all the points. in this case (0,0).

As Voo said,This is my requirement : Find a point that minimizes the sum of the distances to the points in a given set

Upvotes: 4

Views: 6686

Answers (4)

deuce
deuce

Reputation: 11

Requirement: Find a point that minimizes the sum of the distances to the points in a given set.

The point with the minimum euclidean distance sum to all other points, has:

x = mean average of all X in the set
y = mean average of all Y in the set

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272507

Assuming you're asking for the closest candidate to a given point

You are asking about nearest neighbour searches.

The simplest approach is simply too loop over every candidate coordinate, compute the Euclidean distance (assuming you want a Euclidean metric), and track the minimum. Is that sufficient?

More complex (but potentially faster) approaches involve storing your candidate points in e.g. a space-partitioning tree, e.g. a quad-tree, or a kd-tree, or one of several other variants.

Upvotes: 2

Anila
Anila

Reputation: 1136

You can calculate distance between two points using euclidien distance formula: squareroot((x1-X)²+(yi-Y)²) or you can use manhattan formula: |yi-Y|+|xi-X|.

Is this a pathfinding problem?

Upvotes: 0

giorashc
giorashc

Reputation: 13713

public Coord2D minDistance(List<Coord2D> coordinates, Coord2D someCoord) {
   float minDistance = Float.MAX_VALUE;
   Coord2D result;
   for (Coord2D coord : coordinates) {
       float distance = Math.sqrt(Math.pow((coord.x - someCoord.x), 2) + (Math.pow((coord.y - someCoord.y), 2))
       if (distance < result) { 
           result = coord;
           minDistance = distance;
       }
   }

   return result;
}

Upvotes: 1

Related Questions