精华内容
下载资源
问答
  • js百度地图计算点与折线最短距离
    千次阅读
    2022-03-02 19:18:48

    百度地图Android SDk中的方法,用js重写,原理不懂,实际使用时感觉有明显误差,但误差可以接受。

    /**
     * 
     * @param linesPoint 折线点列表 Point(lng,lat)
     * @param point 计算最短距离点
     * @param map 百度地图实例,用于计算两点间距离
     * @returns {{distance: number, point: (*)}} 最短距离,点
     */
    function getNearestPointFromLine(linesPoint, point, map) {
        var lineBeginPoint = linesPoint[0];
        var linePointSize = linesPoint.length;
        var closestPoint;
        var closestDistance = Infinity;
        for (var i = 1; i <= linePointSize - 1; i++) {
            var lineEndPoint = linesPoint[i];
            var closestPointByLine = getClosestPoint(point, lineBeginPoint, lineEndPoint);
            var distance = parseInt(map.getDistance(point, closestPointByLine));
            if (distance < closestDistance) {
                closestDistance = distance;
                closestPoint = closestPointByLine;
            }
            lineBeginPoint = lineEndPoint;
        }
        return {point: closestPoint, distance: closestDistance};
    }
    
    function getClosestPoint(target, lineBegin, lineEnd) {
        var p1 = (lineEnd.lng - lineBegin.lng) * (target.lng - lineBegin.lng) +
            (lineEnd.lat - lineBegin.lat) * (target.lat - lineBegin.lat);
        if (p1 <= 0.0) {
            return lineBegin;
        } else {
            var p2 = (lineEnd.lng - lineBegin.lng) * (lineEnd.lng - lineBegin.lng) +
                (lineEnd.lat - lineBegin.lat) * (lineEnd.lat - lineBegin.lat);
            if (p1 >= p2) {
                return lineEnd;
            } else {
                var p3 = p1 / p2;
                var p4 = lineBegin.lng + (lineEnd.lng - lineBegin.lng) * p3;
                var p5 = lineBegin.lat + (lineEnd.lat - lineBegin.lat) * p3;
                return new BMap.Point(p4, p5);
            }
        }
    }
    
    更多相关内容
  • 计算点到直线的最短距离,适用于地图坐标
  • 使用深搜找到最短位置,地图 本题要求是求出初始位置到达目标位置的最短距离 输入条件: 5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3 第一行是5行四列 中间到最后一列之前是地图,0代表无障碍物,1代表有...

    推荐好书 《啊哈!算法》 真的比别的书更容易理解
    需要pdf的可以加我,可以分享

    ————————————————————————————————————————

    本篇是用来记录看书笔记的,来源于 《啊哈!算法》

    dfs基本模型

    在这里插入图片描述

    1.使用深搜来进行全排列

    其中的book数组来存放是否已经存在之前放进a数组中的数
    a数组用来存放每一次的结果

    #include <stdio.h>
    int n;
    int a[10],book[10];  //c语言中全局变量没有赋值以前为0 
    void dfs(int step)   //深搜 
    {
    	int i;
    	if(step==n+1){   //这里是到最后的时候 
    		for(i=1;i<=n;i++)
    			printf("%d ",a[i]);
    		printf("\n");
    		return;     //此时设置出口出去 
    	}
    	for(i=1;i<=n;i++){
    		if(book[i]==0){
    			a[step] = i;
    			book[i]=1;
    			dfs(step+1);  //这里通过调用自身 
    			book[i] = 0;
    		}
    	}
    }
    int main()
    {
    	scanf("%d",&n);
    	dfs(1);
    	return 0;
    } 
    

    深搜实际上来说就是找一个方向找到底,再进行别的方向找到底,直至最后

    ————————————————————————————————————————

    2.使用深搜找到最短位置,地图

    本题要求是求出初始位置到达目标位置的最短距离

    输入条件
    5 4
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1
    1 1 4 3

    第一行是5行四列
    中间到最后一列之前是地图,0代表无障碍物,1代表有障碍物
    最后一行是初始位置(1,1) 目标位置为(4,3)

    #include <stdio.h>
    int n,m,p,q,min=9999999;
    int a[51][51],book[51][51];
    
    void dfs(int x,int y,int step)
    {
    	int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    	int i,tx,ty;
    	if(x==p&&y==q){   //到达终点 
    		if(step<min)
    			min = step;
    		return;   //找到的话就结束 
    	} 
    	for(i=0;i<4;i++){
    		tx = x+next[i][0];   //tx,ty分别为向一个方向走 
    		ty = y+next[i][1];
    		if(tx<1||tx>m||ty<1||ty>n)
    			continue;
    		if(a[tx][ty]==0&&book[tx][ty]==0){   //不是障碍物或者之前已经走过的路径 
    			book[tx][ty]=1;     //提前说明这个已经走过了 
    			dfs(tx,ty,step+1);  //进行深搜 
    			book[tx][ty]=0;     //保存原来的点 
    		} 
    	}
    }
    
    int main()
    {
    	int i,j,startx,starty;
    	scanf("%d%d",&n,&m);   //n为行,m为列
    	//读入迷宫
    	for(i=1;i<=n;i++)
    		for(j=1;j<=m;j++)
    			scanf("%d",&a[i][j]);
    	
    	//读入起点和终点
    	scanf("%d%d%d%d",&startx,&starty,&p,&q); 
    	//从起点开始搜索
    	book[startx][starty] = 1;
    	dfs(startx,starty,0);   //其中包括起始位置和步数
    	
    	//输出最短步数
    	printf("%d",min); 
    	
    	return 0;
    }
    

    运行结果为:7

    解决思路
    1.找到最短路径那就需要把各个方向位置都去走过一遍,最后才能求出最短的距离(因为是深搜,所以必须把所有的路径都求过去)
    2.本题需要两个数组,一个用来存放地图,另一个存放的是方向,本题代码中next就是存放的是方向,4行每一行代表x和y分别加多少,就是上下左右四个方向
    3.dfs应当有三个条件,两个是x和y,另外一个就是步数,用来求最短的步数
    4.就是判断是否出界的条件,还有就是是否当前是障碍物和曾经走过的位置
    5.走到最后终点进行最小值的比对,进而求出最短路径

    ————————————————————————————————————————

                                                      可以加qq群一起学习讨论:891507813
    
    展开全文
  • 点到线段最短距离的运算与点到直线的最短距离的运算二者之间存在一定的差别,即求点到线段最短距离时需要考虑参考点在沿线段方向的投影点是否在线段,若在线段才可采用点到直线距离公式
  • 地图最短路径算法

    2019-03-24 23:28:35
    最短路径算法,做了堆优化有测试用例,可以随机生成地图地图中的数字代表的是该点的高度,高度差为两点的距离
  • 求出最短距离的方案。 这次也是搭配着矩形图来解决 在这里0就是代表自己相同点重合,无穷则代表两点之间没有关系,里面大于0的数字是两点之间的距离 举例子: 输入1 2 2 意思就是顶点1指向顶点2 两点之间距离为2 ...

    在这里插入图片描述
    求出最短距离的方案。

    这次也是搭配着矩形图来解决
    在这里插入图片描述
    在这里0就是代表自己相同点重合,无穷则代表两点之间没有关系,里面大于0的数字是两点之间的距离

    举例子
    输入1 2 2 意思就是顶点1指向顶点2 两点之间距离为2
    输入4 5 5 意思就是顶点4指向顶点5 两点之间距离为5

    顶点之间指向方向以及,两点之间距离等信息放在表中,在利用表中数据来求出

    输入内容
    5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3

    第一行 第一个5 的意思是创建5*5的表格  第二个8是等下输入8行
    后面8行  就是8组(两个顶点+距离) 每组第一个指向第二个
    

    代码

    #include <stdio.h>
    int min=99999999,book[101],n,e[101][101];
    
    //cur是当前所在的城市编号,dis是当前已经走过的路程 
    void dfs(int cur,int dis)
    {
    	int j;
    	//如果当前走过的路已经大于之前找到的最短路了,就可以返回了
    	if(dis>min) return;
    	if(cur==n)  //判断是否达到目标
    	{
    		if(dis<min)
    			min = dis;
    		return;
    	} 
    	
    	//依次1-n个城市尝试
    	for(j=1;j<=n;j++){
    		if(e[cur][j]!=99999999&&book[j]==0)
    		{
    			book[j]=1; //标记已经访问了
    			dfs(j,dis+e[cur][j]);  //从该城市出发继续寻找目标
    			book[j]=0;   //访问完要取消访问 
    		} 
    	}
    	return; 
    } 
    
    int main()
    {
    	int i,j,m,a,b,c;
    	scanf("%d%d",&n,&m);
    	//初始化二维矩阵
    	for(i=1;i<=n;i++)
    		for(j=1;j<=n;j++)
    			if(i==j) e[i][j]=0;
    			else   e[i][j]=99999999;
    	for(i=1;i<=m;i++)
    	{
    		scanf("%d%d%d",&a,&b,&c);
    		e[a][b] = c;
    	}
    	//进行标记 book[1]=1
    	book[1]=1;
    	dfs(1,0);  //从第一个点开始出发,0表示走过的路径
    	printf("%d",min); 
    	return 0;
    } 
    

    最后运行结果为:9

    整体大概过程

    这里的9999999假设为无穷,e数组是个二维数组 就是表格用来存放关于顶点之间信息
    book数组用来保存是否访问过该节点

    第一步:输入表格的长度以及下面几组顶点方向及距离,给表格首先赋全值,后面根据8行再次填充对应表格位置的长度。

    第二步:book的首位地址为1表示已经访问过了,进入dfs
    先看其中for循环,首先第一步访问第一行数据,根据判断条件到第二个点满足,于是先给book数组对应记上已经访问过
    紧接着进行调用自身进入第二组循环,(此时第一组for循环并没有执行完),在第二组循环中找到满足条件为3,book数组记上
    现在进行第三行 (此时一,二组都没执行完) 第三行中第一个已经访问过,后面有找到对应的位置4 , book数组记上
    进入第四行了 (此时一,二,三组都没执行完) 第四行中找到对应点为5 book数组记上
    进入第五行 也就是目的点了

    找到终点了,应当给出条件让它结束了 此时求出第一组例子的暂且最小值
    此时是不是就结束了,并没有之前一二三组循环并没有结束 ,
    我们回到第四行继续执行
    5这个点找完后 这个循环也结束了
    那么回到 第三个循环 这里最主要的一点就是在这个时候如果又找到下一个点
    那么之前book中存的不还是生效嘛 所以在每次调用自身之后要将book数组中对应位置清0这步骤很关键
    这样到下一个访问方案时才能够继续 按照之前的步骤 只要第一行遍历结束后整个过程就结束了,此时也会得到最小距离min


      推荐  啊哈,算法   这本书,真的很好   可以一起谈论交流  加群呀:891507813
    
    展开全文
  • 我们把曲线切割成直线,那么两两的最短距离就是那些直角边画出来的集合,因此,我们可以通过比较这些集合,求出相关的距离。可是,这在百度地图中,却不是最好的方案。 解决方案 将问题简单化,百度地图的曲线可以...

    前言

    首先,我们都知道,点和直线最短的距离就是点到直线的垂直距离。我们用直角三角板的直角边,画出的直线即为所求,那么,曲线呢?

    问题转化

    我们把曲线切割成直线,那么两两的最短距离就是那些直角边画出来的集合,因此,我们可以通过比较这些集合,求出相关的距离。可是,这在百度地图中,却不是最好的方案。

    解决方案

    将问题简单化,百度地图的曲线可以看成按某种精度连接起来的点集,我们可以通过求球体比较两点之间的距离公式,简单算出他们最短距离。
    下面是求两点间的最短距离公式:

    假设两点的坐标分别为A(x1,y1),B(x2,y2),圆的半径为r
    AB=\sqrt{[(x1-x2)^2+(y1-y2)^2]}
    圆心角为θ
    那么sin(\theta /2)=(AB/2)/r=\sqrt{[(x1-x2)^2+(y1-y2)^2]/(2r)}
    所以

    展开全文
  • 本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考,具体如下: 这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容,这里要做的是Dijkstra算法,与Floyd...
  • 最短距离

    2015-07-04 14:11:09
    目前网络电子地图的使用很普遍。利用电子地图可以很方便地确定从一个地点到另一个地点的路径。特别地,可确定在城市中的公交...你的任务:对给定的一个(无向)图G,及G中的两点s、t,计算从起点s到顶点t的最短距离
  • 821. 字符的最短距离给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。示例 1:输入: S = “loveleetcode”, C = ‘e’输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2...
  • 地图上找到从起始节点到结束节点的最短路径和距离** 2. 找出地图上从起始节点到所有其他节点的最短路径和距离** **地图应由节点和段组成,例如: 1.节点的格式为[ID XY]或[ID XYZ](ID为整数,X,Y,Z代表位置坐标...
  • 题目要求参考下图完成游戏地图中从起点到目标点的最短路径寻找问题。二.设计思路先对游戏地图做了几个设定,以矩阵来模拟游戏地图。将可行的区域位置赋值0,障碍区赋值为inf。考虑到地图大小,将起始点和终点区域...
  • 计算点到线段的最短距离

    热门讨论 2013-04-09 17:42:49
    这个计算点到线段最短距离算法是先计算线段距离点最近的点,然后求出 2...在计算用户到当前位置到某条公路的最短距离等实际情况中,可以先用这个算法,然后根据结果坐标使用 CLLocation 类的函数计算实际距离 VC6工程
  • 我试图构造一个for循环,但它没有返回最短距离(分钟) lst=[] for stopLat in stations['lat']: for stopLon in stations['lon']: for propLat in properties['lat']: for propLon in properties['lon']: lst....
  • 我试图用Dijkstra算法在真实地图上找到两个点之间的最短路径,但是在有限的时间内(120秒)我无法得到结果。如何优化我的代码?我只允许用“枕头”作为外包装。在在map有两个红点(33193)(749457),我想画出它们中...
  • 最近因为工作的需求,需要计算出高德地图中两个坐标的距离,通过查找相关资料发现了多种实现的方法,下面这篇文章主要给大家介绍了关于利用java、js或mysql计算高德地图中两坐标之间距离的相关资料,文中通过示例...
  • 提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间...
  • 找指定两坐标间的最短距离 这一类 找两点间最短距离的问题一般是使用BFS来解决。 题目描述 给定一个矩阵,x 为坐标起点,即可以用作出发的地方,T 为终点, 即要到达的地方,那么请给出 从 X 出发能到达 T 的最短的...
  • 所谓的最短路径,顾名思义就是带权值的图中,求一个结点到另一个结点的路径最小。Dijkstra算法1.介绍迪杰斯特拉(Dijkstra)算法是典型的最短路径算法,用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点...
  • * 表面同一经线圈相差1"两点间的距离为 2πR/360/3600 * 表面同一纬线圈相差1"两点间的距离为 2πR×cos(纬度)/360/3600 * 当R取半径平均值6371km时, * 地球表面同一经线圈相差1"两点间的距离约为...
  • ArcGIS计算城市间最短距离(多元最短路径)

    千次阅读 多人点赞 2020-07-27 19:52:24
    步骤2.1 截取湖北省数据2.1.1 新建地图(多源最短路径-湖北)2.1.2 内容列表窗口>>图层>>右键>>添加数据, 再全国行政区划分中导入省和市的矢量图2.1.3 对图层中的省点击右键>>打开属性表...
  • 判断几种特殊情况,点为多边形顶点,点在多边形边上,射线与多边形交点是多边形的顶点(多边形的每一个顶点其实是相邻两条线段的端点,所以顶点可以算两个点) /** * 给定点和多边形,判断给定的点是否在多边形...
  • (3)依次向S中加入v0 ,v1… vn-1,每加入一个顶点,对dist[i][j]进行一次修正:设S={v0 ,v1…vk-1},加入vk,则dist(k)[i...dist(k)[i][j]的含义:允许中间顶点的序号最大为k时从vi到vj的最短路径长度。dist(n-1)[i][...
  • 最短距离和人流量

    2019-07-29 11:12:36
    最短距离和人流量 题目: 作为一个城市(城市标号从1开始)的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。 每条道路都有着距离和人流量 二个指标。人流量...
  • 含有各种障碍物的,水平面两点间最短距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是Dijkstra!不是Floyd!
  • """找最短路径需要使用广度优先搜索有一个 5 * 4 的二维数组代表地图,如下所示。1代表路障,0代表可以通过,请计算从位置(Xs, Ys)到位置(Xd, Yd)的最短步数。0 0 1 00 0 0 00 0 1 00 1 0 00 0 0 1"""import queue ...
  • ###Pathfinding Challenge ###Introduction 此应用程序挑战用户提出最短路径,该路径将通过由一系列可点击点组成的地图上每个组中的至少一个点。 这个概念的灵感来自于数学问题中的旅行商类别,其中只有通过计算每条...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,653
精华内容 4,261
关键字:

地图上最短距离