椭球面上两点最短距离的算法思考

这篇具有很好参考价值的文章主要介绍了椭球面上两点最短距离的算法思考。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

椭球面上两点最短距离的三种算法思路

 如何计算椭球体 两点间距离,matlab,算法,matlab

 我们不妨以一个具体的情境去进行代码分析

如何计算椭球体 两点间距离,matlab,算法,matlab

下列程序绘制椭球面及两点的程序. 

close all
a=6000;
b=5000;
x=[2200 2900];
y=[3600 3300];
z=b*sqrt(1-(x.*x+y.*y)/(a*a)) %计算P1, P2的z坐标


v1=[x(1) y(1) z(1)];% 向量 OP1 
v2=[x(2) y(2) z(2)];% 向量 OP2
[theta,alpha]=meshgrid(linspace(0,pi/2,50), linspace(0,2*pi,50));
z=b*sin(theta);% 根据椭球面参数方程绘制半椭球面
x=a*cos(theta).*cos(alpha);
y=a*cos(theta).*sin(alpha);
mesh(x,y,z)

hold on

plot3(v1(1),v1(2),v1(3),'r.','markersize',24)
plot3(v2(1),v2(2),v2(3),'r.','markersize',24)
    1. 问题分析

1.1.1球体上最短距离

(1)方式:计算两个点和球心所表示的向量的夹角,即球心角,然后使用弧长计算公式来求解;

若采用经纬度求解则用球面距离的公式计算出球面上两点间的距离,公式如下:

distance = R * acos(cos(lat1)*cos(lat2)*cos(lon2-lon1)+sin(lat1)*sin(lat2))。

其中,R为球面半径,lat1、lat2、lon1、lon2为两点的纬度和经度。

(2)原因:球体曲率半径处处相等,弧长是在球面上连接两点的最短路径,也称为大圆弧。球体上两点间的最短路径是沿着大圆弧走,因为大圆是球面上最短的路径。而两点之间的球面距离就是沿着大圆弧所经过的弧长。

如果坐标系是经纬度坐标系,则可以通过余弦定理、球面三角公式等方法计算两点间的距离。常用的方法是Haversine公式,该公式用来计算球面上两点间的真实距离。

1.1.2椭球体上最短距离

如何计算椭球体 两点间距离,matlab,算法,matlab

(1)特点:椭球面和球面不同之处在于,其曲率半径并不是处处相等的

(2)思路:代码部分主要对A思路代码进行分析

A

网格剖分:可以借鉴微积分中化曲为直思路,将其划分为极小的网格区域,每一个网格可以视为平面,因此问题变为,划分网格法搜索椭球面上的所有点,然后计算出连接v1和v2两个点的所有路径的长度,并选出其中的最短路径,即使用贪心算法决策每一步的走向最后使结果处在最优状态(贪心算法:贪心算法是一种优化问题的解法,其基本策略是从局部最优状态出发,构建全局最优解。它通常适用于一些最优化问题,例如找到最小生成树、最短路径、最优装载、背包问题、集合覆盖等。贪心算法的设计步骤包括以下几个部分:1.确定问题的最优解结构特性,建立相应的贪心选择性质。2.采用贪心策略,使问题规模缩小,并保证问题仍然具有最优子结构。3.证明贪心选择性质和最优子结构可以得到问题的最优解。4.设计贪心算法,并用较小的时间复杂度解决问题。贪心算法不一定适用于所有问题,需要根据具体问题的特点和解法特性来确定是否适用贪心算法。在设计贪心算法时,需要注意选择合适的贪心策略,保证选择的贪心决策具有最优子结构和贪心选择性质,并且可以证明最终得到的解是全局最优解。)

B

连接两点,再选择一个点,做平面,计算平面与椭球面的在这两点之间截痕的长度。该方法的原理是将椭球看作一组半径不同的球拼接而成。在椭球上的两点之间画一条线段,然后将这条线段与一个平面相交,得到一个截痕。通过计算这个截痕的长度即可得到这条线段在椭球表面的最短距离。

C

以椭球面的参数方程,计算两点 P 对应参变量的值,然后从一点出发参变量逐步增加确定点点集,蚁群算法是一种启发式搜索算法,模拟了蚂蚁在寻找食物时的行为。这种算法的思想是,将搜索问题看作一个蚁群在植物上觅食的过程,每个蚂蚁的行为是独立的,但是通过蚁群中蚂蚁之间的相互作用,最终能够找到最优解。在蚁群算法中,每个蚂蚁的行动都是由一个局部搜索规则和一个全局搜索规则决定的。局部搜索规则是基于信息素的选择概率,即蚂蚁倾向于选择信息素强的路径,而全局搜索规则则是基于启发式信息的选择概率,即蚂蚁在选择路径时,更倾向于选择离目标点更近的路径。蚁群算法在求解椭球上两点间最短距离的问题中,利用了椭球表面的连续性,从一个起点出发逐步行进,找到最短路径,同时也可以并行地搜索多个路径。与传统的搜索算法相比,蚁群算法具有更高的搜索效率和鲁棒性,可以处理更大的数据集和更复杂的问题

    1. 1模型假设

A

(1)网格足够小,接近于平面,且划分数目合理

(2)每次移动沿最优方向

(3)假设椭球面上两点间的路径长度可以通过所有路径长度中最短的路径长度来近似表示

B

(1)最短距离是垂直于z轴的横截面的一部分

(2)交线为圆

(3)每次取最短距离

C

(1)在椭圆上已知两点之间有无数随机点,当点足够多时,已知两点之间的连线由线上的许多随机点构成。

(2)每次从一个随机点到下一个随机点的路程都移动留下记录,若该次移动为此随机点到下一个目的地间所有移动中最短的,记录该路径。

(3)每个随机点只经历一次。

    1. 变量与符号说明

A

  1. a和b为椭球的长轴和短轴。
  2. x和y表示椭球面网格点的自然坐标系下的坐标。
  3. z表示椭球面网格点在之前假设的参数方程下的z坐标坐标。
  4. v1和v2为椭球面上两点的直角坐标系下的坐标。
  5. u1, v1, u2, v2为参数方程中的两个参数,用于描述椭球面上的点的位置。
  6. step是划分网格法中的步长,用于控制划分网格的精度。

p1和p2是椭球面上网格点对应的坐标。

B

(1)a和b为椭球的长轴和短轴。

(2)x和y表示椭球面网格点的自然坐标系下的坐标。

3z表示椭球面网格点在之前假设的参数方程下的z坐标坐标。

4n所做平面数量

(5) r截面与椭球面交线的半径

(6)d距离

C

(1)m 蚂蚁数量

(2)alpha信息素重要程度因子

(3)beta启发函数重要程度因子

(4)rho信息素挥发因子

(5)Q = 1;常系数

(6)Tau信息素矩阵

(7)Table路径记录表

(8)iter迭代次数初值

9)iter_max最大迭代次数 

10)Route_best各代最佳路径       

11)Length_best各代最佳路径的长度  

11Length_ave各代路径的平均长度

 

    1. 模型建立与求解(实验过程)

A(具体代码附后)

如何计算椭球体 两点间距离,matlab,算法,matlab

 如何计算椭球体 两点间距离,matlab,算法,matlab

 

B(不做代码分析,可以私聊交流)

如何计算椭球体 两点间距离,matlab,算法,matlab

 

C(不做代码分析,可以私聊交流)

    1. 实验结果分析

A

如何计算椭球体 两点间距离,matlab,算法,matlab该程序通过划分网格法对椭球面上的点进行搜索,找到连接V1和v2两个点的所有路径中的最短路径,从而计算出椭球面上两点最短距离。

 

实验结果表明,椭球面上连接V1和v2两个点的最短距离为1000.0000。该结果可以作为对椭球面上两点间距离的一个近似估计,但实际上,该计算结果的精度受到划分网格法的步长影响,步长越小,计算结果越准确。同时,精度也会受到椭球面的形状和两点之间的位置关系的影响。因此,在实际应用中,需要根据具体情况选择合适的计算方法和精度控制,以获得更准确的计算结果。

B

如何计算椭球体 两点间距离,matlab,算法,matlab

 

该程序通过在两点之间等间距做垂直于z轴的截面,求出截面与椭圆面交线的半径(交线为圆),确定在圆周上取点的范围,均匀划分并做图,利用算法找最优点,记录最短距离,绘制点的轨迹得出结果。

实验结果会比真实结果偏小,需要更精确地调整程序

C

该程序对椭球面上已知两点间设置一定数量的随机点,再通过蚁群算法进行从一点途径随机点到另一点的路径统计。

实验结果因算法具有随机性,不能得出准确答案,大概答案得出在800-1200之间。算法的缺陷较大,如存在这收敛速度慢,容易陷入局部最优,随机性过强等缺点。因此实际应用时只作为参考。

 

    1. 优缺点及改进方向

(自评本报告内容的优点、不足之处,以及可以怎么进行改进)

A.

优点:算法思路较易,适用范围广。

缺点:计算的精度严重依赖于网格的剖分大小和方式,网格尺寸小,计算精度大,但是相应的计算量也成倍增加,会极大延长实际需要的计算时间,不利于工程实际应用和分析。

改进方式:1.采用网格局部加密算法控制计算精度,即采用金字塔式网格架构,网格从底层到顶层逐渐减小尺寸,在需要加密的位置,比方说曲率变化剧烈的地方采用较细网格,而对其他采用较粗网格,但是该方法对于现阶段我们的知识而言较复杂.

2.利用深度学习模型,如果模型能根据结果反馈修正之前环节中非最优的决策,将大大提高精度,且可用于多种模型最小值的求解,但是深度学习方面知识较为缺乏。

3.使用球坐标系可避免三角函数的运算,简化坐标系转化的过程。

B:

缺点:该思路通过连接两点,并选择中间的一个点作为平面上的点,然后计算该平面与椭球面上的交线长度,该长度即为两点之间的最短距离。这种方法的优点在于比较简单,精度也相对较高,但缺点在于需要截取椭球面与平面之间的曲线长度,难度较大。

C

该程序对椭球面上已知两点间设置一定数量的随机点,再通过蚁群算法进行从一点途径随机点到另一点的路径统计。

缺点:实验结果因算法具有随机性,不能得出准确答案,大概答案得出在800-1200之间。在实际问题中,蚁群算法需要设置合适的参数,如蚂蚁数量、信息素挥发因子等,才能达到最优解。而这些参数的设置需要一定的经验和调试,不同的参数设置也可能导致不同的结果。

优点:当迭代次数足够大时,结果近似于准确答案。且蚁群算法具有自适应性和并行性,可以在大规模数据集上高效地求解问题。在求解椭圆面上最短路径问题中,蚁群算法可以通过模拟蚂蚁在椭圆面上的行走路径,不断更新最短路径,并最终收敛到最优解。

  1. 检验方案

1.求一个两点间直线距离作为下限距离,再求一个折线较短距离,如果运行结果落在区间里,就说明在误差允许范围

2.定两个特殊点,如椭球的端点,验证一下特殊情况下程序输出结果是否正确

 代码

a = 6000; b = 5000; 
x = [2200 2900];  % 第一个点和第二个点的x坐标
y = [3600 3300];  % 第一个点和第二个点的y坐标
% 计算第一个点和第二个点在椭球面上的z坐标
z = b * sqrt(1 - (x.*x + y.*y) / (a*a));
% 将自然坐标系转换为直角坐标系
v1 = [a*cos(y(1)*pi/180)*cos(x(1)*pi/180), a*cos(y(1)*pi/180)*sin(x(1)*pi/180), b*sin(y(1)*pi/180)];
v2 = [a*cos(y(2)*pi/180)*cos(x(2)*pi/180), a*cos(y(2)*pi/180)*sin(x(2)*pi/180), b*sin(y(2)*pi/180)];
% 定义划分网格的步长
step = 0.01;
% 在划分网格上搜索最短路径
min = inf;
for u1 = 0:step:1
    for v1 = 0:step:1
        % 计算当前网格点对应的点在椭球面上的坐标
        p1 = [a*cos(2*pi*u1)*sin(pi*v1), a*sin(2*pi*u1)*sin(pi*v1), b*cos(pi*v1)];
        for u2 = 0:step:1
            for v2 = 0:step:1
                % 计算当前网格点对应的点在椭球面上的坐标
                p2 = [a*cos(2*pi*u2)*sin(pi*v2), a*sin(2*pi*u2)*sin(pi*v2), b*cos(pi*v2)];
                % 计算当前路径长度
                dist = norm(p1 - v1) + norm(p1 - p2) + norm(p2 - v2);
                % 判断当前路径是否比当前的最短路径更短
                if dist < min
                    min = dist;
                end
            end
        end
    end
end
fprintf('椭球面上两点最短距离为 %.4f\n', min);

希望大家批评指正!文章来源地址https://www.toymoban.com/news/detail-794813.html

到了这里,关于椭球面上两点最短距离的算法思考的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 空间分析实战指南:点到多边形的最短距离

    在我们最近的项目中,出现了一个新的需求:需要验证现场拍摄的照片的经纬度与实际地块之间的最短距离,以确保业务员在地块的一公里范围内进行拍照。 实现这个功能有两种方式,一种是在前台APP中校验,一种是在后台进行校验,接下来我会分别介绍这两种方式。 在我

    2024年02月13日
    浏览(37)
  • 力扣(leetcode)第821题字符的最短距离(Python)

    题目链接:821.字符的最短距离 给你一个字符串 s 和一个字符 c ,且 c 是 s 中出现过的字符。 返回一个整数数组 answer ,其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。 两个下标 i 和 j 之间的 距离 为 abs(i - j) ,其中 abs 是绝对值函数。 示

    2024年01月19日
    浏览(36)
  • GEE机器学习——利用最短距离方法进行土地分类和精度评定

    最短距离方法(Minimum Distance)是一种常用的模式识别算法,用于计算样本之间的相似度或距离。该方法通过计算样本之间的欧氏距离或其他距离度量,来确定样本之间的相似程度或差异程度。 最短距离方法的具体步骤如下: 1. 数据准备:收集并准备用于训练的数据集,确保

    2024年01月20日
    浏览(53)
  • 2023河南萌新联赛第(二)场:河南工业大学 F - 最短距离

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 给定一棵包含 n n n 个顶点的树 T T T ,以及 m m m 个查询请求。每个查询包含三个参数 : x 、 y :x、y : x 、 y 和 k k k 。其中 x x x 和 y y y 是树中的两个顶点, k k k 是一个整数。对于

    2024年02月15日
    浏览(41)
  • C++ 如何求点到直线的距离?(两点式)

    点到直线的距离公式: 将两点式整理可得: 两者结合可得: (其中:fabs是求绝对值,sqrt是开2次根号,pow是求一个数的n次方) 运行结果: 参考文章:一点到另外两点所成直线的距离

    2024年02月14日
    浏览(38)
  • Java根据坐标经纬度计算两点距离(5种方法)、校验经纬度是否在圆/多边形区域内的算法推荐

    目录 前言 一、根据坐标经纬度计算两点距离(5种方法) 1.方法一 2.方法二 3.方法三 4.方法四 5.方法五 5.1 POM引入第三方依赖 5.2 代码 6.测试结果对比 二、校验经纬度是否在制定区域内 1.判断一个坐标是否在圆形区域内 2.判断一个坐标是否在一个多边形区域内 3.结果 总结   

    2024年02月10日
    浏览(82)
  • mysql 计算两点之间距离

    先说一下我们可能会用到的一些场景,这样同学们可以先评估,该篇文章是否对你有帮助! 场景: 假设 美团,我点外卖时,系统会让我先进行定位,比如我定位在了 A 点,系统就会给我推荐,离 A 点最近的商家们,我们先排除评分等等条件,只看距离,优先距离(最近的商家

    2024年02月11日
    浏览(36)
  • 根据经纬度计算两点之间的距离

    前言 在我们平时使用美团,饿了么等app进行订餐,或者使用猫眼进行订电影票的时候,都有一个距离的排序,表明该家店距离我们当前的位置,这种基于地理位置的服务,统一被称为LBS(Location Based Service),而LBS的实现则是借助于GIS,WC(无线通信)等信息技术来实现。而今

    2024年02月05日
    浏览(86)
  • python实现d435i深度相机测量两点之间的距离

    本文介绍python方法实现intel公司realsense系列d435i深度相机测量彩色图像上两点之间的距离。 原理很简单,就是将相机获得的彩色图像流与深度流对齐,这样彩色图像上的每个像素就会对应一个深度值,作为z坐标,然后通过相机内参获得该像素的x坐标和y坐标。我们获得的x、

    2024年02月16日
    浏览(37)
  • 根据经纬度计算地球上两点之间的距离——Haversine公式介绍及计算步骤

    目录 摘要 1.半正矢公式(Haversine Formula)介绍 2.半正矢公式应用 3.半正矢公式计算 3.1 主要思路 3.2 计算步骤 3.2.1 平面向量计算方法 3.2.2 空间向量计算方法 写本文的出发点是需要在Qlik中根据经纬度计算地球上两点间的距离。我在社区上搜到了相关公式的分享,这个公式叫做

    2023年04月10日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包