弧路径算法

❶ 求二维平面中两弧线最小距离的算法

第一步:连接两圆心,如果和两个弧均有交点,则最近距离点即为两交点间距离,问题结束,否则下一步
第二步:用弧1的圆心与弧2中的两个端点相连,选取较短的那条连线,看这条线是否与弧1有交点,如果有,则最短距离为交点与端点的距离,问题结束.如果无,则用弧2的圆心与弧1的两个端点相连,类似上述的步骤进行操作.上述操作后均不存在交点,则下一步
第三步:连接弧1的端点与弧2的端点,产生四条连线,选出这四条线中最短的一条

❷ 路径分析的最优路径分析方法

1．道路预处理
进行道路数据录入时，往往在道路的交叉接合处出现重叠或相离的情况，不宜计算机处理。因此，需要对原始数据进行预处理，使道路接合符合处理要求。进行预处理时，取每条线段的首末节点坐标为圆心，以给定的阈值为半径作圆域，判断其他线段是否与圆域相交，如果相交，则相交的各个线对象共用一个节点号。
2．道路自动断链
对道路进行预处理之后即可获得比较理想的数据，在此基础上再进行道路的自动断链。步骤如下：
（1）取出所有线段记录数n，从第一条线段开始；
（2）找出所有与之相交的线段并求出交点数m；
（3）将m个交点和该线段节点在判断无重合后进行排序；
（4）根据交点数量，该线段被分成m+1段；
（5）第一段在原始位置不变，后m段从记录尾开始递增；
（6）重复（2）～（5），循环至n。
3．节点匹配
拓扑关系需使用统一的节点。节点匹配方法是按记录顺序将所有线段的始末点加上相应节点号，坐标相同的节点共用一个节点号，与前面所有线段首末点都不相同的节点按自然顺序递增1。
4．迪杰克斯特拉（Dijkstra）算法
经典的图论与计算机算法的有效结合，使得新的最短路径算法不断涌现。目前提出的最短路径算法中，使用最多、计算速度比较快，又比较适合于计算两点之间的最短路径问题的数学模型就是经典的Dijkstra算法。
该算法是典型的单源最短路径算法，由Dijkstra EW于1959年提出，适用于所有弧的权均为非负的情况，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法的基本思想是：认为两节点间最佳路径要么是直接相连，要么是通过其他已找到的与起始点的最佳路径的节点中转点。定出起始点P0后，定能找出一个与之直接相连且路径长度最短的节点，设为P1，P0到P1就是它们间的最佳路径。
Dijkstra算法的基本流程如下：首先将网络中所有节点分成两组，一组包含了已经确定属于最短路径中点的集合，记为S（该集合在初始状态只有一个源节点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；另一组是尚未确定最短路径的节点的集合，记为V，按照最短路径长度递增的次序依次把第二组的顶点加入到第一组中，在加入的过程中总保持从源点到S中各顶点的最短路径长度不大于从源点到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从源点到此顶点的最短路径长度，V中的顶点距离是从源点到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

❸ 数据结构中弧和路径的区别

如果n个顶点形成一个有向环，这时候图为强连通有向图，但不会出现任何顶点到其他所有顶点都有弧

❹ 弧的计算公式

您好！
你的“98CM”是弧长？应该是弦长吧。
就你的问题来算，我当你的“37CM”是直径时它的周长已是：116.24CM，大于你的“98CM”
我当你的“98CM”是弦长来算，则有：
设：
弦长C=98CM
弧弓高h=37CM
求-弧半径R
公式：R=（C*C+4h*h）/8h
R=（98*98+4*37*37）/8*37
=50.95CM
画弧半径约为50.95CM

❺ 圆弧路径的三点的意义

运用“三点法”求解动点路径长问题，一般有两种情况:线段或圆弧，求动点路径长的方法三点法，“三点”指动点的起点，终点与过程点。
“三点法”分为三步:精准作图，运用刻度尺，圆规及量角器等工具作出位置较为精准的“三点”；大胆猜测，若“三点”共线，则动点路径为线段;若“三点”不共线，则动点路径为圆弧；小心验证，根据画出的“三点图”，运用相似三角形、“定角定长定圆”等方法对猜想进行严格的证明。
三点圆弧就是用三个点能形成一段圆弧，且三点不能在一条线上。

❻ 关于时间依赖的最短路径算法

Dijkstra 最短路径算法的一种高效率实现*

随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s～3 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计，目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，这些算法的具体内容可以参见文献〔1〕。其中TQQ算法的基础是图增长理论，较适合于计算单源点到其他所有点间的最短距离；后两种算法则是基于Dijkstra的算法，更适合于计算两点间的最短路径问题〔1〕。总体来说，这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的效率。
1 经典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi= ;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min〔dj, dk+lkj〕
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min〔dj, 所有未标记的点j〕
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
2 已有的Dijkstra算法的实现
从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。
网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表〔4〕 表示，其优缺点的比较见表 1。
表 1 几种图的存储结构的比较
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 称 实现方法 优 点 缺 点 时间复杂度
邻接矩阵 二维数组 1. 易判断两点间的关系 占用空间大 O(n2+m*n)
2. 容易求得顶点的度
邻接表 链表 1. 节省空间 1. 不易判断两点间的关系 O(n+m)或O(n*m)
2. 易得到顶点的出度 2. 不易得到顶点的入度
十字链表 链表 1. 空间要求较小 结构较复杂 同邻接表
2.易求得顶点的出度和入度
邻接多重表 链表 1. 节省空间 结构较复杂 同邻接表
2. 易判断两点间的关系

目前,对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA 以及 DKD 在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程〔1〕。
DKA和DKD是采用如图 1 所示的桶结构来支持这个运算，其算法的命名也来源于此。在DKA算法中，第i个桶内装有权值落在 〔b*i, (i+1)*b) 范围内的可供扫描的点，其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点有可能被多次扫描，但最多次数不会超过b次。最坏情况下，DKA的时间复杂度将会是O(m*b+n(b+C/b))，其中，C为图中边的最大权值。DKD将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点。当然随着点的插入和删除，两个桶内的点是需要动态调整的。在DKA算法中，给每个桶一定的范围以及DKD中使用双桶，在一定程度上都是以空间换时间的做法，需要改进。

图 1 一个桶结构的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra算法实现
3.1 网络拓扑关系的建立
上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、带权、出度、入度等。而GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。综合以上4种存储结构的优缺点， 笔者采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Net-Arc List），另一个则存储和顶点相关的数据（Net-Node Index）。Net-Arc List用一个数组维护并且以以弧段起点的点号来顺序排列，同一起点的弧段可以任意排序。这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示。Net-Node Index则相当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置。此外，属性数据作为GIS不可少的一部分也是必须记录的。这样，计算最佳路径所需的网络信息已经完备了。在顶点已编号的情况下，建立Net-Arc List和Net-Node Index两个表以及对Net-Arc List的排序，其时间复杂度共为O(2n+lgn)，否则为O(m+2n+lgn)。这个结构所需的空间也是必要条件下最小的，记录了m个顶点以及n条边的相关信息，与邻接多重表是相同的。图 2 是采用这个结构的示意图。
3.2 快速搜索技术的实现
无论何种算法，一个基本思想都是将点按权值的大小顺序排列，以节省操作时间。前面已经提到过，这两个算法都是以时间换空间的算法，所以在这里有必要讨论存储空间问题 (这部分空间的大小依赖于点的个数及其出度)。根据图中顶点和边的个数可以求出顶点的平均出度e=m/n（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中，e∈〔2,5〕。这样,如果当前永久标记的点为t个，那么，下一步需扫描点的个数就约为t～4t个。如果采用链表结构，按实际应用中的网络规模大小，所需的总存储空间一般不会超过100 K。所以完全没有必要采用以时间换空间的做法，相反以空间换时间的做法是完全可行的。在实现这部分时，笔者采用了一个FIFO队列，相应的操作主要是插入、排序和删除，插入和删除的时间复杂度都是O(1)，所以关键问题在于选择一个合适的排序算法。一般可供选择的排序算法有快速排序、堆排序以及归并排序等，其实现的平均时间都为O(nlgn)。经过比较实验，笔者选择了快速排序法。另外，Visual C++提供的run-time库也提供了现成的快速排序的函数qsort( )可供使用。

图 2 基于最佳路径计算的网络拓扑表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，笔者用Visual C++实现了吉奥之星（GeoStar）中的最佳路径模块。以北京的街道为数据（共6 313个结点，9 214条弧段(双向)），在主频为133、硬盘为1 G、内存为32 M的机器上，计算一条贯穿全城、长为155.06 km的线路，约需1 s～2 s。如图 3所示。

图 3 GeoStar中最佳路径实现示意图

ps:图片没有办法贴上去.
你可以参考《算法导论》第二版

❼ 数据结构中弧和路径的区别

这两个概念差太远了吧?

• 弧：指的是有向图里面的边，他是有明确方向的。如果是无向图的边，直接叫做“边”。比如有向图的 v1 结点到 v2 结点的弧可能是：<v1, v2>；

• 路径：指的是图（包括有向图和无向图）里面连接两个结点之间的边的集合，也就是一个顶点序列。比如：v1 到 v3 的路径可能这样表示：<v1, v2>、<v2, v3>；

可见，如果是有向图，那么路径里面是用弧来组成。

如果是无向图，路径是用边来组成。

❽ 圆弧的算法

弧长公式L=|a|*r，a是圆心角（弧度制）r是半径 追问： 没懂 回答： 还有种算法是：n°的圆心角所对的弧长的计算公式是L＝n*2πR/360 其实就是圆心角的弧度乘以半径就行了 追问： 弧度是圆心角吗？ 回答： 弧度制学了没？就是圆心角的弧度 弧度就是角度除以180° 追问： 如果圆心角是90度那么弧度数是多少？ 回答： 抱歉前面的说法有错， 弧度是角度除以180°再乘以π 所以90°=π/2 180°=π 45°=π/4 追问： 谢谢我懂了

满意请采纳

❾ d3.js画圆弧和圆的坐标、弧长计算方法

svg路径画圆的特性：(rx ry x-axis-rotation large-arc-flag sweep-flag x y)。
rx，ry: 是椭圆的两个半轴的长度。
x-axis-rotation: 是椭圆相对于坐标系的旋转角度，角度数而非弧度数。
large-arc-flag: 是标记绘制大弧(1)还是小弧(0)部分。
sweep-flag: 是标记向顺时针(1)还是逆时针(0)方向绘制。
x，y: 是圆弧终点的坐标。

已知两点和半径求弧路径。

已知圆上两点和半径求弧长。

已知圆上的y轴半径和圆心求相交的x轴坐标。

已知圆上的x轴半径和圆心求y轴坐标。

❿ 圆弧的计算公式

圆弧的计算公式如下 ：

（1）圆弧的弧长：

(10)弧路径算法扩展阅读：

圆上任意两点间的部分叫做圆弧，简称弧。初、高中数学课有教学。圆的任意一条直径的两个端点把圆分成两条弧，大于半圆叫优弧，小于半圆叫劣弧。

弧用符号“⌒”表示。例如，以A、B为端点的圆弧读做圆弧AB或弧AB。大于半圆的弧叫优弧，小于半圆的弧叫劣弧。圆弧的度数是指这段圆弧所对圆心角的度数。

半圆也是弧，连接AB两点的直线是弦AB，半圆既不是劣弧也不是优弧，它是区分劣弧和优弧的一个界限。

构造圆弧

圆在几何图形中可以说是一种非常常用的图形，通过圆能够衍生出很多曲线问题，圆弧就是最简单的一种，我们用几何画板圆工具可以很轻易地作出圆，也可以利用几何画板构造圆上的弧，即构造圆弧。