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

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.rhkb.cn/news/493555.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Intel-ECI之Codesys PLC + Ethercat 远端IO + Codesys IDE编程

Intel-ECI之Codesys PLC + Ethercat 远端IO + Codesys IDE编程

目录 一、 准备工作 二、安装Codesys 软件 PLC 三、 使用Codesys IDE 编程测试 CODESYS* 是领先的独立于制造商的 IEC 61131-3 自动化软件&#xff0c;适用于工程控制系统。它用于 Intel Edge Controls for Industrial&#xff08;Intel ECI 或 ECI&#xff09;&#xff0c;…
阅读更多...
渗透测试-前端加密分析之RSA加密登录（密钥来源服务器）

渗透测试-前端加密分析之RSA加密登录（密钥来源服务器）

本文是高级前端加解密与验签实战的第6篇文章&#xff0c;本系列文章实验靶场为Yakit里自带的Vulinbox靶场&#xff0c;本文讲述的是绕过RSA加密来爆破登录。 分析 这里的代码跟上文的类似&#xff0c;但是加密的公钥是通过请求服务端获取的 http://127.0.0.1:8787/crypto/js/…
阅读更多...
【Leecode】Leecode刷题之路第87天之扰乱字符串

【Leecode】Leecode刷题之路第87天之扰乱字符串

题目出处 87-扰乱字符串-题目出处 题目描述 个人解法 思路&#xff1a; todo代码示例&#xff1a;&#xff08;Java&#xff09; todo复杂度分析 todo官方解法 87-扰乱字符串-官方解法 方法1&#xff1a;动态规划 思路&#xff1a; 代码示例&#xff1a;&#xff08;Java&…
阅读更多...
Qt之串口设计-线程实现（十二）

Qt之串口设计-线程实现（十二）

Qt开发 系列文章 - Serial-port&#xff08;十二&#xff09; 目录 前言 一、SerialPort 二、实现方式 1.创建类 2.相关功能函数 3.用户使用 4.效果演示 5.拓展应用-实时刷新 总结 前言 Qt作为一个跨平台的应用程序开发框架&#xff0c;在串口编程方面提供了方便易用…
阅读更多...
Restaurants WebAPI（三）——Serilog/

Restaurants WebAPI（三）——Serilog/

文章目录 项目地址一、Serilog使用1.1 安装 Serilog1.2 注册日志服务1.3 设置日志级别和详情1.4 配置到文件里1.5 给不同的环境配置日志1.5.1 配置appsettings.Development.json二、Swagger的使用三、自定义Exception中间件3.1 使用FluentValidation项目地址 教程作者：教程地址…
阅读更多...
Tekscan压力分布测量系统：电池安全与质量提升的保障

Tekscan压力分布测量系统：电池安全与质量提升的保障

随着科技的快速发展&#xff0c;电池技术在电动汽车、工业和消费电子等领域的重要性日益增加。Tekscan 压力分布测量系统针对这些领域的需求&#xff0c;成为推动电池技术进步和多领域创新的重要工具。 在锂离子电池的充放电过程中&#xff0c;热循环引起的膨胀和收缩对其性能和…
阅读更多...
【WRF教程第3.1期】预处理系统 WPS 详解：以4.5版本为例

【WRF教程第3.1期】预处理系统 WPS 详解：以4.5版本为例

预处理系统 WPS 详解&#xff1a;以4.5版本为例 每个 WPS 程序的功能程序1&#xff1a;geogrid程序2&#xff1a;ungrib程序3&#xff1a;metgrid WPS运行&#xff08;Running the WPS&#xff09;步骤1&#xff1a;Define model domains with geogrid步骤2&#xff1a;Extract…
阅读更多...
开源轮子 - Logback 和 Slf4j

开源轮子 - Logback 和 Slf4j

spring boot内置&#xff1a;Logback 文章目录 spring boot内置&#xff1a;Logback一&#xff1a;Logback强在哪&#xff1f;二&#xff1a;简单使用三&#xff1a;把 log4j 转成 logback四&#xff1a;日志门面SLF4J1&#xff1a;什么是SLF4J2&#xff1a;SLF4J 解决了什么痛…
阅读更多...
Linux下部署MySQL8.0集群 - 主从复制(一主两从)

Linux下部署MySQL8.0集群 - 主从复制(一主两从)

目录 一、部署前准备 1、查看系统信息 # 查看系统版本 cat /etc/red* # 查看系统位数 getconf LONG_BIT[rootlocalhost ~]# cat /etc/red* CentOS Linux release 7.5.1804 (Core) [rootlocalhost ~]# getconf LONG_BIT 642、下载对应安装包 进入MySQL官网&#xff1a;https:…
阅读更多...
springboot中的AOP以及面向切面编程思想

springboot中的AOP以及面向切面编程思想

快速入门体验AOP aop中相关概念 实现导入依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-aop</artifactId> </dependency> 新建aop文件夹，里面声明XXXAspect类 @Aspect // 声…
阅读更多...
在Java虚拟机（JVM）中，方法可以分为虚方法和非虚方法。

在Java虚拟机（JVM）中，方法可以分为虚方法和非虚方法。

在Java虚拟机（JVM）中，方法可以分为虚方法和非虚方法。以下是关于这两种方法的详细解释： 一、虚方法（Virtual Method） 定义：虚方法是指在运行时由实例的实际类型决定的方法。在Java中，所有的非私有、非静态、非final方法都是虚方法。当调用一个虚方法时，JVM会根据实…
阅读更多...
Java图片拼接

Java图片拼接

最近遇到一个挺离谱的功能&#xff0c;某个表单只让上传一张图&#xff0c;多图上传会使导出失败。跟开发沟通后表示&#xff0c;这个问题处理不了。我... 遂自己思考&#xff0c;能否以曲线救国的方式拯救一下&#xff0c;即不伤及代码之根本&#xff0c;又能解决燃眉之急。灵…
阅读更多...
webGL硬核知识：图形渲染管渲染流程，各个阶段对应的API调用方式

webGL硬核知识：图形渲染管渲染流程，各个阶段对应的API调用方式

一、图形渲染管线基础流程概述 WebGL 的图形渲染管线大致可分为以下几个主要阶段&#xff0c;每个阶段都有其特定的任务&#xff0c;协同工作将 3D 场景中的物体最终转换为屏幕上呈现的 2D 图像&#xff1a; 顶点处理&#xff08;Vertex Processing&#xff09;阶段&#xff1…
阅读更多...
大数据面试题--企业面试真题

大数据面试题--企业面试真题

大数据面试题--企业面试真题 PlanHub 点击访问获取&#xff1a; 大数据面试体系专栏_酷兜科技​www.kudoumh.top/hlwai/85.html 点击访问获取&#xff1a; 大数据面试体系专栏_酷兜科技​www.kudoumh.top/hlwai/85.html 大数据面试题汇总 HDFS 1、 HDFS 读写流程。 2、HDF…
阅读更多...
lambda初探（一）

lambda初探（一）

发生捕获时&#xff0c;拿到x,y的值 退出lambda表达式后&#xff0c;foo外层的值不变化。foo内部的x&#xff0c;值是持续的&#xff0c;像static。即使退出foo函数后&#xff0c;值的状态依然保持。 外层x的值变化&#xff0c;并不影响foo内部。 foo运行了两次&#xff0c;内…
阅读更多...
【D3.js in Action 3 精译_046】DIY 实战：在 Observable 平台利用饼图布局函数实现 D3 多个环形图的绘制

【D3.js in Action 3 精译_046】DIY 实战：在 Observable 平台利用饼图布局函数实现 D3 多个环形图的绘制

当前内容所在位置&#xff1a; 第五章 饼图布局与堆叠布局 ✔️ 5.1 饼图和环形图的创建 ✔️ 5.1.1 准备阶段&#xff08;一&#xff09;5.1.2 饼图布局生成器&#xff08;二&#xff09;5.1.3 圆弧的绘制&#xff08;三&#xff09;5.1.4 数据标签的添加&#xff08;四&#…
阅读更多...
基于Spring Boot的智慧农业专家远程指导系统

基于Spring Boot的智慧农业专家远程指导系统

一、系统背景与意义 随着科技的不断进步&#xff0c;农业领域也在积极寻求创新与发展。然而&#xff0c;传统农业生产中农民往往依靠经验进行种植和养殖&#xff0c;缺乏科学的指导和技术支持。同时&#xff0c;农业专家资源有限&#xff0c;难以覆盖广大的农村地区&#xff0…
阅读更多...
【JavaEE初阶】线程 和 thread

【JavaEE初阶】线程 和 thread

本节⽬标 认识多线程 掌握多线程程序的编写 掌握多线程的状态 一. 认识线程&#xff08;Thread&#xff09; 1概念 1) 线程是什么 ⼀个线程就是⼀个 "执⾏流". 每个线程之间都可以按照顺序执⾏⾃⼰的代码. 多个线程之间 "同时" 执⾏着多份代码. 还…
阅读更多...
练习题 最小栈

练习题 最小栈

最小栈 最小栈 class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {stacknew Stack<>();minstacknew Stack<>();}public void push(int val) {stack.push(val);if(minstack.empty()){minstack.push(…
阅读更多...
全志H618 Android12修改doucmentsui鼠标单击图片、文件夹选中区域

全志H618 Android12修改doucmentsui鼠标单击图片、文件夹选中区域

背景： 由于当前的文件管理器在我们的产品定义当中，某些界面有改动的需求，所以需要在Android12 rom中进行定制以符合当前产品定义。 需求： 在进入File文件管理器后，鼠标左击整个图片、整个文件夹可以选中该类型，进行操作，故代码分析以及客制化如下： 主要涉及的代码：…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023