1、场景描述
给定点Point A （x,y）和 直线点集合 Points [(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)......],计算出集合中距离点A最近的一个点 （如果集合中的两个点距离A点最近且相等，则只取其中一个）
2、代码，
LatLngXY.java
package com.example.demo.letcode;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class LatLngXY {
private Double x;
private Double y;
}
3、二分算法代码
BinarySearch.java
package com.example.demo.letcode;
import com.google.common.collect.Lists;
import com.google.common.util.concurrent.AtomicDouble;
import java.util.List;
public class BinarySearch {
/**
* 二分查找算法
*
* @param latLngList 给定点集合
* @param latLng 给定点
* @param atomicDouble 存储最小距离
* @return
*/
public static LatLngXY binarySearch(List<LatLngXY> latLngList, LatLngXY latLng, AtomicDouble atomicDouble) {
if (latLngList.size() == 1) {
return latLngList.get(0);
}
//
int middle = latLngList.size() / 2;
LatLngXY middleLatLng = latLngList.get(middle);
List<LatLngXY> left = latLngList.subList(0, middle);
List<LatLngXY> right = latLngList.subList(middle, latLngList.size());
//计算中间点距离
double dis = distatce(middleLatLng, latLng);
atomicDouble.set(dis);
if (dis == 0) {
//距离是0 点重合 直接返回
return middleLatLng;
} else {
if (right.size() == 1) {
//右侧 就一个元素 是中间元素已经对比过了
//取左侧最后一个点
LatLngXY leftLast = left.get(left.size() - 1);
double leftdis = distatce(latLng, leftLast);
if (leftdis == atomicDouble.get()) {
return leftLast;
}
if (leftdis > atomicDouble.get()) {
//中间点 距离小于左侧的
return middleLatLng;
}
//左侧点距离小于当前中间点计算距离 且小于右侧点计算的距离 递归查找左侧
if (leftdis < atomicDouble.get()) {
atomicDouble.set(leftdis);
return binarySearch(left, latLng, atomicDouble);
}
} else {
//右侧多个元素
//取左侧最后一个点
LatLngXY leftLast = left.get(left.size() - 1);
// 取右侧第二个点 没有则取第一个点
LatLngXY rightSecond = right.get(1);
double leftdis = distatce(latLng, leftLast);
double rightDis = distatce(latLng, rightSecond);
//正好中间就是距离最小的
if (rightDis > atomicDouble.get() && leftdis > atomicDouble.get()) {
return middleLatLng;
}
if (leftdis == atomicDouble.get()) {
return leftLast;
}
if (rightDis == atomicDouble.get()) {
return rightSecond;
}
//左侧点距离小于当前中间点计算距离 且小于右侧点计算的距离 递归查找左侧
if (leftdis < atomicDouble.get() && leftdis < rightDis) {
atomicDouble.set(leftdis);
return binarySearch(left, latLng, atomicDouble);
}
//右侧点距离小于当前中间点计算距离 且小于左侧点计算的距离 递归查找右侧
if (rightDis < atomicDouble.get() && rightDis < leftdis) {
atomicDouble.set(rightDis);
return binarySearch(right, latLng, atomicDouble);
}
}
}
return null;
}
/**
* 计算两点之间距离
*
* @param latLng1
* @param latLng2
* @return
*/
public static double distatce(LatLngXY latLng1, LatLngXY latLng2) {
double x = latLng2.getX() - latLng1.getX();
double y = latLng2.getY() - latLng1.getY();
//平方相加
double xy = Math.pow(x, 2) + Math.pow(y, 2);
//开方
return Math.sqrt(xy);
}
public static void main(String[] args) {
List<LatLngXY> latLngList = Lists.newArrayList();
LatLngXY lanLng1 = LatLngXY.builder().y(0D)
.x(1D).build();
LatLngXY lanLng2 = LatLngXY.builder().y(0D)
.x(2D).build();
LatLngXY lanLng3 = LatLngXY.builder().y(0D)
.x(3D).build();
LatLngXY lanLng4 = LatLngXY.builder().y(0D)
.x(4D).build();
LatLngXY lanLng5 = LatLngXY.builder().y(0D)
.x(5D).build();
LatLngXY lanLng6 = LatLngXY.builder().y(0D)
.x(6D).build();
LatLngXY lanLng7 = LatLngXY.builder().y(0D)
.x(7D).build();
latLngList.add(lanLng1);
latLngList.add(lanLng2);
// latLngList.add(lanLng3);
latLngList.add(lanLng4);
latLngList.add(lanLng5);
latLngList.add(lanLng6);
latLngList.add(lanLng7);
LatLngXY lanLng81 = LatLngXY.builder().y(0D)
.x(3.5D).build();
LatLngXY search1 = binarySearch(latLngList, lanLng81, new AtomicDouble(Double.MAX_VALUE));
System.out.println(search1);
// LatLngXY lanLng82 = LatLngXY.builder().y(0D)
// .x(1.0D).build();
// LatLngXY search2 = binarySearch(latLngList, lanLng82, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search2);
//
// LatLngXY lanLng83 = LatLngXY.builder().y(0D)
// .x(1.2D).build();
// LatLngXY search3 = binarySearch(latLngList, lanLng83, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search3);
//
// LatLngXY lanLng84 = LatLngXY.builder().y(0D)
// .x(1.8D).build();
// LatLngXY search4 = binarySearch(latLngList, lanLng84, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search4);
//
// LatLngXY lanLng85 = LatLngXY.builder().y(0D)
// .x(2.0D).build();
// LatLngXY search5 = binarySearch(latLngList, lanLng85, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search5);
//
// LatLngXY lanLng86 = LatLngXY.builder().y(0D)
// .x(2.2D).build();
// LatLngXY search6 = binarySearch(latLngList, lanLng86, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search6);
//
// LatLngXY lanLng87 = LatLngXY.builder().y(0D)
// .x(2.6D).build();
// LatLngXY search7 = binarySearch(latLngList, lanLng87, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search7);
//
// LatLngXY lanLng88 = LatLngXY.builder().y(0D)
// .x(3.0D).build();
// LatLngXY search8 = binarySearch(latLngList, lanLng88, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search8);
//
// LatLngXY lanLng89 = LatLngXY.builder().y(0D)
// .x(3.2D).build();
// LatLngXY search9 = binarySearch(latLngList, lanLng89, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search9);
//
// LatLngXY lanLng810 = LatLngXY.builder().y(0D)
// .x(3.8D).build();
// LatLngXY search10 = binarySearch(latLngList, lanLng810, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search10);
//
// LatLngXY lanLng811 = LatLngXY.builder().y(0D)
// .x(4.0D).build();
// LatLngXY search11 = binarySearch(latLngList, lanLng811, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search11);
//
// LatLngXY lanLng812 = LatLngXY.builder().y(0D)
// .x(4.2D).build();
// LatLngXY search12 = binarySearch(latLngList, lanLng812, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search12);
//
// LatLngXY lanLng813 = LatLngXY.builder().y(0D)
// .x(4.6D).build();
// LatLngXY search13 = binarySearch(latLngList, lanLng813, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search13);
//
// LatLngXY lanLng814 = LatLngXY.builder().y(0D)
// .x(5.0D).build();
// LatLngXY search14 = binarySearch(latLngList, lanLng814, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search14);
//
// LatLngXY lanLng815 = LatLngXY.builder().y(0D)
// .x(5.2D).build();
// LatLngXY search15 = binarySearch(latLngList, lanLng815, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search15);
//
// LatLngXY lanLng816 = LatLngXY.builder().y(0D)
// .x(5.8D).build();
// LatLngXY search16 = binarySearch(latLngList, lanLng816, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search16);
//
// LatLngXY lanLng817 = LatLngXY.builder().y(0D)
// .x(6.0D).build();
// LatLngXY search17 = binarySearch(latLngList, lanLng817, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search17);
//
// LatLngXY lanLng818 = LatLngXY.builder().y(0D)
// .x(6.2D).build();
// LatLngXY search18 = binarySearch(latLngList, lanLng818, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search18);
//
// LatLngXY lanLng819 = LatLngXY.builder().y(0D)
// .x(6.8D).build();
// LatLngXY search19 = binarySearch(latLngList, lanLng819, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search19);
//
//
// LatLngXY lanLng820 = LatLngXY.builder().y(0D)
// .x(7.0D).build();
// LatLngXY search20 = binarySearch(latLngList, lanLng820, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search20);
//
//
// LatLngXY lanLng821 = LatLngXY.builder().y(0D)
// .x(7.6D).build();
// LatLngXY search21 = binarySearch(latLngList, lanLng821, new AtomicDouble(Double.MAX_VALUE));
// System.out.println(search21);
}
}