Reduce Complexity. Find closest pair of latitudes and longitudes
I have two arrays representing two different GPS paths. Each array contains latitudes in the even indices(starting from 0) and longitudes in the odd indices as shown below :
48.855002219371706,2.3472976684570312,48.855050000000006,2.34735,48.85508,2.3473200000000003,48.85584,2.3477300000000003,48.8562,2.3465000000000003,...
I would like to calculate the sum of the distances between the closest points of these two paths. I calculate the distance between pairs of latitudes and longitudes using the Haversine method.
This is what I do : I search for the pair of latitudes and longitudes that are at minimum distance in the current arrays. Then I add the minimum distance to a variable that sums up all the minimum distances. Then I remove the latitudes and longitudes treated from the arrays.
Here is the code :
public class Distance {
private String filename1;
private String filename2;
public Distance(String filename1, String filename2) {
this.filename1 = filename1;
this.filename2 = filename2;
}
public double distance() {
if(this.filename1.equals(this.filename2))
return 0;
double distance = 0;
BufferedReader br1 = null;
BufferedReader br2 = null;
try {
br1 = new BufferedReader(new FileReader("files/" + this.filename1));
br2 = new BufferedReader(new FileReader("files/" + this.filename2));
String []data1 = br1.readLine().split(",");
String []data2 = br2.readLine().split(",");
System.out.println("Number of points in " + this.filename1 + " = " + data1.length/2);
System.out.println("Number of points in " + this.filename2 + " = " + data2.length/2);
while((isPresent(data1)) && (isPresent(data2))) {
int posi = -1;
int posj = -1;
double minD = Double.MAX_VALUE;
for(int i = 0; i < data1.length; i+=2) {
if(!data1[i].equals("-9999")) {
double lat1 = Double.parseDouble(data1[i]);
double lon1 = Double.parseDouble(data1[i+1]);
for(int j = 0; j < data2.length; j+=2) {
if(!data2[j].equals("-9999")) {
double lat2 = Double.parseDouble(data2[j]);
double lon2 = Double.parseDouble(data2[j+1]);
double d = getDistance(lat1, lon1, lat2, lon2);
if(minD > d) {
minD = d;
posi = i;
posj = j;
}
}
}
}
}
if(posi != -1){
data1[posi] = data1[posi+1] = data2[posj] = data2[posj+1] = "-9999";
distance += minD;
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if(br1 != null) {
try {
br1.close();
} catch (IOException e) {
e.printStackTrace();
}
}
if(br2 != null) {
try {
br2.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return distance;
}
private boolean isPresent(String arr[]) {
for(int i = 0; i < arr.length; i+=2) {
if(!arr[i].equals("-9999"))
return true;
}
return false;
}
private double getDistance(double lat1, double lon1, double lat2,
double lon2) {
double R = 6378.1; // Radius of the earth in km
double dLat = deg2rad(lat2-lat1); // deg2rad below
double dLon = deg2rad(lon2-lon1);
double a =
Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) *
Math.sin(dLon/2) * Math.sin(dLon/2)
;
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
double d = R * c; // Distance in km
return d*1000;
}
private double deg2rad(double d) {
return d * (Math.PI/180);
}
}
Do you think it is a clumsy way to do this? How can I do it quickly?
NB I have seen the Closest pair of points problem but do not know how I can implement it with latitudes and longitudes for comparison of points between two different arrays.
Hope this may help
input:files with latitude and longitude data
from first file
sort all the values on the basis of latitude and store it in array
sort all the values on the basis of longitude and store it in second array
Input size of arrays are n and m
Now pick a point from second array and find the closest point using this video
Repeat this for all points and print the minimum
Sorting each array O(nlogn)*2=O(nlogn) Finding a nearest point will be not more than O(2m)
As array length is known.Use the big size array and use it for n sized array operations.
If one of the file fixed then this can be re-used.
上一篇: 在具有信号强度的2D平面中进行三角测量
下一篇: 降低复杂性。 找到最接近的一对纬度和经度