当前位置：首页 > news >正文

使用二分查找法找出给定点距离给定点集合距离最近的点

news 2025/7/5 15:06:07

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);}}

查看全文

http://www.lryc.cn/news/507229.html