如何找到多个点之间指定点的最短距离?

Question

我已经输入了点并找到了它们之间的距离。现在我想找出m点的哪个距离最短。

import java.awt.Point;
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

public class Solution 
{
public static void main(String[] args) 
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int k = in.nextInt();
Point[] coordinates=new Point[10];
double dist;
for(int i = 0; i < m; i++)
{
coordinates[i]=new Point(in.nextInt(),in.nextInt());
}
for(int i=0;i<m-1;i++)
{       
dist=Math.sqrt(((coordinates[i+1].getX()-coordinates[i].getX())*(coordinates[i+1].getX()-coordinates[i].getX()))+((coordinates[i+1].getY()-coordinates[i].getY())*(coordinates[1].getY()-coordinates[0].getY())));
System.out.println("dist between "+coordinates[i+1].getX()+","+coordinates[i+1].getY()+"and "+coordinates[i].getX()+","+coordinates[i].getY() +" is "+dist);
}
in.close();
}
}

Answer 1

你的 for 循环的设计方式是，它只检查一个点和它后面读取的点。您需要 2 个 for 循环来将每个点与所有其他点进行比较

for(int i = 0; i < m - 1; i++)
{
for (int j = 0; j < m; j++)
{
// compare point i with point j and store the smallest here
// you probably want to discard points where i == j
}
}

Answer 2

您必须在另一个 for 循环中创建一个 for 循环才能遍历每个点的所有点。第一个 for 循环将遍历每个点。第二个循环也将通过所有点，因此在第二个循环中，您将拥有两个循环的任何可能组合。然后，您需要计算距离并检查计算的距离是否小于之前计算的最小距离。

最后，您将拥有最小的距离：

• 0.0f 表示点 [] 大小为 0 或 1
• 大小为 2 或更大的点 [] 的最小距离

下面是一些示例代码：

float smallesDistance = 0.0f;
Point[] points = ...;
for(int i = 0; i < points.length; i++) {
for (int j = 0; j < points.length; j++) {
if(i != j) { //cant compare on point with itself
Point a = points[i];
Point b = points[j];
float distance = ...; //calculate distance with pythagorean theorem
if(distance < smallesDistance)
smallesDistance = distance;
}
}
}

如果您需要最远的距离，只需将if(distance < smallesDistance)替换为if(distance > smallesDistance).

Answer 3

以下是帮助程序函数：

1. distance：计算两点之间的距离
2. shortest_pair：返回距离最短的对

代码如下：

import java.awt.Point;
double distance(Point p1, Point p2)
{
return Math.sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
int[] shortest_pair(Point[] coordinates)
{
int m = coordinates.length;
double shortest_distance = Double.MAX_VALUE;
int[] shortest_pair = new int[2];
for (int i = 0; i < m-1; i++)
{
for (int j = i+1; j < m; j++)
{
double d = distance(coordinates[i], coordinates[j]);
if (d < shortest_distance)
{
shortest_distance = d;
shortest_pair[0] = i;
shortest_pair[1] = j;
}
}
}
return shortest_pair;
}

示例如下：

Random rand = new Random();
rand.setSeed(0);
int m = coordinates.length;
assert m == 10;
for(int i = 0; i < m; i++)
coordinates[i] = new Point(rand.nextInt(10), rand.nextInt(10));
assert Arrays.equals(shortest_pair(coordinates), new int[] { 2, 7 });