转载请注明出处：http://blog.csdn.net/yianemail/article/details/47130525
现在大多基于地图的应用都有查看附近商家的实现，之前在网上看到别的一些方法，大多是去数据库中查看每条数据库记录的lbs 经纬度，然后跟当前经纬度计算距离，在某个范围内的则是周围商家。
数据库记录小还好，如果数据库非常庞大，每条都要做对比，岂不是很耗性能？
地球是圆形，每条纬度不等长。
一 ：
如果我们把每条数据库记录lbs信息抽取到一个集合（数组）,然后根据当前位置以及距离（假设周围3公里）算出在同一纬度，左右各三公里。然后依据左右三公里处的经度信息
利用二分查找确定该经度在集合中的位置（或者一个合适的位置，因为集合中不一定存在该经度值）。这样只对在该范围内的商家lbs信息进行距离计算即可。看一张图：
假设半径为3公里。我们只需要计算在该半径内的商店lbs信息，计算量就会少很多。
二：实现。实体类Location.java
/**
* 经纬度
* @author luhuanju
*/
public class Location{
private int id;//id 代表商家
private double Latitude;//纬度
private double Longitude;//经度
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public double getLatitude() {
return Latitude;
}
public void setLatitude(double latitude) {
Latitude = latitude;
}
public double getLongitude() {
return Longitude;
}
public void setLongitude(double longitude) {
Longitude = longitude;
}
public Location(double latitude, double longitude) {
super();
Latitude = latitude;
Longitude = longitude;
}
public Location(int id, double latitude, double longitude) {
super();
this.id = id;
Latitude = latitude;
Longitude = longitude;
}
}
然后新建测试集合。按照经度大小排序（要用到二分分治）。
import java.util.Comparator;
/**
* 排序
* @author luhuanju
*/
public class Compare implements Comparator<Object> {
@Override
public int compare(Object o1, Object o2) {
Location location1 = (Location) o1;
Location location2 = (Location) o2;
if (location1.getLongitude() > location2.getLongitude()) {
return 1;
} else if (location1.getLongitude() < location2.getLongitude()) {
return -1;
} else {
return 0;
}
}
}
public static void main(String[] args) {
List<Location> list=new ArrayList<Location>();
list.add(new Location(1,31.0214710000,121.4432520000));
list.add(new Location(1,31.0188710000,121.4446900000));
list.add(new Location(1,31.0241940000,121.4341970000));
list.add(new Location(1,31.0203560000,121.4336230000));
list.add(new Location(1,31.0210990000,121.4314670000));
list.add(new Location(1,31.0208013402,121.4322355312));
list.add(new Location(1,31.0218913198,121.4279013257));
list.add(new Location(1,31.0173210199,121.4294606657));
list.add(new Location(1,31.0229044299,121.4411514014));
Compare compare=new Compare();//实现了Comparator接口，排序
Collections.sort(list, compare);//进行按照经度排序}
二： 接下来找到距离中心点左右各三公里的经纬点。
/**
* @ luhuanju
* @param Latitude 当前纬度
* @param Longitude 当前经度
* @param distance 距离（米）
* @return 返回4个位置点。即半径为距离的上下左右位置点
*/
static Location[] mLocations = new Location[4];
private static final double EARTH_RADIUS = 6378137;
public static Location[] getRectangle4Point(double Latitude,
double Longitude, int distance) {
double dlng = 2 * Math.asin(Math.sin(distance / (2 * EARTH_RADIUS))
/ Math.cos(Latitude));
dlng = Math.toDegrees(dlng);
double dlat = distance / EARTH_RADIUS;
dlat = Math.toDegrees(dlat);
Location mLeft = new Location( Latitude,Longitude - dlng);
Location mRight = new Location(Latitude,Longitude + dlng);
Location mTop = new Location(Latitude + dlat,Longitude );
Location mBottom = new Location(Latitude - dlat,Longitude);
mLocations[0] = mLeft;
mLocations[1] = mRight;
mLocations[2] = mTop;
mLocations[3] = mBottom;
return mLocations;
}
三:
得到左右3公里位置点后，对位置点的经度信息在集合中进行二分查找。以找到确定或者合适的位置：
intLeftIndex=LbsUtil.LeftIndex(list,locations[0].getLongitude());
int RightIndex=LbsUtil.RightIndex(list, locations[1].getLongitude());
LeftIndex－RightIndex之间的元素是我们需要的进行距离比对的。
对于中心的左侧位置点而言，我们需要的是位置点右侧方向的值。即集合元素下标往大：
public static int LeftIndex(List<Location> list, double des) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (des == list.get(middle).getLongitude()) {
/**
* 若集合刚好存在该元素，则返回下标
*/
System.out.println("刚好");
just=middle;
return middle;
} else if (des < list.get(middle).getLongitude()) {
/**
*若集合不存在该元素 返回最右侧近邻下标
*/
left = middle;
high = middle - 1;
} else {
low = middle + 1;
}
}
if(just!=0){
return just;
}else{
return left;
}
}
对于中心的右侧位置点而言，我们需要的是位置左右侧方向的值。即集合元素下标往小：
public static int RightIndex(List<Location> list, double des) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (des == list.get(middle).getLongitude()) {
/**
* 若集合刚好存在该元素，则返回下标
*/
just = middle;
return middle;
} else if (des < list.get(middle).getLongitude()) {
high = middle - 1;
} else {
/**
*若集合不存在该元素 返回最左侧近邻下标
*/
right = middle;
low = middle + 1;
}
}
if(just!=0){
return just;
}else{
return right;
}
}
四： 拿到左右三公里区间商家lbs位置信息后，拿到每位商家位置点与中心点的位置信息。
/**
* 商家点与中心点的距离
* 单位米
* @param lng1
* @param lat1
* @param lng2
* @param lat2
* @return
*/
public static double GetDistance(double lng1, double lat1, double lng2, double lat2){
double radLat1 = rad(lat1);
double radLat2 = rad(lat2);
double a = radLat1 - radLat2;
double b = rad(lng1) - rad(lng2);
double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a/2),2) +
Math.cos(radLat1)*Math.cos(radLat2)*Math.pow(Math.sin(b/2),2)));
s = s * EARTH_RADIUS;
s = Math.round(s * 10000) / 10000;
return s;
}
private static double rad(double d){
return d * Math.PI / 180.0;
}
五：测试代码：
