转载请注明出处：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 {@Overridepublic 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()二： 接下来找到距离中心点左右各三公里的经纬点。
/** * @ 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 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
对于中心的右侧位置点而言，我们需要的是位置左右侧方向的值。即集合元素下标往小：
public static int RightIndex(List 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/** * 商家点与中心点的距离 * 单位米 * @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; }
五：测试代码：
