javascript - Finding closest x,y coordinates - Stack Overflow

admin管理员组

文章数量:1418380

I have coordinates (x, y) of place where I am currently and array of objects with coordinates of destinations.

Coordinates x and y are just representing of fields in map like this:

and it is up to 100x100.

myPosition is array: [ 13, 11 ] where 13 is x and 11 is y (demonstratively marked it as red in above jpg).

destinations is array of object:

[ { x: 22, y: 13 },
{ x: 16, y: 25 },
{ x: 20, y: 11 },
{ x: 76, y: 49 },
{ x: 65, y: 47 },
{ x: 82, y: 33 },
{ x: 86, y: 35 },
{ x: 61, y: 59 },
{ x: 62, y: 52 },
{ x: 18, y: 52 },
{ x: 24, y: 49 },
{ x: 52, y: 55 },
{ x: 20, y: 57 },
{ x: 80, y: 11 },
{ x: 55, y: 61 },
{ x: 46, y: 59 },
{ x: 77, y: 19 },
{ x: 2, y: 22 },
{ x: 78, y: 23 },
{ x: 86, y: 51 },
{ x: 75, y: 46 },
{ x: 6, y: 8 },
{ x: 25, y: 12 },
{ x: 81, y: 21 },
{ x: 53, y: 58 } ]

I need some tips or algorithm which will sort destination array of object in order from closest to my position.

I have coordinates (x, y) of place where I am currently and array of objects with coordinates of destinations.

Coordinates x and y are just representing of fields in map like this:

and it is up to 100x100.

myPosition is array: [ 13, 11 ] where 13 is x and 11 is y (demonstratively marked it as red in above jpg).

destinations is array of object:

[ { x: 22, y: 13 },
{ x: 16, y: 25 },
{ x: 20, y: 11 },
{ x: 76, y: 49 },
{ x: 65, y: 47 },
{ x: 82, y: 33 },
{ x: 86, y: 35 },
{ x: 61, y: 59 },
{ x: 62, y: 52 },
{ x: 18, y: 52 },
{ x: 24, y: 49 },
{ x: 52, y: 55 },
{ x: 20, y: 57 },
{ x: 80, y: 11 },
{ x: 55, y: 61 },
{ x: 46, y: 59 },
{ x: 77, y: 19 },
{ x: 2, y: 22 },
{ x: 78, y: 23 },
{ x: 86, y: 51 },
{ x: 75, y: 46 },
{ x: 6, y: 8 },
{ x: 25, y: 12 },
{ x: 81, y: 21 },
{ x: 53, y: 58 } ]

I need some tips or algorithm which will sort destination array of object in order from closest to my position.

• javascript
• algorithm

Share Improve this question Follow edited Mar 10, 2019 at 1:42 BT101 asked Mar 10, 2019 at 1:25 BT101BT101 3,8561111 gold badges4848 silver badges101101 bronze badges

Add a ment  | 

1 Answer 1

Sorted by: Reset to default 5

What you got is called the nearest neighbor problem.

Two solutions, depening on where you need to take your problem:

1. You could simply do a brute force distance search with the usual optimization of skipping the square-root:

Some code:

function DistSquared(pt1, pt2) {
    var diffX = pt1.x - pt2.x;
    var diffY = pt1.y - pt2.y;
    return (diffX*diffX+diffY*diffY);
}

 closest = destinations[0];
 shortestDistance = DistSquared(myPosition, destinations[0]);
 for (i = 0; i < destinations.length; i++) {
     var d = DistSquared(myPosition, destinations[i]);
     if (d < shortestDistance) {
         closest = destinations[i];
         shortestDistance = d;
     }
 }

2. If you are going to make repeated nearest neighbor queries on the same destinations array, you can use an algorithm known as a k-d tree. This where you build a binary tree representation of your grid of points by partitioning it in half many times along a different axis.

本文标签： javascriptFinding closest xY coordinatesStack Overflow