如何高效地 return 半径内的道路

Question

我有一个 Road Object 的 ArrayList，它具有诸如数字、start_latitude、start_longitude、end_latitude、end_longitude 等属性。现在我想 return 对于给定的经纬度值，半径为 500 米的道路。所以我尝试了

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 有点大，所以需要 while.So 有什么有效的方法吗？

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 进行平方，这可能会提高我们的速度。

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

希望对您有所帮助！

Answer 2

我会为区域对象使用空间索引，例如四叉树、R 树或 PH 树。

您可以将路段作为矩形插入（选择矩形，使得路段是矩形的对角线）。然后您可以执行 window-查询，查询 window 您的搜索点 +/- 500m。这将 return 所有与查询 window 相交的矩形（路段）。作为最后一步，您必须检查所有 returned 分段天气，它们确实在给定半径内，因为查询 window 是矩形的，并且可能 return 分段有点太远离开。

Java 可以找到各种空间索引的实现 here and here。

如何高效地 return 半径内的道路

How to efficiently return the Roads within a radius

java

arraylist

latitude-longitude

data-structures