java - 如何高效返回半径内的道路

Question

我有一个道路对象的ArrayList，其中具有数字、起始纬度、起始经度、结束纬度、结束经度等属性。现在我想返回给定经纬度值的半径为 500m 的道路。所以我尝试了

ArrayList<Roads> RoadList=new ArrayList<Roads>();

//I added all the road objects like below
RoadList.setNumber(01);
RoadList.setStartLatitude(1.24);
RoadList.setStartLongitude(102.3);
RoadList.setEndLatitude();
RoadList.setEndLongitude();

//Then I compute the distance between the end of road and given lat lon and also distance between  start of road from give lat lon values and if the distance is below 500 I pick the road object.
given latitude=1.2;
given logitude=103.8
public ArrayList<Integer> getRoads(){ 
ArrayList<Integer> roads=new ArrayList<Integer>();

for(int i=0; i<RoadList.size();i++){

double x=  Math.pow( Math.pow(RoadList.get(i).getStartLatitude()-given latitude,2)+Math.pow(RoadList.get(i).getStartLongitude()-given longitude,2),0.5);
double y=  Math.pow( Math.pow(RoadList.get(i).getEndLatitude()-given latitude,2)+Math.pow(RoadList.get(i).getEndLongitude()-given longitude,2),0.5);


if(x <500 || y<500){
  roads.add(RoadList.get(i).getNumber());
}

}
return roads;
}

由于我的ArrayList有点大，所以需要一段时间。那么有什么有效的方法可以做到这一点吗？

Answer 1

如何转换这两行

double x=  Math.pow( Math.pow(RoadList.get(i).getStartLatitude()-given latitude,2)+Math.pow(RoadList.get(i).getStartLongitude()-given longitude,2),0.5);
double y=  Math.pow( Math.pow(RoadList.get(i).getEndLatitude()-given latitude,2)+Math.pow(RoadList.get(i).getEndLongitude()-given longitude,2),0.5);

变成这样的东西

double start_x1 = RoadList.get(i).getStartLatitude()-given latitude;
double start_x2 = RoadList.get(i).getStartLongitude()-given longitude;
start_x1 *= start_x1;
start_x2 *= start_x2;

double end_x1 = RoadList.get(i).getEndLatitude()-given latitude;
double end_x2 = RoadList.get(i).getEndLongitude()-given longitude;
end_x1 *= end_x1;
end_x2 *= end_x2;

double x = Math.sqrt(start_x1 + start_x2);
double y = Math.sqrt(end_x1 + end_x2);

因此，您可以在 O(1) 内执行此计算，而不是使用 Math.pow 进行平方，这可能会提高我们的速度。

我不太确定，但你可以尝试一下并告诉我。

希望这有帮助!