弧路徑演算法

❶ 求二維平面中兩弧線最小距離的演算法

第一步:連接兩圓心,如果和兩個弧均有交點,則最近距離點即為兩交點間距離,問題結束,否則下一步
第二步:用弧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，半圓既不是劣弧也不是優弧，它是區分劣弧和優弧的一個界限。

構造圓弧

圓在幾何圖形中可以說是一種非常常用的圖形，通過圓能夠衍生出很多曲線問題，圓弧就是最簡單的一種，我們用幾何畫板圓工具可以很輕易地作出圓，也可以利用幾何畫板構造圓上的弧，即構造圓弧。