在Java中按距离排序

本文介绍了在Java中按距离排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

你好， 我在Java中有N个播放器.每个玩家都有(X，Y)坐标的位置. 我得到了一个新的球员，以及他的位置. 我必须在数组中找到与输入播放器最接近的K个播放器. 如何用Java做到呢? 我考虑过通过players数组，并与当前的K个最接近的玩家保持K大小的数组，并在通过players数组时对其进行更新. 但是为此，我必须有一个到输入播放器的距离"比较器. 问题是比较器在2个对象之间进行比较，但是现在我需要比较2个播放器中的哪个最接近输入播放器. 1)如何在Java中做到这一点? 2)还有更好的选择来找到K个最接近的球员吗? 谢谢

Hello, I have an array of N players in Java. Each player has a position by (X,Y) coordinates. I get as input a new player, with his position. I have to find the K closest players in the array to the input player. How can I do it in Java? I thought about going thru the players array, and keep a K-size array with the current K closest players, and update it as I go thru the players array. But for this, I must have a "distance to input player" comparator. The problem is that the comparator compares between 2 objects, but now I need to compare which of the 2 players is closest to the input player. 1) How can I do it in Java? 2) Is there a better option to find the K closest players? Thanks

推荐答案

使用距离函数D = sqrt((x1-x2)^ 2 +(y1-y2)^ 2)并将壁橱保持在阵列上的K个元素. 根据您的最终问题是，您可以与所有对象进行比较和排序，然后抢先K，或者一口气把新的K放入排序列表中.由您决定. 希望对您有所帮助. Use a distance function D=sqrt((x1-x2)^2+(y1-y2)^2) and keep the closets ones on the array of K elements. Depending on what your final problem is you could either compare with all and sort, then grab first K, or do it in one pass while putting new ones in a sorted list. up to you. hope it helps.

如果您有一个看起来像这样的Player类； If you have a Player class that looks something like this; package mypany; public class Player { private final double x; private final double y; public Player(final double x, final double y) { this.x = x; this.y = y; } public double getX() { return x; } public double getY() { return y; } public double getDistance(final Player other) { final double dx = getX() - other.getX(); final double dy = getY() - other.getY(); return Math.sqrt(dx*dx + dy*dy); } }

还有一个地图类，它在持有玩家和与实现Comparable<Player>; 的另一个(隐式)玩家之间的距离之间

And a map class between holding a player and a distance to another (implicit) player that implements Comparable<Player>;

package mypany; public class PlayerDistance implements Comparable<playerdistance> { private final Player player; private final double distance; public PlayerDistance(final Player player, final double distance) { this.player = player; this.distance = distance; } public Player getPlayer() { return player; } public double getDistance() { return distance; } @Override public int compareTo(PlayerDistance other) { return distance < other.distance ? -1 : 1; } }

可以这样检索 K 最接近的Player的列表；

The the list of K closest Players can be retrieved like this;

package mypany; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Program { public static Iterable<playerdistance> getClosest( final Player source, final Iterable<player> others, int maxToGrab) { final List<playerdistance> distances = new ArrayList<playerdistance>(); for(final Player player : others) { distances.add(new PlayerDistance(player, source.getDistance(player))); } Collections.sort(distances); return distances.subList(0, Math.min(maxToGrab, distances.size())); } public static void main(String[] args) throws Exception { final List<player> players = new ArrayList<player>(); players.add(new Player(1.0, 1.0)); players.add(new Player(2.0, 2.0)); players.add(new Player(3.0, 3.0)); final Player me = new Player(0.0, 0.0); for(final PlayerDistance playerDistance : getClosest(me, players, 2)) { System.out.println(playerDistance.getPlayer() + " at " + playerDistance.getDistance()); } } }

已添加: 上面的解决方案给出了距离以及最接近的Player，但是如果您说不创建另一个类更重要，那么可以通过让Player实现Comparator(不是). 像这样；

Added: The above solution gives the distances as well as the closest Players, but if as you say it''s more important not to create another class then that can be achieved by letting Player implement Comparator (not Comparable). Like, this;

package mypany; import java.util.Comparator; public class Player implements Comparator<Player> { private final String name; private final double x; private final double y; public Player(final String name, final double x, final double y) { this.name = name; this.x = x; this.y = y; } public double getX() { return x; } public double getY() { return y; } @Override public String toString() { return name; } public double getDistance(final Player other) { final double dx = getX() - other.getX(); final double dy = getY() - other.getY(); return Math.sqrt(dx*dx + dy*dy); } @Override public int compare(Player o1, Player o2) { final double distanceDelta = getDistance(o1) - getDistance(o2); return distanceDelta < 0 ? -1 : 1; } }

然后，找到最接近 K 的方法就变得简单了；

Then, the method of finding the K closest simply becomes;

package mypany; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Program { public static Iterable<Player> getClosest(final Player source, final List<Player> others, int maxToGrab) { Collections.sort(others, source); return others.subList(0, Math.min(maxToGrab, others.size())); } public static void main(String[] args) throws Exception { final List<Player> players = new ArrayList<Player>(); players.add(new Player("A", 1.0, 1.0)); players.add(new Player("B", 2.0, 2.0)); players.add(new Player("C", 3.0, 3.0)); players.add(new Player("D", 1.0, 0.5)); final Player me = new Player("S", 0.0, 0.0); for(final Player player : getClosest(me, players, 2)) { System.out.println(player); } } }

希望这会有所帮助， 弗雷德里克(Fredrik)

Hope this helps, Fredrik

01234567890 00 01 a 02 03 04 x b 05 06 c 玩家a 玩家b 直角x 从a到x = 3 b至x = 4 从a到b = 5 (3,4,5三角形) a * a = 9 b * b = 16 从a到b的距离= Math.sqrt((a * a)+(b * b)) c到b的距离= b至x = 3 c至x = 2 (3 * 3)+(2 * 2)= 13 Math.sqrt(13)= 3.605551275463989 x必须与其他两个点都成直角(90度) 01234567890 00 01 a 02 03 04 x b 05 06 c Player a Player b right angle x a to x = 3 b to x = 4 a to b = 5 (3,4,5 triangle) a*a = 9 b*b = 16 distance from a to b = Math.sqrt((a*a) + (b*b)) distance from c to b = b to x = 3 c to x = 2 (3*3)+(2*2)=13 Math.sqrt(13) = 3.605551275463989 x must be at right angles (90degrees) to both of other points