用戶:Ab3080888/數學沙盒
排隊論(英語:Queueing theory)是一門研究等待現象的數學理論。[1] 它通過建立數學模型來預測排隊長度和等待時間。[1] 由於其研究成果對服務資源配置的決策具有重要指導意義,排隊論已成為運籌學中的重要分支學科。
這門學科可以追溯到阿格納·克拉魯普·厄蘭的開創性研究。他最初為解決哥本哈根電話交換公司的來電問題建立了理論模型。[1] 這些理論不僅為電信流量工程奠定了基礎,還逐步拓展到電信、交通、計算機[2]、項目管理等眾多領域。目前,排隊論在工業工程領域應用尤為廣泛,已成為工廠、商店、辦公室和醫院等場所規劃設計的重要工具。[3][4]
描述
排隊論是管理科學領域中的重要研究方向之一。管理科學為企業提供了多種科學和數學方法來解決各類問題。[5] 排隊分析主要研究等待隊列的概率特性,因此其分析結果(即運行特徵)具有概率性而非確定性。這些運行特徵包括:系統內顧客數量的概率分佈、系統內平均顧客數、隊列中平均等待人數、顧客在系統內的平均停留時間、顧客的平均等待時間,以及服務台忙碌或空閒的概率等。[5] 排隊分析的核心目標是通過計算現有系統的這些特徵,並測試各種可能的改進方案。通過對比當前系統與替代方案的運行特徵,管理者可以清晰地評估每個方案的利弊得失。這些分析能夠幫助管理者做出最終決策,實現成本節約、縮短等待時間、提升效率等目標。常用的排隊模型主要包括單服務台和多服務台兩種基本類型,具體會在後文詳細討論。這些模型還可以根據服務時間是否固定、隊列長度是否受限、源群體是否有限等因素進行細分。[5]
單排隊節點
排隊系統可以簡單理解為一個近似的黑盒模型。任務(在不同場景中也稱為顧客或請求)進入系統後,可能需要等待,接受處理,最後離開系統。
不過,這個系統並不是一個完全的黑盒,因為我們需要了解它的一些內部運作機制。系統中設有一個或多個服務窗口(server),每個窗口都可以受理一個新到達的任務。當某個任務處理完畢離開後,對應的服務窗口就能繼續接待下一個任務。
舉個常見的例子:超市收銀台就是一個典型的排隊系統(雖然還有其他例子,但這個是文獻中最常用的)。顧客來到超市,在收銀台辦理結賬,然後離開。由於每個收銀員同一時間只能服務一位顧客,所以這是一個單服務窗口的排隊系統。如果規定顧客看到收銀員正忙就直接離開,這種情況就是無等待空間的排隊系統;如果設置了可容納 n 位顧客的等候區,則稱為具有 n 個等待空間的排隊系統。
出生-死亡過程
單個隊列(也稱為排隊節點)的行為可以用出生-死亡過程來描述。該過程刻畫了隊列中任務的到達和離開動態,以及系統中實時的任務數量。如果用 k 表示系統中的任務數量(包括正在處理的和在緩衝區等待的),那麼每當有新任務到達時 k 值加1,任務完成離開時 k 值減1。
系統通過「出生」和「死亡」兩種事件在不同的 k 值之間轉換。對於每個任務,這些轉換分別以到達率和離開率發生。在隊列系統中,這些速率通常被認為是穩定的,不會隨隊列中任務數量的變化而改變,因此我們可以採用單位時間內的平均到達率和離開率。基於這一假設,該過程的平均到達率,平均離開率。
Balance equations
The steady state equations for the birth-and-death process, known as the balance equations, are as follows. Here denotes the steady state probability to be in state n.
The first two equations imply
and
- .
By mathematical induction,
- .
The condition leads to
which, together with the equation for , fully describes the required steady state probabilities.
Kendall's notation
Single queueing nodes are usually described using Kendall's notation in the form A/S/c where A describes the distribution of durations between each arrival to the queue, S the distribution of service times for jobs, and c the number of servers at the node.[6][7] For an example of the notation, the M/M/1 queue is a simple model where a single server serves jobs that arrive according to a Poisson process (where inter-arrival durations are exponentially distributed) and have exponentially distributed service times (the M denotes a Markov process). In an M/G/1 queue, the G stands for "general" and indicates an arbitrary probability distribution for service times.
Example analysis of an M/M/1 queue
Consider a queue with one server and the following characteristics:
- : the arrival rate (the reciprocal of the expected time between each customer arriving, e.g. 10 customers per second)
- : the reciprocal of the mean service time (the expected number of consecutive service completions per the same unit time, e.g. per 30 seconds)
- n: the parameter characterizing the number of customers in the system
- : the probability of there being n customers in the system in steady state
Further, let represent the number of times the system enters state n, and represent the number of times the system leaves state n. Then for all n. That is, the number of times the system leaves a state differs by at most 1 from the number of times it enters that state, since it will either return into that state at some time in the future () or not ().
When the system arrives at a steady state, the arrival rate should be equal to the departure rate.
Thus the balance equations
imply
The fact that leads to the geometric distribution formula
where .
Simple two-equation queue
A common basic queueing system is attributed to Erlang and is a modification of Little's Law. Given an arrival rate λ, a dropout rate σ, and a departure rate μ, length of the queue L is defined as:
- .
Assuming an exponential distribution for the rates, the waiting time W can be defined as the proportion of arrivals that are served. This is equal to the exponential survival rate of those who do not drop out over the waiting period, giving:
The second equation is commonly rewritten as:
The two-stage one-box model is common in epidemiology.[8]
History
In 1909, Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on what would now be called queueing theory.[9][10][11] He modeled the number of telephone calls arriving at an exchange by a Poisson process and solved the M/D/1 queue in 1917 and M/D/k queueing model in 1920.[12] In Kendall's notation:
- M stands for "Markov" or "memoryless", and means arrivals occur according to a Poisson process
- D stands for "deterministic", and means jobs arriving at the queue require a fixed amount of service
- k describes the number of servers at the queueing node (k = 1, 2, 3, ...)
If the node has more jobs than servers, then jobs will queue and wait for service.
The M/G/1 queue was solved by Felix Pollaczek in 1930,[13] a solution later recast in probabilistic terms by Aleksandr Khinchin and now known as the Pollaczek–Khinchine formula.[12][14]
After the 1940s, queueing theory became an area of research interest to mathematicians.[14] In 1953, David George Kendall solved the GI/M/k queue[15] and introduced the modern notation for queues, now known as Kendall's notation. In 1957, Pollaczek studied the GI/G/1 using an integral equation.[16] John Kingman gave a formula for the mean waiting time in a G/G/1 queue, now known as Kingman's formula.[17]
Leonard Kleinrock worked on the application of queueing theory to message switching in the early 1960s and packet switching in the early 1970s. His initial contribution to this field was his doctoral thesis at the Massachusetts Institute of Technology in 1962, published in book form in 1964. His theoretical work published in the early 1970s underpinned the use of packet switching in the ARPANET, a forerunner to the Internet.
The matrix geometric method and matrix analytic methods have allowed queues with phase-type distributed inter-arrival and service time distributions to be considered.[18]
Systems with coupled orbits are an important part in queueing theory in the application to wireless networks and signal processing.[19]
Modern day application of queueing theory concerns among other things product development where (material) products have a spatiotemporal existence, in the sense that products have a certain volume and a certain duration.[20]
Problems such as performance metrics for the M/G/k queue remain an open problem.[12][14]
Service disciplines
Various scheduling policies can be used at queueing nodes:
- First in, first out
- Also called first-come, first-served (FCFS),[21] this principle states that customers are served one at a time and that the customer that has been waiting the longest is served first.[22]
- Last in, first out
- This principle also serves customers one at a time, but the customer with the shortest waiting time will be served first.[22] Also known as a stack.
- Processor sharing
- Service capacity is shared equally between customers.[22]
- Priority
- Customers with high priority are served first.[22] Priority queues can be of two types: non-preemptive (where a job in service cannot be interrupted) and preemptive (where a job in service can be interrupted by a higher-priority job). No work is lost in either model.[23]
- Shortest job first
- The next job to be served is the one with the smallest size.[24]
- Preemptive shortest job first
- The next job to be served is the one with the smallest original size.[25]
- Shortest remaining processing time
- The next job to serve is the one with the smallest remaining processing requirement.[26]
- Service facility
- Single server: customers line up and there is only one server
- Several parallel servers (single queue): customers line up and there are several servers
- Several parallel servers (several queues): there are many counters and customers can decide for which to queue
- Unreliable server
Server failures occur according to a stochastic (random) process (usually Poisson) and are followed by setup periods during which the server is unavailable. The interrupted customer remains in the service area until server is fixed.[27]
- Customer waiting behavior
- Balking: customers decide not to join the queue if it is too long
- Jockeying: customers switch between queues if they think they will get served faster by doing so
- Reneging: customers leave the queue if they have waited too long for service
Arriving customers not served (either due to the queue having no buffer, or due to balking or reneging by the customer) are also known as dropouts. The average rate of dropouts is a significant parameter describing a queue.
排隊網絡
Queue networks are systems in which multiple queues are connected by customer routing. When a customer is serviced at one node, it can join another node and queue for service, or leave the network.
For networks of m nodes, the state of the system can be described by an m–dimensional vector (x1, x2, ..., xm) where xi represents the number of customers at each node.
The simplest non-trivial networks of queues are called tandem queues.[28] The first significant results in this area were Jackson networks,[29][30] for which an efficient product-form stationary distribution exists and the mean value analysis[31] (which allows average metrics such as throughput and sojourn times) can be computed.[32] If the total number of customers in the network remains constant, the network is called a closed network and has been shown to also have a product–form stationary distribution by the Gordon–Newell theorem.[33] This result was extended to the BCMP network,[34] where a network with very general service time, regimes, and customer routing is shown to also exhibit a product–form stationary distribution. The normalizing constant can be calculated with the Buzen's algorithm, proposed in 1973.[35]
Networks of customers have also been investigated, such as Kelly networks, where customers of different classes experience different priority levels at different service nodes.[36] Another type of network are G-networks, first proposed by Erol Gelenbe in 1993:[37] these networks do not assume exponential time distributions like the classic Jackson network.
Routing algorithms
In discrete-time networks where there is a constraint on which service nodes can be active at any time, the max-weight scheduling algorithm chooses a service policy to give optimal throughput in the case that each job visits only a single-person service node.[21] In the more general case where jobs can visit more than one node, backpressure routing gives optimal throughput. A network scheduler must choose a queueing algorithm, which affects the characteristics of the larger network.[38]
Mean-field limits
Mean-field models consider the limiting behaviour of the empirical measure (proportion of queues in different states) as the number of queues m approaches infinity. The impact of other queues on any given queue in the network is approximated by a differential equation. The deterministic model converges to the same stationary distribution as the original model.[39]
Heavy traffic/diffusion approximations
In a system with high occupancy rates (utilisation near 1), a heavy traffic approximation can be used to approximate the queueing length process by a reflected Brownian motion,[40] Ornstein–Uhlenbeck process, or more general diffusion process.[41] The number of dimensions of the Brownian process is equal to the number of queueing nodes, with the diffusion restricted to the non-negative orthant.
Fluid limits
Fluid models are continuous deterministic analogs of queueing networks obtained by taking the limit when the process is scaled in time and space, allowing heterogeneous objects. This scaled trajectory converges to a deterministic equation which allows the stability of the system to be proven. It is known that a queueing network can be stable but have an unstable fluid limit.[42]
Queueing Applications
Queueing theory finds widespread application in computer science and information technology. In networking, for instance, queues are integral to routers and switches, where packets queue up for transmission. By applying queueing theory principles, designers can optimize these systems, ensuring responsive performance and efficient resource utilization. Beyond the technological realm, queueing theory is relevant to everyday experiences. Whether waiting in line at a supermarket or for public transportation, understanding the principles of queueing theory provides valuable insights into optimizing these systems for enhanced user satisfaction. At some point, everyone will be involved in an aspect of queuing. What some may view to be an inconvenience could possibly be the most effective method. Queueing theory, a discipline rooted in applied mathematics and computer science, is a field dedicated to the study and analysis of queues, or waiting lines, and their implications across a diverse range of applications. This theoretical framework has proven instrumental in understanding and optimizing the efficiency of systems characterized by the presence of queues. The study of queues is essential in contexts such as traffic systems, computer networks, telecommunications, and service operations. Queueing theory delves into various foundational concepts, with the arrival process and service process being central. The arrival process describes the manner in which entities join the queue over time, often modeled using stochastic processes like Poisson processes. The efficiency of queueing systems is gauged through key performance metrics. These include the average queue length, average wait time, and system throughput. These metrics provide insights into the system's functionality, guiding decisions aimed at enhancing performance and reducing wait times. References: Gross, D., & Harris, C. M. (1998). Fundamentals of Queueing Theory. John Wiley & Sons. Kleinrock, L. (1976). Queueing Systems: Volume I - Theory. Wiley. Cooper, B. F., & Mitrani, I. (1985). Queueing Networks: A Fundamental Approach. John Wiley & Sons
See also
References
- ^ 1.0 1.1 1.2 Sundarapandian, V. 7. Queueing Theory. Probability, Statistics and Queueing Theory. PHI Learning. 2009. ISBN 978-81-203-3844-9.
- ^ Lawrence W. Dowdy, Virgilio A.F. Almeida, Daniel A. Menasce. Performance by Design: Computer Capacity Planning by Example. [2009-07-08]. (原始內容存檔於2016-05-06).
- ^ Schlechter, Kira. Hershey Medical Center to open redesigned emergency room. The Patriot-News. March 2, 2009 [March 12, 2009]. (原始內容存檔於June 29, 2016).
- ^ Mayhew, Les; Smith, David. Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target. Cass Business School. December 2006 [2008-05-20]. ISBN 978-1-905752-06-5. (原始內容存檔於September 7, 2021).
- ^ 5.0 5.1 5.2 Taylor, Bernard W. Introduction to management science 13th. New York: Pearson. 2019. ISBN 978-0-13-473066-0.
- ^ Tijms, H.C, Algorithmic Analysis of Queues, Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003
- ^ Kendall, D. G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain. The Annals of Mathematical Statistics. 1953, 24 (3): 338–354. JSTOR 2236285. doi:10.1214/aoms/1177728975 .
- ^ Hernández-Suarez, Carlos. An application of queuing theory to SIS and SEIS epidemic models. Math. Biosci. 2010, 7 (4): 809–823. PMID 21077709. doi:10.3934/mbe.2010.7.809 .
- ^ Agner Krarup Erlang (1878-1929) | plus.maths.org. Pass.maths.org.uk. 1997-04-30 [2013-04-22]. (原始內容存檔於2008-10-07).
- ^ Asmussen, S. R.; Boxma, O. J. Editorial introduction. Queueing Systems. 2009, 63 (1–4): 1–2. S2CID 45664707. doi:10.1007/s11134-009-9151-8.
- ^ Erlang, Agner Krarup. The theory of probabilities and telephone conversations (PDF). Nyt Tidsskrift for Matematik B. 1909, 20: 33–39. (原始內容 (PDF)存檔於2011-10-01).
- ^ 12.0 12.1 12.2 Kingman, J. F. C. The first Erlang century—and the next. Queueing Systems. 2009, 63 (1–4): 3–4. S2CID 38588726. doi:10.1007/s11134-009-9147-4.
- ^ Pollaczek, F., Ueber eine Aufgabe der Wahrscheinlichkeitstheorie, Math. Z. 1930
- ^ 14.0 14.1 14.2 Whittle, P. Applied Probability in Great Britain. Operations Research. 2002, 50 (1): 227–239. JSTOR 3088474. doi:10.1287/opre.50.1.227.17792 .
- ^ Kendall, D.G.:Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain, Ann. Math. Stat. 1953
- ^ Pollaczek, F., Problèmes Stochastiques posés par le phénomène de formation d'une queue
- ^ Kingman, J. F. C.; Atiyah. The single server queue in heavy traffic. Mathematical Proceedings of the Cambridge Philosophical Society. October 1961, 57 (4): 902. Bibcode:1961PCPS...57..902K. JSTOR 2984229. S2CID 62590290. doi:10.1017/S0305004100036094.
- ^ Ramaswami, V. A stable recursion for the steady state vector in markov chains of m/g/1 type. Communications in Statistics. Stochastic Models. 1988, 4: 183–188. doi:10.1080/15326348808807077.
- ^ Morozov, E. Stability analysis of a multiclass retrial system withcoupled orbit queues. Proceedings of 14th European Workshop. Lecture Notes in Computer Science 17. 2017: 85–98. ISBN 978-3-319-66582-5. doi:10.1007/978-3-319-66583-2_6 .
- ^ Carlson, E.C.; Felder, R.M. Simulation and queueing network modeling of single-product production campaigns. Computers & Chemical Engineering. 1992, 16 (7): 707–718. doi:10.1016/0098-1354(92)80018-5.
- ^ 21.0 21.1 Manuel, Laguna. Business Process Modeling, Simulation and Design. Pearson Education India. 2011: 178 [6 October 2017]. ISBN 978-81-317-6135-9 (英語).
- ^ 22.0 22.1 22.2 22.3 Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.
- ^ Harchol-Balter, M. Scheduling: Non-Preemptive, Size-Based Policies. Performance Modeling and Design of Computer Systems. 2012: 499–507. ISBN 978-1-139-22642-4. doi:10.1017/CBO9781139226424.039.
- ^ Andrew S. Tanenbaum; Herbert Bos. Modern Operating Systems. Pearson. 2015. ISBN 978-0-13-359162-0.
- ^ Harchol-Balter, M. Scheduling: Preemptive, Size-Based Policies. Performance Modeling and Design of Computer Systems. 2012: 508–517. ISBN 978-1-139-22642-4. doi:10.1017/CBO9781139226424.040.
- ^ Harchol-Balter, M. Scheduling: SRPT and Fairness. Performance Modeling and Design of Computer Systems. 2012: 518–530. ISBN 978-1-139-22642-4. doi:10.1017/CBO9781139226424.041.
- ^ Dimitriou, I. A Multiclass Retrial System With Coupled Orbits And Service Interruptions: Verification of Stability Conditions. Proceedings of FRUCT 24. 2019, 7: 75–82.
- ^ Archived copy (PDF). [2018-08-02]. (原始內容存檔 (PDF)於2017-03-29).
- ^ Jackson, J. R. Networks of Waiting Lines. Operations Research. 1957, 5 (4): 518–521. JSTOR 167249. doi:10.1287/opre.5.4.518.
- ^ Jackson, James R. Jobshop-like Queueing Systems. Management Science. Oct 1963, 10 (1): 131–142. JSTOR 2627213. doi:10.1287/mnsc.1040.0268.
- ^ Reiser, M.; Lavenberg, S. S. Mean-Value Analysis of Closed Multichain Queuing Networks. Journal of the ACM. 1980, 27 (2): 313. S2CID 8694947. doi:10.1145/322186.322195 .
- ^ Van Dijk, N. M. On the arrival theorem for communication networks. Computer Networks and ISDN Systems. 1993, 25 (10): 1135–2013 [2019-09-24]. S2CID 45218280. doi:10.1016/0169-7552(93)90073-D. (原始內容存檔於2019-09-24).
- ^ Gordon, W. J.; Newell, G. F. Closed Queuing Systems with Exponential Servers. Operations Research. 1967, 15 (2): 254. JSTOR 168557. doi:10.1287/opre.15.2.254.
- ^ Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. Open, closed and mixed networks of queues with different classes of customers. Journal of the ACM. 1975, 22 (2): 248–260. S2CID 15204199. doi:10.1145/321879.321887 .
- ^ Buzen, J. P. Computational algorithms for closed queueing networks with exponential servers (PDF). Communications of the ACM. 1973, 16 (9): 527–531 [2015-09-01]. S2CID 10702. doi:10.1145/362342.362345. (原始內容存檔 (PDF)於2016-05-13).
- ^ Kelly, F. P. Networks of Queues with Customers of Different Types. Journal of Applied Probability. 1975, 12 (3): 542–554. JSTOR 3212869. S2CID 51917794. doi:10.2307/3212869.
- ^ Gelenbe, Erol. G-Networks with Triggered Customer Movement. Journal of Applied Probability. Sep 1993, 30 (3): 742–748. JSTOR 3214781. S2CID 121673725. doi:10.2307/3214781.
- ^ Newell, G. F. Applications of Queueing Theory. SpringerLink. 1982. ISBN 978-94-009-5972-9. doi:10.1007/978-94-009-5970-5 (英語).
- ^ Bobbio, A.; Gribaudo, M.; Telek, M. S. Analysis of Large Scale Interacting Systems by Mean Field Method. 2008 Fifth International Conference on Quantitative Evaluation of Systems. 2008: 215. ISBN 978-0-7695-3360-5. S2CID 2714909. doi:10.1109/QEST.2008.47.
- ^ Chen, H.; Whitt, W. Diffusion approximations for open queueing networks with service interruptions. Queueing Systems. 1993, 13 (4): 335. S2CID 1180930. doi:10.1007/BF01149260.
- ^ Yamada, K. Diffusion Approximation for Open State-Dependent Queueing Networks in the Heavy Traffic Situation. The Annals of Applied Probability. 1995, 5 (4): 958–982. JSTOR 2245101. doi:10.1214/aoap/1177004602 .
- ^ Bramson, M. A stable queueing network with unstable fluid model. The Annals of Applied Probability. 1999, 9 (3): 818–853. JSTOR 2667284. doi:10.1214/aoap/1029962815 .
Further reading
- Gross, Donald; Carl M. Harris. Fundamentals of Queueing Theory. Wiley. 1998. ISBN 978-0-471-32812-4. Online
- Zukerman, Moshe. Introduction to Queueing Theory and Stochastic Teletraffic Models (PDF). 2013. arXiv:1307.2968 .
- Deitel, Harvey M. An introduction to operating systems revisited first. Addison-Wesley. 1984: 673. ISBN 978-0-201-14502-1. 已忽略未知參數
|orig-date=
(幫助) chap.15, pp. 380–412 - Gelenbe, Erol; Isi Mitrani. Analysis and Synthesis of Computer Systems. World Scientific 2nd Edition. 2010. ISBN 978-1-908978-42-4.
- Newell, Gordron F. Applications of Queueing Theory. Chapman and Hall. 1 June 1971.
- Leonard Kleinrock, Information Flow in Large Communication Nets, (MIT, Cambridge, May 31, 1961) Proposal for a Ph.D. Thesis
- Leonard Kleinrock. Information Flow in Large Communication Nets (RLE Quarterly Progress Report, July 1961)
- Leonard Kleinrock. Communication Nets: Stochastic Message Flow and Delay (McGraw-Hill, New York, 1964)
- Kleinrock, Leonard. Queueing Systems: Volume I – Theory. New York: Wiley Interscience. 2 January 1975: 417. ISBN 978-0-471-49110-1.
- Kleinrock, Leonard. Queueing Systems: Volume II – Computer Applications. New York: Wiley Interscience. 22 April 1976: 576. ISBN 978-0-471-49111-8.
- Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik. Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall, Inc. 1984. ISBN 978-0-13-746975-8.
- Jon Kleinberg; Éva Tardos. Algorithm Design. Pearson. 30 June 2013. ISBN 978-1-292-02394-6.
External links
- Teknomo's Queueing theory tutorial and calculators
- Virtamo's Queueing Theory Course
- Myron Hlynka's Queueing Theory Page
- LINE: a general-purpose engine to solve queueing models
The study of geodesics on an ellipsoid arose in connection with geodesy specifically with the solution of triangulation networks. The figure of the Earth is well approximated by an oblate ellipsoid, a slightly flattened sphere. A geodesic is the shortest path between two points on a curved surface, i.e., the analogue of a straight line on a plane surface. The solution of a triangulation network on an ellipsoid is therefore a set of exercises in spheroidal trigonometry (Euler 1755).
If the Earth is treated as a sphere, the geodesics are great circles (all of which are closed) and the problems reduce to ones in spherical trigonometry. However, Newton (1687) showed that the effect of the rotation of the Earth results in its resembling a slightly oblate ellipsoid and, in this case, the equator and the meridians are the only closed geodesics. Furthermore, the shortest path between two points on the equator does not necessarily run along the equator. Finally, if the ellipsoid is further perturbed to become a triaxial ellipsoid (with three distinct semi-axes), then only three geodesics are closed and one of these is unstable.
The problems in geodesy are usually reduced to two main cases: the direct problem, given a starting point and an initial heading, find the position after traveling a certain distance along the geodesic; and the inverse problem, given two points on the ellipsoid find the connecting geodesic and hence the shortest distance between them. Because the flattening of the Earth is small, the geodesic distance between two points on the Earth is well approximated by the great-circle distance using the mean Earth radius—the relative error is less than 1%. However, the course of the geodesic can differ dramatically from that of the great circle. As an extreme example, consider two points on the equator with a longitude difference of 179°59′; while the connecting great circle follows the equator, the shortest geodesics pass within 180 km of either pole (the flattening makes two symmetric paths passing close to the poles shorter than the route along the equator).
Aside from their use in geodesy and related fields such as navigation, terrestrial geodesics arise in the study of the propagation of signals which are confined (approximately) to the surface of the Earth, for example, sound waves in the ocean (Munk & Forbes 1989) and the radio signals from lightning (Casper & Bent 1991). Geodesics are used to define some maritime boundaries, which in turn determine the allocation of valuable resources as such oil and mineral rights. Ellipsoidal geodesics also arise in other applications; for example, the propagation of radio waves along the fuselage of an aircraft, which can be roughly modeled as a prolate (elongated) ellipsoid (Kim & Burnside 1986) .
Geodesics are an important intrinsic characteristic of curved surfaces. The sequence of progressively more complex surfaces, the sphere, an ellipsoid of revolution, and a triaxial ellipsoid, provide a useful family of surfaces for investigating the general theory of surfaces. Indeed, Gauss's work on the survey of Hanover, which involved geodesics on an oblate ellipsoid, was a key motivation for his study of surfaces (Gauss 1828). Similarly, the existence of three closed geodesics on a triaxial ellipsoid turns out to be a general property of closed, simply connected surfaces; this was conjectured by Poincaré (1905) and proved by Lyusternik & Schnirelmann (1929) (Klingenberg 1982,§3.7).
Geodesics on an ellipsoid of revolution
There are several ways of defining geodesics (Hilbert & Cohn-Vossen 1952,第220–221頁). A simple definition is as the shortest path between two points on a surface. However, it is frequently more useful to define them as paths with zero geodesic curvature—i.e., the analogue of straight lines on a curved surface. This definition encompasses geodesics traveling so far across the ellipsoid's surface (somewhat less than half the circumference) that other distinct routes require less distance. Locally, these geodesics are still identical to the shortest distance between two points.
By the end of the 18th century, an ellipsoid of revolution (the term spheroid is also used) was a well-accepted approximation to the figure of the Earth. The adjustment of triangulation networks entailed reducing all the measurements to a reference ellipsoid and solving the resulting two-dimensional problem as an exercise in spheroidal trigonometry (Bomford 1952,Chap. 3).
It is possible to reduce the various geodesic problems into one of two types. Consider two points: A at latitude φ1 and longitude λ1 and B at latitude φ2 and longitude λ2 (see Fig. 1). The connecting geodesic (from A to B) is AB, of length s12, which has azimuths α1 and α2 at the two endpoints.[1] The two geodesic problems usually considered are:
- the direct geodesic problem or first geodesic problem, given A, α1, and s12, determine B and α2;
- the inverse geodesic problem or second geodesic problem, given A and B, determine s12, α1, and α2.
As can be seen from Fig. 1, these problems involve solving the triangle NAB given one angle, α1 for the direct problem and λ12 = λ2 − λ1 for the inverse problem, and its two adjacent sides. In the course of the 18th century these problems were elevated (especially in literature in the German language) to the principal geodesic problems (Hansen 1865,第69頁).
For a sphere the solutions to these problems are simple exercises in spherical trigonometry, whose solution is given by formulas for solving a spherical triangle. (See the article on great-circle navigation.)
For an ellipsoid of revolution, the characteristic constant defining the geodesic was found by Clairaut (1735). A systematic solution for the paths of geodesics was given by Legendre (1806) and Oriani (1806) (and subsequent papers in 1808 and 1810). The full solution for the direct problem (complete with computational tables and a worked out example) is given by Bessel (1825).[2]
Much of the early work on these problems was carried out by mathematicians—for example, Legendre, Bessel, and Gauss—who were also heavily involved in the practical aspects of surveying. Beginning in about 1830, the disciplines diverged: those with an interest in geodesy concentrated on the practical aspects such as approximations suitable for field work, while mathematicians pursued the solution of geodesics on a triaxial ellipsoid, the analysis of the stability of closed geodesics, etc.
During the 18th century geodesics were typically referred to as "shortest lines".[3] The term "geodesic line" was coined by Laplace (1799b):
Nous désignerons cette ligne sous le nom de ligne géodésique [We will call this line the geodesic line].
This terminology was introduced into English either as "geodesic line" or as "geodetic line", for example (Hutton 1811),
A line traced in the manner we have now been describing, or deduced from trigonometrical measures, by the means we have indicated, is called a geodetic or geodesic line: it has the property of being the shortest which can be drawn between its two extremities on the surface of the Earth; and it is therefore the proper itinerary measure of the distance between those two points.
In its adoption by other fields "geodesic line", frequently shortened, to "geodesic", was preferred.[4]
This section treats the problem on an ellipsoid of revolution (both oblate and prolate). The problem on a triaxial ellipsoid is covered in the next section.
When determining distances on the earth, various approximate methods are frequently used; some of these are described in the article on geographical distance.
Equations for a geodesic
Here the equations for a geodesic are developed; these allow the geodesics of any length to be computed accurately. The following derivation closely follows that of Bessel (1825). Bagratuni (1962,§15), Krakiwsky & Thomson (1974,§4), Rapp (1993,§1.2), and Borre & Strang (2012) also provide derivations of these equations.
Consider an ellipsoid of revolution with equatorial radius a and polar semi-axis b. Define the flattening f = (a − b)/a, the eccentricity e2 = f(2 − f), and the second eccentricity e′ = e/(1 − f). (In most applications in geodesy, the ellipsoid is taken to be oblate, a > b; however, the theory applies without change to prolate ellipsoids, a < b, in which case f, e2, and e′2 are negative.)
Let an elementary segment of a path on the ellipsoid have length ds. From Figs. 2 and 3, we see that if its azimuth is α, then ds is related to dφ and dλ by
- (1)
where ρ is the meridional radius of curvature, R = ν cosφ is the radius of the circle of latitude φ, and ν is the normal radius of curvature. The elementary segment is therefore given by
or
where φ′ = dφ/dλ and L depends on φ through ρ(φ) and R(φ). The length of an arbitrary path between (φ1, λ1) and (φ2, λ2) is given by
where φ is a function of λ satisfying φ(λ1) = φ1 and φ(λ2) = φ2. The shortest path or geodesic entails finding that function φ(λ) which minimizes s12. This is an exercise in the calculus of variations and the minimizing condition is given by the Beltrami identity,
Substituting for L and using Eqs. (1) gives
Clairaut (1735) first found this relation, using a geometrical construction; a similar derivation is presented by Lyusternik (1964,§10).[5] Differentiating this relation and manipulating the result gives (Jekeli 2012,Eq. (2.95))
This, together with Eqs. (1), leads to a system of ordinary differential equations for a geodesic (Borre & Strang 2012,Eqs. (11.71) and (11.76))
- (2)
We can express R in terms of the parametric latitude, β,[6] using
(see Fig. 4 for the geometrical construction), and Clairaut's relation then becomes
This is the sine rule of spherical trigonometry relating two sides of the triangle NAB (see Fig. 5), NA = ½π − β1, and NB = ½π − β2 and their opposite angles B = π − α2 and A = α1.
In order to find the relation for the third side AB = σ12, the spherical arc length, and included angle N = ω12, the spherical longitude, it is useful to consider the triangle NEP representing a geodesic starting at the equator; see Fig. 6. In this figure, the variables referred to the auxiliary sphere are shown with the corresponding quantities for the ellipsoid shown in parentheses. Quantities without subscripts refer to the arbitrary point P; E, the point at which the geodesic crosses the equator in the northward direction, is used as the origin for σ, s and ω.
If the side EP is extended by moving P infinitesimally (see Fig. 7), we obtain
- (3)
Combining Eqs. (1) and (3) gives differential equations for s and λ
Up to this point, we have not made use of the specific equations for an ellipsoid, and indeed the derivation applies to an arbitrary surface of revolution.[7] Bessel now specializes to an ellipsoid in which R and Z are related by
where Z is the height above the equator (see Fig. 4). Differentiating this and setting dR/dZ = −sinφ/cosφ gives
eliminating Z from these equations, we obtain
This relation between β and φ can be written as
which is the normal definition of the parametric latitude on an ellipsoid. Furthermore, we have
so that the differential equations for the geodesic become
The last step is to use σ as the independent parameter[8] in both of these differential equations and thereby to express s and λ as integrals. Applying the sine rule to the vertices E and G in the spherical triangle EGP in Fig. 6 gives
where α0 is the azimuth at E. Substituting this into the equation for ds/dσ and integrating the result gives
- (4)
where
and the limits on the integral are chosen so that s(σ = 0) = 0. Legendre (1811,第180頁) pointed out that the equation for s is the same as the equation for the arc on an ellipse with semi-axes b(1 + e′2 cos2α0)1/2 and b. In order to express the equation for λ in terms of σ, we write
which follows from Eq. (3) and Clairaut's relation. This yields
- (5)
and the limits on the integrals are chosen so that λ = λ0 at the equator crossing, σ = 0.
In using these integral relations, we allow σ to increase continuously (not restricting it to a range [−π, π], for example) as the great circle, resp. geodesic, encircles the auxiliary sphere, resp. ellipsoid. The quantities ω, λ, and s are likewise allowed to increase without limit. Once the problem is solved, λ can be reduced to the conventional range.
This completes the solution of the path of a geodesic using the auxiliary sphere. By this device a great circle can be mapped exactly to a geodesic on an ellipsoid of revolution. However, because the equations for s and λ in terms of the spherical quantities depend on α0, the mapping is not a consistent mapping of the surface of the sphere to the ellipsoid or vice versa; instead, it should be viewed merely as a convenient tool for solving for a particular geodesic.
There are also several ways of approximating geodesics on an ellipsoid which usually apply for sufficiently short lines (Rapp 1991,§6); however, these are typically comparable in complexity to the method for the exact solution given above (Jekeli 2012,§2.1.4).
Behavior of geodesics
Before solving for the geodesics, it is worth reviewing their behavior. Fig. 8 shows the simple closed geodesics which consist of the meridians (green) and the equator (red). (Here the qualification "simple" means that the geodesic closes on itself without an intervening self-intersection.) This follows from the equations for the geodesics given in the previous section.
For meridians, we have α0 = 0 and Eq. (5) becomes λ = ω + λ0, i.e., the longitude will vary the same way as for a sphere, jumping by π each time the geodesic crosses the pole. The distance, Eq. (4), reduces to the length of an arc of an ellipse with semi-axes a and b (as expected), expressed in terms of parametric latitude, β.
The equator (β = 0 on the auxiliary sphere, φ = 0 on the ellipsoid) corresponds to α0 = ½π. The distance reduces to the arc of a circle of radius b (and not a), s = bσ, while the longitude simplifies to λ = (1 − f)σ + λ0. A geodesic that is nearly equatorial will intersect the equator at intervals of πb. As a consequence, the maximum length of a equatorial geodesic which is also a shortest path is πb on an oblate ellipsoid (on a prolate ellipsoid, the maximum length is πa).
All other geodesics are typified by Figs. 9 to 11. Figure 9 shows latitude as a function of longitude for a geodesic starting on the equator with α0 = 45°. A full cycle of the geodesic, from one northward crossing of the equator to the next, is shown. The equatorial crossings are called nodes and the points of maximum or minimum latitude are called vertices; the vertex latitudes are given by |β| = ±(½π − |α0|). The latitude is an odd, resp. even, function of the longitude about the nodes, resp. vertices. The geodesic completes one full oscillation in latitude before the longitude has increased by 360°. Thus, on each successive northward crossing of the equator (see Fig. 10), λ falls short of a full circuit of the equator by approximately 2π f sinα0 (for a prolate ellipsoid, this quantity is negative and λ completes more that a full circuit; see Fig. 12). For nearly all values of α0, the geodesic will fill that portion of the ellipsoid between the two vertex latitudes (see Fig. 11).
If the ellipsoid is sufficiently oblate, i.e., b/a < ½, another class of simple closed geodesics is possible (Klingenberg 1982,§3.5.19). Two such geodesics are illustrated in Figs. 13 and 14. Here b/a = 2/7 and the equatorial azimuth, α0, for the green (resp. blue) geodesic is chosen to be 53.175° (resp. 75.192°), so that the geodesic completes 2 (resp. 3) complete oscillations about the equator on one circuit of the ellipsoid.
Evaluation of the integrals
Solving the geodesic problems entails evaluating the integrals for the distance, s, and the longitude, λ, Eqs. (4) and (5). In geodetic applications, where f is small, the integrals are typically evaluated as a series; for this purpose, the second form of the longitude integral is preferred (since it avoids the near singular behavior of the first form when geodesics pass close to a pole). In both integrals, the integrand is an even periodic function of period π. Furthermore, the term dependent on σ is multiplied by a small quantity k2 = O(f). As a consequence, the integrals can both be written in the form
where B0 = 1 + O(f) and Bj = O(f j). Series expansions for Bj can readily be found and the result truncated so that only terms which are O(f J) and larger are retained.[9] (Because the longitude integral is multiplied by f, it is typically only necessary to retain terms up to O(f J−1) in that integral.) This prescription is followed by many authors (Legendre 1806) (Oriani 1806) (Bessel 1825) (Helmert 1880) (Rainsford 1955) (Rapp 1993). Vincenty (1975a) uses J = 3 which provides an accuracy of about 0.1 mm for the WGS84 ellipsoid. Karney (2013) gives expansions carried out for J = 6 which suffices to provide full double precision accuracy for |f| ≤ 1/50. Trigonometric series of this type can be conveniently summed using Clenshaw summation.
In order to solve the direct geodesic problem, it is necessary to find σ given s. Since the integrand in the distance integral is positive, this problem has a unique root, which may be found using Newton's method, noting that the required derivative is just the integrand of the distance integral. Oriani (1833) instead uses series reversion so that σ can be found without iteration; Helmert (1880) gives a similar series.[10] The reverted series converges somewhat slower that the direct series and, if |f| > 1/100, Karney (2013,addenda) supplements the reverted series with one step of Newton's method to maintain accuracy. Vincenty (1975a) instead relies on a simpler (but slower) function iteration to solve for σ.
It is also possible to evaluate the integrals (4) and (5) by numerical quadrature (Saito 1970) (Saito 1979) (Sjöberg & Shirazian 2012) or to apply numerical techniques for the solution of the ordinary differential equations, Eqs. (2) (Kivioja 1971) (Thomas & Featherstone 2005) (Panou et al. 2013) . Such techniques can be used for arbitrary flattening f. However, if f is small, e.g., |f| ≤ 1/50, they do not offer the speed and accuracy of the series expansions described above. Furthermore, for arbitrary f, the evaluation of the integrals in terms of elliptic integrals (see below) also provides a fast and accurate solution. On the other hand, Mathar (2007) has tackled the more complex problem of geodesics on the surface at a constant altitude, h, above the ellipsoid by solving the corresponding ordinary differential equations, Eqs. (2) with [ρ, ν] replaced by [ρ + h, ν + h].
Geodesics on an ellipsoid was an early application of elliptic integrals. In particular, Legendre (1811) writes the integrals, Eqs. (4) and (5), as
- (6)
- (7)
where
and
and F(φ, k), E(φ, k), and Π(φ, α2, k), are incomplete elliptic integrals in the notation of DLMF (2010,§19.2(ii)).[11][12] The first formula for the longitude in Eq. (7) follows directly from the first form of Eq. (5). The second formula in Eq. (7), due to Cayley (1870), is more convenient for calculation since the elliptic integral appears in a small term. The equivalence of the two forms follows from DLMF (2010,Eq. (19.7.8)). Fast algorithms for computing elliptic integrals are given by Carlson (1995) in terms of symmetric elliptic integrals. Equation (6) is conveniently inverted using Newton's method. The use of elliptic integrals provides a good method of solving the geodesic problem for |f| > 1/50.[13]
Solution of the direct problem
The basic strategy for solving the geodesic problems on the ellipsoid is to map the problem onto the auxiliary sphere by converting φ, λ, and s, to β, ω and σ, to solve the corresponding great-circle problem on the sphere, and to transfer the results back to the ellipsoid.
In implementing this program, we will frequently need to solve the "elementary" spherical triangle for NEP in Fig. 6 with P replaced by either A (subscript 1) or B (subscript 2). For this purpose, we can apply Napier's rules for quadrantal triangles to the triangle NEP on the auxiliary sphere which give
We can also stipulate that cosβ ≥ 0 and cosα0 ≥ 0.[14] Implementing this plan for the direct problem is straightforward. We are given φ1, α1, and s12. From φ1 we obtain β1 (using the formula for the parametric latitude). We now solve the triangle problem with P = A and β1 and α1 given to find α0, σ1, and ω1.[15] Use the distance and longitude equations, Eqs. (4) and (5), together with the known value of λ1, to find s1 and λ0. Determine s2 = s1 + s12 and invert the distance equation to find σ2. Solve the triangle problem with P = B and α0 and σ2 given to find β2, ω2, and α2. Convert β2 to φ2 and substitute σ2 and ω2 into the longitude equation to give λ2.[16]
The overall method follows the procedure for solving the direct problem on a sphere. It is essentially the program laid out by Bessel (1825),[17] Helmert (1880,§5.9), and most subsequent authors.
Intermediate points, way-points, on a geodesic can be found by holding φ1 and α1 fixed and solving the direct problem for several values of s12. Once the first waypoint is found, only the last portion of the solution (starting with the determination of s2) needs to be repeated for each new value of s12.
Solution of the inverse problem
The ease with which the direct problem can be solved results from the fact that given φ1 and α1, we can immediately find α0, the parameter in the distance and longitude integrals, Eqs. (4) and (5). In the case of the inverse problem, we are given λ12, but we cannot easily relate this to the equivalent spherical angle ω12 because α0 is unknown. Thus, the solution of the problem requires that α0 be found iteratively. Before tackling this, it is worth understanding better the behavior of geodesics, this time, keeping the starting point fixed and varying the azimuth.
Suppose point A in the inverse problem has φ1 = −30° and λ1 = 0°. Fig. 15 shows geodesics (in blue) emanating A with α1 a multiple of 15° up to the point at which they cease to be shortest paths. (The flattening has been increased to 1/10 in order to accentuate the ellipsoidal effects.) Also shown (in green) are curves of constant s12, which are the geodesic circles centered A. Gauss (1828) showed that, on any surface, geodesics and geodesic circle intersect at right angles. The red line is the cut locus, the locus of points which have multiple (two in this case) shortest geodesics from A. On a sphere, the cut locus is a point. On an oblate ellipsoid (shown here), it is a segment of the circle of latitude centered on the point antipodal to A, φ = −φ1. The longitudinal extent of cut locus is approximately λ12 ∈ [π − f π cosφ1, π + f π cosφ1]. If A lies on the equator, φ1 = 0, this relation is exact and as a consequence the equator is only a shortest geodesic if |λ12| ≤ (1 − f)π. For a prolate ellipsoid, the cut locus is a segment of the anti-meridian centered on the point antipodal to A, λ12 = π, and this means that meridional geodesics stop being shortest paths before the antipodal point is reached.
The solution of the inverse problem involves determining, for a given point B with latitude φ2 and longitude λ2 which blue and green curves it lies on; this determines α1 and s12 respectively. In Fig. 16, the ellipsoid has been "rolled out" onto a plate carrée projection. Suppose φ2 = 20°, the green line in the figure. Then as α1 is varied between 0° and 180°, the longitude at which the geodesic intersects φ = φ2 varies between 0° and 180° (see Fig. 17). This behavior holds provided that |φ2| ≤ |φ1| (otherwise the geodesic does not reach φ2 for some values of α1). Thus, the inverse problem may be solved by determining the value α1 which results in the given value of λ12 when the geodesic intersects the circle φ = φ2.
This suggests the following strategy for solving the inverse problem (Karney 2013) . Assume that the points A and B satisfy
- (8)
(There is no loss of generality in this assumption, since the symmetries of the problem can be used to generate any configuration of points from such configurations.)
- First treat the "easy" cases, geodesics which lie on a meridian or the equator. Otherwise...
- Guess a value of α1.
- Solve the so-called hybrid geodesic problem, given φ1, φ2, and α1 find λ12, s12, and α2, corresponding to the first intersection of the geodesic with the circle φ = φ2.
- Compare the resulting λ12 with the desired value and adjust α1 until the two values agree. This completes the solution.
Each of these steps requires some discussion.
1. For an oblate ellipsoid, the shortest geodesic lies on a meridian if either point lies on a pole or if λ12 = 0 or ±π. The shortest geodesic follows the equator if φ1 = φ2 = 0 and |λ12| ≤ (1 − f)π. For a prolate ellipsoid, the meridian is no longer the shortest geodesic if λ12 = ±π and the points are close to antipodal (this will be discussed in the next section). There is no longitudinal restriction on equatorial geodesics.
2. In most cases a suitable starting value of α1 is found by solving the spherical inverse problem[14]
with ω12 = λ12. This may be a bad approximation if A and B are nearly antipodal (both the numerator and denominator in the formula above become small); however, this may not matter (depending on how step 4 is handled).
3. The solution of the hybrid geodesic problem is as follows. It starts the same way as the solution of the direct problem, solving the triangle NEP with P = A to find α0, σ1, ω1, and λ0.[18] Now find α2 from sinα2 = sinα0/cosβ2, taking cosα2 ≥ 0 (corresponding to the first, northward, crossing of the circle φ = φ2). Next, σ2 is given by tanσ2 = tanβ2/cosα2 and ω2 by tanω2 = tanσ2/sinα0.[14] Finally, use the distance and longitude equations, Eqs. (4) and (5), to find s12 and λ12.[19]
4. In order to discuss how α1 is updated, let us define the root-finding problem in more detail. The curve in Fig. 17 shows λ12(α1; φ1, φ2) where we regard φ1 and φ2 as parameters and α1 as the independent variable. We seek the value of α1 which is the root of
where g(0) ≤ 0 and g(π) ≥ 0. In fact, there is a unique root in the interval α1 ∈ [0, π]. Any of a number of root-finding algorithms can be used to solve such an equation. Karney (2013) uses Newton's method, which requires a good starting guess; however it may be supplemented by a fail-safe method, such as the bisection method, to guarantee convergence.
An alternative method for solving the inverse problem is given by Helmert (1880,§5.13). Let us rewrite the Eq. (5) as
Helmert's method entails assuming that ω12 = λ12, solving the resulting problem on auxiliary sphere, and obtaining an updated estimate of ω12 using
This fixed point iteration is repeated until convergence. Rainsford (1955) advocates this method and Vincenty (1975a) adopted it in his solution of the inverse problem. The drawbacks of this method are that convergence is slower than obtained using Newton's method (as described above) and, more seriously, that the process fails to converge at all for nearly antipodal points. In a subsequent report, Vincenty (1975b) attempts to cure this defect; but he is only partially successful—the NGS (2012) implementation still includes Vincenty's fix still fails to converge in some cases. Lee (2011) has compared 17 methods for solving the inverse problem against the method given by Karney (2013) .
The shortest distance returned by the solution of the inverse problem is (obviously) uniquely defined. However, if B lies on the cut locus of A there are multiple azimuths which yield the same shortest distance. Here is a catalog of those cases:
- φ1 = −φ2 (with neither point at a pole). If α1 = α2, the geodesic is unique. Otherwise there are two geodesics and the second one is obtained by interchanging α1 and α2. (This occurs when λ12 ≈ ±π for oblate ellipsoids.)
- λ12 = ±π (with neither point at a pole). If α1 = 0 or ±π, the geodesic is unique. Otherwise there are two geodesics and the second one is obtained by negating α1 and α2. (This occurs when φ1 + φ2 ≈ 0 for prolate ellipsoids.)
- A and B are at opposite poles. There are infinitely many geodesics which can be generated by varying the azimuths so as to keep α1 + α2 constant. (For spheres, this prescription applies when A and B are antipodal.)
Differential behavior of geodesics
Various problems involving geodesics require knowing their behavior when they are perturbed. This is useful in trigonometric adjustments (Ehlert 1993), determining the physical properties of signals which follow geodesics, etc. Consider a reference geodesic, parameterized by s the length from the northward equator crossing, and a second geodesic a small distance t(s) away from it. Gauss (1828) showed that t(s) obeys the Gauss-Jacobi equation
- (9)
where K(s) is the Gaussian curvature at s. The solution may be expressed as the sum of two independent solutions
where
We shall abbreviate m(s1, s2) = m12, the so-called reduced length, and M(s1, s2) = M12, the geodesic scale.[20] Their basic definitions are illustrated in Fig. 18. Christoffel (1869) made an extensive study of their properties. The reduced length obeys a reciprocity relation,
Their derivatives are
Assuming that points 1, 2, and 3, lie on the same geodesic, then the following addition rules apply (Karney 2013) ,
The reduced length and the geodesic scale are components of the Jacobi field.
The Gaussian curvature for an ellipsoid of revolution is
Helmert (1880,Eq. (6.5.1.)) solved the Gauss-Jacobi equation for this case obtaining
where
As we see from Fig. 18 (top sub-figure), the separation of two geodesics starting at the same point with azimuths differing by dα1 is m12 dα1. On a closed surface such as an ellipsoid, we expect m12 to oscillate about zero. Indeed, if the starting point of a geodesic is a pole, φ1 = ½π, then the reduced length is the radius of the circle of latitude, m12 = a cosβ2 = a sinσ12. Similarly, for a meridional geodesic starting on the equator, φ1 = α1 = 0, we have M12 = cosσ12. In the typical case, these quantities oscillate with a period of about 2π in σ12 and grow linearly with distance at a rate proportional to f. In trigonometric adjustments over small areas, it may be possible to approximate K(s) in Eq. (9) by a constant K. In this limit, the solutions for m12 and M12 are the same as for a sphere of radius 1/√K, namely,
To simplify the discussion of shortest paths in this paragraph we consider only geodesics with s12 > 0. The point at which m12 becomes zero is the point conjugate to the starting point. In order for a geodesic between A and B, of length s12, to be a shortest path it must satisfy the Jacobi condition (Jacobi 1837) (Jacobi 1866,§6) (Forsyth 1927,§§26–27) (Bliss 1916) , that there is no point conjugate to A between A and B. If this condition is not satisfied, then there is a nearby path (not necessarily a geodesic) which is shorter. Thus, the Jacobi condition is a local property of the geodesic and is only a necessary condition for the geodesic being a global shortest path. Necessary and sufficient conditions for a geodesic being the shortest path are:
- for an oblate ellipsoid, |σ12| ≤ π;
- for a prolate ellipsoid, |λ12| ≤ π, if α0 ≠ 0; if α0 = 0, the supplemental condition m12 ≥ 0 is required if |λ12| = π.
The latter condition above can be used to determine whether the shortest path is a meridian in the case of a prolate ellipsoid with |λ12| = π. The derivative required to solve the inverse method using Newton's method, ∂λ12(α1; φ1, φ2) / ∂α1, is given in terms of the reduced length (Karney 2013,Eq. (46)) .
Geodesic map projections
Two map projections are defined in terms of geodesics. They are based on polar and rectangular geodesic coordinates on the surface (Gauss 1828). The polar coordinate system (r, θ) is centered on some point A. The coordinates of another point B are given by r = s12 and θ = ½π − α1 and these coordinates are used to find the projected coordinates on a plane map, x = r cosθ and y = r sinθ. The result is the familiar azimuthal equidistant projection; in the field of the differential geometry of surfaces, it is called the exponential map. Due to the basic properties of geodesics (Gauss 1828), lines of constant r and lines of constant θ intersect at right angles on the surface. The scale of the projection in the radial direction is unity, while the scale in the azimuthal direction is s12/m12.
The rectangular coordinate system (x, y) uses a reference geodesic defined by A and α1 as the x axis. The point (x, y) is found by traveling a distance s13 = x from A along the reference geodesic to an intermediate point C and then turning ½π counter-clockwise and traveling along a geodesic a distance s32 = y. If A is on the equator and α1 = ½π, this gives the equidistant cylindrical projection. If α1 = 0, this gives the Cassini-Soldner projection. Cassini's map of France placed A at the Paris Observatory. Due to the basic properties of geodesics (Gauss 1828), lines of constant x and lines of constant y intersect at right angles on the surface. The scale of the projection in the y direction is unity, while the scale in the x direction is 1/M32.
The gnomonic projection is a projection of the sphere where all geodesics (i.e., great circles) map to straight lines (making it a convenient aid to navigation). Such a projection is only possible for surfaces of constant Gaussian curvature (Beltrami 1865) . Thus a projection in which geodesics map to straight lines is not possible for an ellipsoid. However, it is possible to construct an ellipsoidal gnomonic projection in which this property approximately holds (Karney 2013,§8) . On the sphere, the gnomonic projection is the limit of a doubly azimuthal projection, a projection preserving the azimuths from two points A and B, as B approaches A. Carrying out this limit in the case of a general surface yields an azimuthal projection in which the distance from the center of projection is given by ρ = m12/M12. Even though geodesics are only approximately straight in this projection, all geodesics through the center of projection are straight. The projection can then be used to give an iterative but rapidly converging method of solving some problems involving geodesics, in particular, finding the intersection of two geodesics and finding the shortest path from a point to a geodesic.
The Hammer retroazimuthal projection is a variation of the azimuthal equidistant projection (Hammer 1910). A geodesic is constructed from a central point A to some other point B. The polar coordinates of the projection of B are r = s12 and θ = ½π − α2 (which depends on the azimuth at B, instead of at A). This can be used to determine the direction from an arbitrary point to some fixed center. Hinks (1929) suggested another application: if the central point A is a beacon, such as the Rugby Clock, then at an unknown location B the range and the bearing to A can be measured and the projection can be used to estimate the location of B.
Envelope of geodesics
The geodesics from a particular point A if continued past the cut locus form an envelope illustrated in Fig. 19. Here the geodesics for which α1 is a multiple of 3° are shown in light blue. (The geodesics are only shown for their first passage close to the antipodal point, not for subsequent ones.) Some geodesic circles are shown in green; these form cusps on the envelope. The cut locus is shown in red. The envelope is the locus of points which are conjugate to A; points on the envelope may be computed by finding the point at which m12 = 0 on a geodesic (and Newton's method can be used to find this point). Jacobi (1891) calls this star-like figure produced by the envelope an astroid.
Outside the astroid two geodesics intersect at each point; thus there are two geodesics (with a length approximately half the circumference of the ellipsoid) between A and these points. This corresponds to the situation on the sphere where there are "short" and "long" routes on a great circle between two points. Inside the astroid four geodesics intersect at each point. Four such geodesics are shown in Fig. 20 where the geodesics are numbered in order of increasing length. (This figure uses the same position for A as Fig. 15 and is drawn in the same projection.) The two shorter geodesics are stable, i.e., m12 > 0, so that there is no nearby path connecting the two points which is shorter; the other two are unstable. Only the shortest line (the first one) has σ12 ≤ π. All the geodesics are tangent to the envelope which is shown in green in the figure. A similar set of geodesics for the WGS84 ellipsoid is given in this table (Karney 2011,Table 1):
No. | α1 (°) | α2 (°) | s12 (m) | σ12 (°) | m12 (m) |
---|---|---|---|---|---|
1 | 161.890524736 | 18.090737246 | 19989832.8276 | 179.894971388 | 57277.3769 |
2 | 30.945226882 | 149.089121757 | 20010185.1895 | 180.116378785 | 24240.7062 |
3 | 68.152072881 | 111.990398904 | 20011886.5543 | 180.267429871 | −22649.2935 |
4 | −81.075605986 | −99.282176388 | 20049364.2525 | 180.630976969 | −68796.1679 |
The approximate shape of the astroid is given by
or, in parametric form,
The astroid is also the envelope of the family of lines
where γ is a parameter. (These are generated by the rod of the trammel of Archimedes.) This aids in finding a good starting guess for α1 for Newton's method for in inverse problem in the case of nearly antipodal points (Karney 2013,§5) .
The astroid is the (exterior) evolute of the geodesic circles centered at A. Likewise, the geodesic circles are involutes of the astroid.
Area of a geodesic polygon
A geodesic polygon is a polygon whose sides are geodesics. The area of such a polygon may be found by first computing the area between a geodesic segment and the equator, i.e., the area of the quadrilateral AFHB in Fig. 1 (Danielsen 1989) . Once this area is known, the area of a polygon may be computed by summing the contributions from all the edges of the polygon.
Here we develop the formula for the area S12 of AFHB following Sjöberg (2006) . The area of any closed region of the ellipsoid is
where dT is an element of surface area and K is the Gaussian curvature. Now the Gauss–Bonnet theorem applied to a geodesic polygon states
where
is the geodesic excess and θj is the exterior angle at vertex j. Multiplying the equation for Γ by R22, where R2 is the authalic radius, and subtracting this from the equation for T gives[21]
where the value of K for an ellipsoid has been substituted. Applying this formula to the quadrilateral AFHB, noting that Γ = α2 − α1, and performing the integral over φ gives
where the integral is over the geodesic line (so that φ is implicitly a function of λ). Converting this into an integral over σ, we obtain
where
and the notation E12 = α2 − α1 is used for the geodesic excess. The integral can be expressed as a series valid for small f (Danielsen 1989) (Karney 2013,§6 and addendum) .
The area of a geodesic polygon is given by summing S12 over its edges. This result holds provided that the polygon does not include a pole; if it does 2π R22 must be added to the sum. If the edges are specified by their vertices, then a convenient expression for E12 is
This result follows from one of Napier's analogies.
Software implementations
An implementation of Vincenty's algorithm in Fortran is provided by NGS (2012). Version 3.0 includes Vincenty's treatment of nearly antipodal points (Vincenty 1975b). Vincenty's original formulas are used in many geographic information systems. Except for nearly antipodal points (where the inverse method fails to converge), this method is accurate to about 0.1 mm for the WGS84 ellipsoid (Karney 2011,§9).
The algorithms given in Karney (2013) are included in
GeographicLib (Karney 2014). These are accurate to about
15 nanometers for the WGS84 ellipsoid. Implementations in several
languages (C++, C, Fortran,
Java, JavaScript,
Python, Matlab, and
Maxima) are provided. In addition to solving the
basic geodesic problem, this library can return m12,
M12, M21, and S12. The
library includes a command-line utility, GeodSolve
, for
geodesic calculations. As of version 4.9.1, the PROJ.4 library for
cartographic projections uses the C implementation for geodesic
calculations. This is exposed in the command-line utility,
geod
, and in the library itself.
The solution of the geodesic problems in terms of elliptic integrals is
included in GeographicLib (in C++ only), e.g., via the -E
option to GeodSolve
. This method of solution is about
2–3 times slower than using series expansions; however it
provides accurate solutions for ellipsoids of revolution with
b/a ∈ [0.01, 100] (Karney 2013,addenda) .
Geodesics on a triaxial ellipsoid
Solving the geodesic problem for an ellipsoid of revolution is, from the mathematical point of view, relatively simple: because of symmetry, geodesics have a constant of the motion, given by Clairaut's relation allowing the problem to be reduced to quadrature. By the early 19th century (with the work of Legendre, Oriani, Bessel, et al.), there was a complete understanding of the properties of geodesics on an ellipsoid of revolution.
On the other hand, geodesics on a triaxial ellipsoid (with 3 unequal axes) have no obvious constant of the motion and thus represented a challenging "unsolved" problem in the first half of the 19th century. In a remarkable paper, Jacobi (1839) discovered a constant of the motion allowing this problem to be reduced to quadrature also (Klingenberg 1982,§3.5).[22][23]
Triaxial coordinate systems
The key to the solution is expressing the problem in the "right" coordinate system. Consider the ellipsoid defined by
where (X,Y,Z) are Cartesian coordinates centered on the ellipsoid and, without loss of generality, a ≥ b ≥ c > 0.[24] A point on the surface is specified by a latitude and longitude. The geographical latitude and longitude (φ, λ) are defined by
The parametric latitude and longitude (φ′, λ′) are defined by
Jacobi (1866,§§26–27) employed the ellipsoidal latitude and longitude (β, ω) defined by
In the limit b → a, β becomes the parametric latitude for an oblate ellipsoid, so the use of the symbol β is consistent with the previous sections. However, ω is different from the spherical longitude defined above.[25]
Grid lines of constant β (in blue) and ω (in green) are given in Fig. 21. In contrast to (φ, λ) and (φ′, λ′), (β, ω) is an orthogonal coordinate system: the grid lines intersect at right angles. The principal sections of the ellipsoid, defined by X = 0 and Z = 0 are shown in red. The third principal section, Y = 0, is covered by the lines β = ±90° and ω = 0° or ±180°. These lines meet at four umbilical points (two of which are visible in this figure) where the principal radii of curvature are equal. Here and in the other figures in this section the parameters of the ellipsoid are a:b:c = 1.01:1:0.8, and it is viewed in an orthographic projection from a point above φ = 40°, λ = 30°.
The grid lines of the ellipsoidal coordinates may be interpreted in three different ways
- They are "lines of curvature" on the ellipsoid, i.e., they are parallel to the directions of principal curvature (Monge 1796).
- They are also intersections of the ellipsoid with confocal systems of hyperboloids of one and two sheets (Dupin 1813,Part 5).
- Finally they are geodesic ellipses and hyperbolas defined using two adjacent umbilical points (Hilbert & Cohn-Vossen 1952,第188頁). For example, the lines of constant β in Fig. 21 can be generated with the familiar string construction for ellipses with the ends of the string pinned to the two umbilical points.
Conversions between these three types of latitudes and longitudes and the Cartesian coordinates are simple algebraic exercises.
The element of length on the ellipsoid in ellipsoidal coordinates is given by
and the differential equations for a geodesic are
Jacobi's solution
Jacobi showed that the geodesic equations, expressed in ellipsoidal coordinates, are separable. Here is how he recounted his discovery to his friend and neighbor Bessel (Jacobi 1839,Letter to Bessel) ,
The day before yesterday, I reduced to quadrature the problem of geodesic lines on an ellipsoid with three unequal axes. They are the simplest formulas in the world, Abelian integrals, which become the well known elliptic integrals if 2 axes are set equal.
Königsberg, 28th Dec. '38.
The solution given by Jacobi (Jacobi 1839) (Jacobi 1866,§28) is
As Jacobi notes "a function of the angle β equals a function of the angle ω. These two functions are just Abelian integrals..." Two constants δ and γ appear in the solution. Typically δ is zero if the lower limits of the integrals are taken to be the starting point of the geodesic and the direction of the geodesics is determined by γ. However, for geodesics that start at an umbilical points, we have γ = 0 and δ determines the direction at the umbilical point. The constant γ may be expressed as
where α is the angle the geodesic makes with lines of constant ω. In the limit b → a, this reduces to sinα cosβ = const., the familiar Clairaut relation. A nice derivation of Jacobi's result is given by Darboux (1894,§§583–584) where he gives the solution found by Liouville (1846) for general quadratic surfaces. In this formulation, the distance along the geodesic, s, is found using
An alternative expression for the distance is
Survey of triaxial geodesics
On a triaxial ellipsoid, there are only 3 simple closed geodesics, the three principal sections of the ellipsoid given by X = 0, Y = 0, and Z = 0.[26] To survey the other geodesics, it is convenient to consider geodesics which intersect the middle principal section, Y = 0, at right angles. Such geodesics are shown in Figs. 22–26, which use the same ellipsoid parameters and the same viewing direction as Fig. 21. In addition, the three principal ellipses are shown in red in each of these figures.
If the starting point is β1 ∈ (−90°, 90°), ω1 = 0, and α1 = 90°, then γ > 0 and the geodesic encircles the ellipsoid in a "circumpolar" sense. The geodesic oscillates north and south of the equator; on each oscillation it completes slightly less that a full circuit around the ellipsoid resulting, in the typical case, in the geodesic filling the area bounded by the two latitude lines β = ±β1. Two examples are given in Figs. 22 and 23. Figure 22 shows practically the same behavior as for an oblate ellipsoid of revolution (because a ≈ b); compare to Fig. 11. However, if the starting point is at a higher latitude (Fig. 22) the distortions resulting from a ≠ b are evident. All tangents to a circumpolar geodesic touch the confocal single-sheeted hyperboloid which intersects the ellipsoid at β = β1 (Chasles 1846) (Hilbert & Cohn-Vossen 1952,第223–224頁).
If the starting point is β1 = 90°, ω1 ∈ (0°, 180°), and α1 = 180°, then γ < 0 and the geodesic encircles the ellipsoid in a "transpolar" sense. The geodesic oscillates east and west of the ellipse X = 0; on each oscillation it completes slightly more that a full circuit around the ellipsoid resulting, in the typical case, in the geodesic filling the area bounded by the two longitude lines ω = ω1 and ω = 180° − ω1. If a = b, all meridians are geodesics; the effect of a ≠ b causes such geodesics to oscillate east and west. Two examples are given in Figs. 24 and 25. The constriction of the geodesic near the pole disappears in the limit b → c; in this case, the ellipsoid becomes a prolate ellipsoid and Fig. 24 would resemble Fig. 12 (rotated on its side). All tangents to a transpolar geodesic touch the confocal double-sheeted hyperboloid which intersects the ellipsoid at ω = ω1.
If the starting point is β1 = 90°, ω1 = 0° (an umbilical point), and α1 = 135° (the geodesic leaves the ellipse Y = 0 at right angles), then γ = 0 and the geodesic repeatedly intersects the opposite umbilical point and returns to its starting point. However, on each circuit the angle at which it intersects Y = 0 becomes closer to 0° or 180° so that asymptotically the geodesic lies on the ellipse Y = 0 (Hart 1849) (Arnold 1989,第265頁). This is shown in Fig. 26. Note that a single geodesic does not fill an area on the ellipsoid. All tangents to umbilical geodesics touch the confocal hyperbola which intersects the ellipsoid at the umbilic points.
Umbilical geodesic enjoy several interesting properties.
- Through any point on the ellipsoid, there are two umbilical geodesics.
- The geodesic distance between opposite umbilical points is the same regardless of the initial direction of the geodesic.
- Whereas the closed geodesics on the ellipses X = 0 and Z = 0 are stable (an geodesic initially close to and nearly parallel to the ellipse remains close to the ellipse), the closed geodesic on the ellipse Y = 0, which goes through all 4 umbilical points, is exponentially unstable. If it is perturbed, it will swing out of the plane Y = 0 and flip around before returning to close to the plane. (This behavior may repeat depending on the nature of the initial perturbation.)
If the starting point A of a geodesic is not an umbilical point, then its envelope is an astroid with two cusps lying on β = −β1 and the other two on ω = ω1 + π (Sinclair 2003) . The cut locus for A is the portion of the line β = −β1 between the cusps (Itoh & Kiyohara 2004) .
(Panou 2013) gives a method for solving the inverse problem for a triaxial ellipsoid by directly integrating the system of ordinary differential equations for a geodesic. (Thus, it does not utilize Jacobi's solution.)
Applications
The direct and inverse geodesic problems no longer play the central role in geodesy that they once did. Instead of solving adjustment of geodetic networks as a two-dimensional problem in spheroidal trigonometry, these problem are now solved by three-dimensional methods (Vincenty & Bowring 1978). Nevertheless, terrestrial geodesics still play an important role in several areas:
- for measuring distances and areas in geographic information systems;
- the definition of maritime boundaries (UNCLOS 2006);
- in the rules of the Federal Aviation Administration for area navigation (RNAV 2007);
- the method of measuring distances in the FAI Sporting Code (FAI 2013).
By the principle of least action, many problems in physics can be formulated as a variational problem similar to that for geodesics. Indeed, the geodesic problem is equivalent to the motion of a particle constrained to move on the surface, but otherwise subject to no forces (Laplace 1799a) (Hilbert & Cohn-Vossen 1952,第222頁). For this reason, geodesics on simple surfaces such as ellipsoids of revolution or triaxial ellipsoids are frequently used as "test cases" for exploring new methods. Examples include:
- the development of elliptic integrals (Legendre 1811) and elliptic functions (Weierstrass 1861);
- the development of differential geometry (Gauss 1828) (Christoffel 1869);
- methods for solving systems of differential equations by a change of independent variables (Jacobi 1839) ;
- the study of caustics (Jacobi 1891);
- investigations into the number and stability of periodic orbits (Poincaré 1905) ;
- in the limit c → 0, geodesics on a triaxial ellipsoid reduce to a case of dynamical billiards;
- extensions to an arbitrary number of dimensions (Knörrer 1980) ;
- geodesic flow on a surface (Berger 2010,Chap. 12).
See also
- Geographical distance
- Great-circle navigation
- Geodesics
- Geodesy
- Meridian arc
- Rhumb line
- Vincenty's formulae
Notes
- ^ Here α2 is the forward azimuth at B. Some authors calculate the back azimuth instead; this is given by α2 ± π.
- ^ This prompted a courteous note by Oriani (1826) noting his previous work, of which, presumably, Bessel was unaware, and also a thinly veiled accusation of plagiarism from Ivory (1826) (his phrase was "second-hand from Germany"), which resulted in an angry rebuttal by Bessel (1827) .
- ^ Clairaut (1735) uses the circumlocution "perpendiculars to the meridian"; this refers to Cassini's proposed map projection for France (Cassini 1735) where one of the coordinates was the distance from the Paris meridian.
- ^ Kummell (1883) attempted to introduce the word "brachisthode" for geodesic. This effort failed.
- ^ Laplace (1799a) showed that a particle constrained to move on a surface but otherwise subject to no forces moves along a geodesic for that surface. Thus, Clairaut's relation is just a consequence of conservation of angular momentum for a particle on a surface of revolution. A similar proof is given by Bomford (1952,§8.06).
- ^ In terms of β, the element of distance on the ellipsoid is given by ds2 = (a2 sin2β2 + b2 cos2β) dβ2 + a2 cos2β dλ2.
- ^ It may be useful to impose the restriction that the surface have a positive curvature everywhere so that the latitude be single valued function of Z.
- ^ Other choices of independent parameter are possible. In particular many authors use the vertex of a geodesic (the point of maximum latitude) as the origin for σ.
- ^ Nowadays, the necessary algebraic manipulations, expanding in a Taylor series, integration, and performing trigonometric simplifications, can be carrying using a computer algebra system. Earlier, Levallois & Dupuy (1952) gave recurrence relations for the series in terms of Wallis' integrals and Pittman (1986) describes a similar method.
- ^ Legendre (1806,Art. 13) also gives a series for σ in terms of s; but this is not suitable for large distances.
- ^ Despite the presence of i = √−1, the elliptic integrals in Eqs. (6) and (7) are real.
- ^ Rollins (2010) obtains different, but equivalent, expressions in terms of elliptic integrals.
- ^ It is also possible to express the integrals in terms of Jacobi elliptic functions (Jacobi 1855) (Luther 1855) (Forsyth 1896) (Thomas 1970,Appendix 1). Halphen (1888) gives the solution for the complex quantities R exp(±iλ) = X ± iY in terms of Weierstrass sigma and zeta functions. This form is of interest because the separate periods of latitude and longitude of the geodesic are captured in a single doubly periodic function; see also Forsyth (1927,§75.)
- ^ 14.0 14.1 14.2 When solving for σ, α, or ω using a formula for its tangent, the quadrant should be determined from the signs of the numerator of the expression for the tangent, e.g., using the atan2 function.
- ^ If β1 = 0 and α1 = ±½π, the equation for σ1 is indeterminate and σ1 = 0 may be used.
- ^ Because tanω = sinα0 tanσ, ω changes quadrants in step with σ. It is therefore straightforward to express λ2 so that λ12 indicates how often and in what sense the geodesic has encircled the ellipsoid.
- ^ Bessel (1825) treated the longitude integral approximately in order to reduce the number of parameters in the equation from two to one so that it could be tabulated conveniently.
- ^ If φ1 = φ2 = 0, take sinσ1 = sinω1 = −0, consistent with the relations (8); this gives σ1 = ω1 = −π.
- ^ The ordering in relations (8) automatically results in σ12 > 0.
- ^ Bagratuni (1962,§17) uses the term "coefficient of convergence of ordinates" for the geodesic scale.
- ^ Sjöberg (2006) multiplies Γ by b2 instead of R22. However, this leads to a singular integrand (Karney 2011,§15).
- ^ This section is adapted from the documentation for GeographicLib (Karney 2014,geodesics on a triaxial ellipsoid)
- ^ Even though Jacobi and Weierstrass (1861) use terrestrial geodesics as the motivation for their work, a triaxial ellipsoid approximates the Earth only slightly better than an ellipsoid of revolution. A better approximation to the shape of the Earth is given by the geoid. However, geodesics on a surface of the complexity of the geoid are partly chaotic (Waters 2011) .
- ^ This notation for the semi-axes is incompatible with that used in the previous section on ellipsoids of revolution, where a and b stood for the equatorial radius and polar semi-axis. Thus the corresponding inequalities are a = a ≥ b > 0 for an oblate ellipsoid and b ≥ a = a > 0 for a prolate ellipsoid.
- ^ The limit b → c gives a prolate ellipsoid with ω playing the role of the parametric latitude.
- ^ If c/a < ½, there are other simple closed geodesics similar to those shown in Figs. 13 and 14 (Klingenberg 1982,§3.5.19).
References
- Arnold, V. I. Mathematical Methods of Classical Mechanics. Translated by K. Vogtmann & A. Weinstein 2nd. Springer-Verlag. 1989. ISBN 978-0-387-96890-2. OCLC 4037141.
- Bagratuni, G. V. Course in Spheroidal Geodesy (PDF). 1967 [1962]. OCLC 6150611. Translation from Russian of Курс сфероидической геодезии (Moscow, 1962) by U.S. Air Force (FTD-MT-64-390)
- doi:10.1007/BF03198517
{{cite doi}}已停用,請參見{{cite journal}}。 - Berger, M. Geometry Revealed. Translated by L. J. Senechal. Springer. 2010. ISBN 978-3-540-70996-1. doi:10.1007/978-3-540-70997-8.
- Bessel, F. W. . . Translated by C. F. F. Karney & R. E. Deakin. The calculation of longitude and latitude from geodesic measurements. Astronomische Nachrichten. 2010, 331 (8): 852–861 [1825]. arXiv:0908.1824 . doi:10.1002/asna.201011352. English translation of Astron. Nachr. 4, 241–254 (1825). Errata.
- doi:10.1002/asna.18270051202
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1090/S0002-9947-1916-1501037-4
{{cite doi}}已停用,請參見{{cite journal}}。 - Bomford, G. Geodesy. Oxford: Clarendon. 1952. OCLC 1396190.
- Borre, K.; Strang, W. G. Algorithms for Global Positioning. Wellesley-Cambridge Press. 2012. ISBN 978-0-9802327-3-8. OCLC 795014501. Chapter 11, Geometry of the Ellipsoid.
- doi:10.1007/BF02198293
{{cite doi}}已停用,請參見{{cite journal}}。 - Casper, P. W.; Bent, R. B. The effect of the Earth's oblate spheroid shape on the accuracy of a time-of-arrival lightning ground strike locating system (PDF). 1991. in Proceedings 1991 International Aerospace and Ground Conference on Lightning and Static Electricity, (Vol. 2).
- Cassini, J. De la carte de la France et de la perpendiculaire a la méridienne de Paris [The map of France and the perpendicular to the meridian of Paris]. Mémoires de l'Académie Royale des Sciences de Paris 1733. 1735: 389–405 (French).
- Cayley, A. On the geodesic lines on an oblate spheroid. Philosophical Magazine (4th ser.). 1870, 40: 329–340. doi:10.1080/14786447008640411 (不活躍 2015-05-11).
- Chasles, M. Sur les lignes géodésiques et les lignes de courbure des surfaces du second degré [Geodesic lines and the lines of curvature of the surfaces of the second degree]. Journal de Mathématiques Pures et Appliquées. 1846, 11: 5–20 (French). 參數
|trans_title=
值左起第49位存在換行符 (幫助) - Christoffel, E. B. Allgemeine Theorie der geodätischen Dreiecke [General theory of geodesic triangles]. Abhandlungen Königlichen Akademie der Wissenschaft zu Berlin. 1869: 119–176 (German).
- Clairaut, A. C. Détermination géometrique de la perpendiculaire à la méridienne tracée par M. Cassini [Geometrical determination of the perpendicular to the meridian drawn by Jacques Cassini]. Mémoires de l'Académie Royale des Sciences de Paris 1733. 1735: 406–416 (French).
- doi:10.1179/003962689791474267
{{cite doi}}已停用,請參見{{cite journal}}。 - Darboux, J. G. Leçons sur la théorie générale des surfaces [Lessons on the general theory of surfaces] 3. Paris: Gauthier-Villars. 1894. OCLC 8566228 (French). PDF.
- DLMF. Olver, F. W. J.; Lozier, D. W.; Boisvert, R. F.; Clark, C. W. , 編. NIST Handbook of Mathematical Functions. Cambridge Univ. Press. 2010. ISBN 978-0-521-19225-5. MR 2723248.
- Dupin, P. C. F. Développements de Géométrie [Developments in geometry]. Paris: Courcier. 1813. OCLC 560800801 (French).
- Ehlert, D. Methoden der ellipsoidischen Dreiecksberechnung [Methods for ellipsoidal triangulatioin] (技術報告). Reihe B: Angewandte Geodäsie, Heft Nr. 292. Deutsche Geodätische Kommission. 1993. OCLC 257615376 (German).
- Euler, L. Élémens de la trigonométrie sphéroïdique tirés de la méthode des plus grands et plus petits [Elements of spheroidal trigonometry taken from the method of maxima and minima]. Mémoires de l'Académie Royale des Sciences de Berlin 1753. 1755, 9: 258–293 (French). Figures.
- FAI. FAI Sporting Code (技術報告). Lausanne, Switzerland: Fédération Aéronautique Internationale. 2013. Section 7.3.1.1.
- Forsyth, A. R. Geodesics on an oblate spheroid. Messenger of Mathematics. 1896, 25: 81–124. PDF.
- Forsyth, A. R. Calculus of Variations. Cambridge Univ. Press. 1927. ISBN 978-1-107-64083-2. OCLC 250050479.
- Gauss, C. F. General Investigations of Curved Surfaces of 1827 and 1825. Translated by J. C. Morehead and A. M. Hiltebeitel. Princeton Univ. Lib. 1902 [1828]. OCLC 7824448. PDF. English translation of Disquisitiones generales circa superficies curvas (Dieterich, Göttingen, 1828).
- Halphen, G. H. Traité des Fonctions Elliptiques et de leurs Applications [A Treatise on Elliptic Functions and their Applications] 2. Gauthier-Villars. 1888. OCLC 25356730 (French). Chapter 6. PDF.
- Hammer, E. Gegenazimutale Projektion [Retroazimuthal projection]. Petermanns Geographische Mitteilungen. 1910, 56 (3): 153–155 + plate (German).
- Hansen, P. A. Geodätische Untersuchungen [Geodetic investigations]. Leipsig: Hirzel. 1865. OCLC 7687476 (German).
- Hart, A. S. Geometrical demonstration of some properties of geodesic lines. Cambridge and Dublin Mathematical Journal. 1849, 4: 80–84.
- Helmert, F. R. Mathematical and Physical Theories of Higher Geodesy 1. St. Louis: Aeronautical Chart and Information Center. 1964 [1880]. OCLC 17273288. English translation of Die Mathematischen und Physikalischen Theorieen der Höheren Geodäsie, Vol. 1 (Teubner, Leipzig, 1880).
- Hilbert, D.; Cohn-Vossen, S. Geometry and the Imagination. Translated by P. Nemenyi. New York: Chelsea. 1952. OCLC 301610346.
- doi:10.2307/1784715
{{cite doi}}已停用,請參見{{cite journal}}。 - Hutton, C. A Course of Mathematics in Three Volumes Composed for the Use of the Royal Military Academy. London. 1811: 115. OCLC 18031510.
- doi:10.1007/s00229-004-0455-z
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1080/14786442608674069
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1515/crll.1837.17.68
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1515/crll.1839.19.309
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1002/asna.18550411401
{{cite doi}}已停用,請參見{{cite journal}}。 - Jacobi, C. G. J. A. Clebsch , 編. Lectures on Dynamics. Translated by K. Balagangadharan. New Delhi: Hindustan Book Agency. 2009 [1866]. ISBN 978-81-85931-91-3. MR 2569315. OCLC 440645889. English translation of Vorlesungen über Dynamik (Reimer, Berlin, 1866). Errata.
- Jacobi, C. G. J. Über die Curve, welche alle von einem Punkte ausgehenden geodätischen Linien eines Rotationsellipsoides berührt [The envelope of geodesic lines emanating from a single point on an ellipsoid]. K. T. W. Weierstrass (editor) (編). Jacobi's Gesammelte Werke 7. Berlin: Reimer: 72–87. 1891. OCLC 630416023 (German). Op. post., completed by F. H. A. Wangerin. PDF. 參數
|trans_title=
值左起第46位存在換行符 (幫助) - Jekeli, C., Geometric Reference Systems in Geodesy, Ohio State Univ., 2012
- Karney, C. F. F. GeographicLib. Version 2009-03. 2009. The first implementation of geodesic routines in Geographiclib.
- Karney, C. F. F. Geodesics on an ellipsoid of revolution. 2011. arXiv:1102.1215v1 [physics.geo-ph]. Errata.
- doi:10.1007/s00190-012-0578-z
{{cite doi}}已停用,請參見{{cite journal}}。 - Karney, C. F. F. GeographicLib. Version 1.38. 2014.
- doi:10.1109/TAP.1986.1143838
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1007/BF02521679
{{cite doi}}已停用,請參見{{cite journal}}。 - Klingenberg, W. P. A. Riemannian Geometry. de Gruyer. 1982. ISBN 978-3-11-008673-7. MR 0666697. OCLC 8476832.
- doi:10.1007/BF01390041
{{cite doi}}已停用,請參見{{cite journal}}。 - Krakiwsky, E. J.; Thomson, D. B., Geodetic position computations (PDF), Dept. of Geodesy and Geomatics Engineering, Lecture Notes (39), Fredericton, N.B.: Univ. of New Brunswick, 1974, Bibcode:1974gpc..book.....K
- Kummell, C. H. Alignment of curves on any surface, with special application to the ellipsoid. Bulletin of the Philosophical Society of Washington. 1883, 6: 123–132. PDF.
- Laplace, P. S. Treatise on Celestial Mechanics 1. Translated by N. Bowditch. Boston: Hillard, Gray, Little, & Wilkins. 1829 [1799a]. OCLC 1294937. Book 1, § 8.
- Laplace, P. S. Traité de Mécanique Céleste [Treatise on Celestial Mechanics] 2. Paris: Crapelet. 1799b: 112. OCLC 25448952 (French).
- doi:10.7848/ksgpc.2011.29.4.329
{{cite doi}}已停用,請參見{{cite journal}}。 - Legendre, A. M. Analyse des triangles tracées sur la surface d'un sphéroïde [Analysis of spheroidal triangles]. Mémoires de l'Institut National de France. 1806, (1st semester): 130–161 (French).
- Legendre, A. M. Exercices de Calcul Intégral sur Divers Ordres de Transcendantes et sur les Quadratures [Exercises in Integral Calculus]. Paris: Courcier. 1811. OCLC 312469983 (French).
- Levallois, J. J.; Dupuy, M. Note sur le Calcul des Grandes Géodésiques (技術報告). Paris: Institut Géographique National. 1952. Chapter 2.
- Liouville, J. Sur quelques cas particuliers où les équations du mouvement d'un point matériel peuvent s'intégrer [Special cases where the equations of motion are integrable]. Journal de Mathématiques Pures et Appliquées. 1846, 11: 345–378 (French).
- Lyusternik, L. Shortest Paths: Variational Problems. Popular Lectures in Mathematics 13. Translated by P. Collins and R. B. Brown. New York: Macmillan. 1964. MR 0178386. OCLC 1048605. Translation from Russian of Кратчайшие Линии: Вариационные Задачи (Moscow, 1955).
- Lyusternik, L.; Schnirelmann, L. Sur le problème de trois géodésiques fermées sur les surfaces de genre 0 [The problem of three closed geodesics on surfaces of genus 0]. Comptes Rendus de l'Académie des Sciences de Paris. 1929, 189: 269–271 (French).
- doi:10.1002/asna.18550422201
{{cite doi}}已停用,請參見{{cite journal}}。 - Mathar, R. J. Geodetic line at constant altitude above the ellipsoid. 2007. arXiv:0711.0642 [math.MG].
- Monge, G. Sur les lignes de courbure de la surface de l'ellipsoïde [On the lines of curvature on the surface of the ellipsoid]. J. Liouville (editor) (編). Application de l'Analyse à la Géometrie 5th. Paris: Bachelier: 139–160. 1850 [1796]. OCLC 2829112 (French). Figures.
- doi:10.1175/1520-0485(1989)019.3C1765:GOWAAM.3E2.0.CO;2
{{cite doi}}已停用,請參見{{cite journal}}。 - National Geodetic Survey. Geodesic Utilities: Inverse and Forward. Version 3.0. 2012.
- Newton, I. The Mathematical Principles of Natural Philosophy. Translated by A. Motte. New York: Adee. 1848 [1687]. Book 3, Proposition 19, Problem 3, pp. 405–409.
- Oriani, B. Elementi di trigonometria sferoidica, Pt. 1 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1806, 1 (1): 118–198 (Italian).
- Oriani, B. Elementi di trigonometria sferoidica, Pt. 2 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1808, 2 (1): 1–58 (Italian).
- Oriani, B. Elementi di trigonometria sferoidica, Pt. 3 [Elements of spheroidal trigonometry]. Memorie dell'Istituto Nazionale Italiano. 1810, 2 (2): 1–58 (Italian).
- doi:10.1002/asna.18260043201
{{cite doi}}已停用,請參見{{cite journal}}。 - Oriani, B. Nota aggiunta agli elementi della trigonometria sferoidica [Note added to the elements of spheroidal trigonometry]. Memorie dell'Imperiale Regio Istituto del Regno Lombardo-Veneto. 1833, 4: 325–331 (Italian).
- doi:10.2478/jogs-2013-0007
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.2478/jogs-2013-0028
{{cite doi}}已停用,請參見{{cite journal}}。 - Pittman, M. E. Precision direct and inverse solutions of the geodesic. Surveying and Mapping. 1986, 46 (1): 47–54.
- doi:10.2307/1986219
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1007/BF02527187
{{cite doi}}已停用,請參見{{cite journal}}。 - Rapp, R. H., Geometric geodesy, part I, Ohio State Univ., 1991
- Rapp, R. H., Geometric geodesy, part II, Ohio State Univ., 1993
- RNAV. Order 8260.54A, The United States Standard for Area Navigation (PDF) (技術報告). Washington, D.C.: U.S. Federal Aviation Administration. 2007. Appendix 2.
- doi:10.1179/003962609X451663
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1007/BF02522166
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1007/BF02521087
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1080/10586458.2003.10504515
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1179/003962606780732100
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1061/(ASCE)SU.1943-5428.0000061
{{cite doi}}已停用,請參見{{cite journal}}。 - doi:10.1061/(ASCE)0733-9453(2005)131:1(20)
{{cite doi}}已停用,請參見{{cite journal}}。 - Thomas, P. D. Spheroidal Geodesics, Reference Systems, & Local Geometry (技術報告). U.S. Naval Oceanographic Office. 1970. SP-138.
- UNCLOS. A Manual on Technical Aspects of the United Nations Convention on the Law of the Sea, 1982 (PDF) (技術報告) 4th. Monaco: International Hydrographic Bureau. 2006.
- doi:10.1179/sre.1975.23.176.88
{{cite doi}}已停用,請參見{{cite journal}}。 - Vincenty, T. Geodetic inverse solution between antipodal points (PDF) (技術報告). DMAAC Geodetic Survey Squadron. 1975b [2011-07-28].
- Vincenty, T.; Bowring, B. R. Application of three-dimensional geodesy to adjustments of horizontal networks (PDF) (技術報告). NOAA. 1978. NOS NGS-13.
- doi:10.1016/j.physd.2011.11.010
{{cite doi}}已停用,請參見{{cite journal}}。 - Weierstrass, K. T. W. Über die geodätischen Linien auf dem dreiaxigen Ellipsoid [Geodesic lines on a triaxial ellipsoid]. Monatsbericht Königlichen Akademie der Wissenschaft zu Berlin. 1861: 986–997 (German). PDF.
External links
- Online geodesic bibliography, approximately 180 books and articles on geodesics on ellipsoids together with links to online copies.
- Implementations of Vincenty (1975a) for oblate ellipsoids:
- NGS implementation, includes modifications described in Vincenty (1975b).
- NGS online tools.
- Online calculator from Geoscience Australia.
- Javascript implementations of solutions to direct problem and inverse problem.
- Implementation of Karney (2013) for ellipsoids of revolution in Geographiclib (Karney 2014):
- GeographicLib web site for downloading library and documentation.
- GeodSolve(1), man page for a utility for geodesic calculations.
- An online version of GeodSolve.
- Planimeter(1), man page for a utility for calculating the area of geodesic polygons.
- An online version of Planimeter.
- geod(1), man page for the PROJ.4 utility for geodesic calculations.
- Javascript utility for direct and inverse problems and area calculations.
- Drawing geodesics on Google Maps.
- Matlab implementation of the geodesic routines (used for the figures for geodesics on ellipsoids of revolution in this article).
- The first description of the geodesic algorithms from (Karney 2009).
- Geodesics on a triaxial ellipsoid: