The Barycentric Coordinates Solution to the Optimal Road Junction Problem

January, 1999, vol.10 no.1

The Barycentric Coordinates Solution to the Optimal Road Junction Problem

Francis E. Greulich
University of Washington
Seattle, WA, USA

The author is a Professor of Forestry, Department of Forest Management and Engineering, College of Forest Resources.

ABSTRACT

The road junction location problems, first posited by Fermat and later generalized by Simpson, is a fundamental component of optimal network design. The barycentric resection formulas of plane surveying provide a solution of elegant simplicity to this problem. Prerequisite junction point angles for the application of the resection formulas are obtained directly from Launhardt's original analytical development of this fundamental problem in route location.

Keywords:Weber problem, network optimization, transportation system design.

BACKGROUND

Krarup and Pruzan [9] give a brief history of the Fermat distance minimization problem. They also discuss its subsequent generalization by Simpson [18] into its weighted distance form. Krarup and Pruzan refer to this latter form of the problem as the Weber problem of optimal factory location. Unfortunately the precursory contribution of professor Launhardt to the analytical solution of this particular problem [11] is overlooked in their review. Launhardt's originative work is however suitably acknowledged and described by Mosler [14]. A little known English translation of Professor Launhardt's publication is also available [12]. The content and scope of this English translation are augmented by additional material taken from Launhardt's subsequent lecture notes and publications.

A recent publication by Hu and Kuang [6] brought the three point resection problem of plane surveying to the attention of the author. A variety of methods may be used to solve this particular problem and examples are typically provided in surveying textbooks. Of particular interest in the use of barycentric coordinates in a calculating procedure sometimes referred to as the Tienstra method [3,16].

Professor J.M. Tienstra (1895-1951) was a professor and director of the Geodetic Institute of the Technical University at Delft in the Netherlands. Professor Tienstra taught the use of the barycentric formulas in solving the three point problem to his many students. It seems most probable that his name became attached to the procedure for this reason [1]. It is clear however that these general formulas were developed at a much earlier date. The earliest development that the author has been able to find is a 1889 paper by Neuberg and Gob [15]. It is quite possible however that earlier work may be found since Möbius published his seminal text on barycentric coordinates in 1827 [13]. Precisely when and by whom these barycentric formulas were first applied to the three point problem of surveying is still an open question.

The barycentric formulas provide a quick solution to the resection problem illustrated in Figure 1. Given known plane coordinates of its three vertices the interior angles, O₁, of the triangle may be found using the Law of Cosines after first calculating the side lengths. The angles, a_i, around an occupied interior point are measured directly in the field and (x,y)-coordinates of the occupied point may be calculated using eqs. 1 and 2.

In a previous Journal publication [5] the author presented a solution procedure for the optimal road junction problem of Launhardt. Included in this procedure was a closed form solution to junction point coordinates (the closed form is quite lengthy and for this reason it was left to the interested reader to make the straight forward substitutions). While the results presented in that previous paper are correct the author here wishes to suggest a new, exceedingly brief and elegant calculating formula for the junction point coordinates based on the barycentric formulas.

EMENDED SOLUTION

The barycentric formulas can be directly applied to the optimal junction point problem. The interior angles of the location triangle are readily calculated as described above. The junction point angles, a_i, in this application of the barycentric formulas come from Launhardt's cost triangle where they are calculated as the supplements of the interior angles (eqs. 10 of Table 1 in 5]). Very convenient calculating equations (eqs. 3) for optimal junction point coordinates may be easily developed using the barycentric formulas for the resected point and Launhardt's optimal junction point angles.

These last two formulas for the optimal location of the junction point are now applied to the illustrative problem originally stated by Launhardt [12] and only recently fully solved using analytical methods [5]. In preliminary steps designed to rule out the location triangle vertices as possible optimal road junction locations the variables listed in Table 2 were calculated. These values can now also be used to immediately find the optimal interior point location, viz., (8.408, 2.257). It should be noted that this answer is wholly consistent with the author's previously published analytical results which, for purposes of comparison with Launhardt's work, only listed optimal road segment lengths. Nevertheless the solution developed via the barycentric formulas represented a computationally efficient emendation of the previously proposed calculating formulas for optimal junction point placement [5].

Table 1. Listing of formulas used in this paper. The notation follows that of a previous paper [5].

Display large image of Table 1

Table 2. Calculated values for Launhardt's example.

J₁ = -244.00	K₁ = -109.48	A_t = 43.64	G₁ = -19476.
J₂ = 44.00	K₂ = -244.30	A_c = 60.24	G₂ = -8009.
J₃ = -206.00	K₃ = -88.52		G₃ = -16272.

Table 3. The Hurter-Martinich example.

k₁ = 300.00	(x₁, y₁) = (0,0)
k₂ = 155.00	(x₂, y₂) = (10, 0)
k₃ = 340.00	(x₃, y₃) = (0, 10)

Rosing [17] when considering problems of this general type states that "the Weiszfeld algorithm [21], as modified by Kuhn and Kuenne [10] seems to be the best [solution] method". An algorithm of this class (the hyperboloid approximation method) was used by Hurter and Martinich [7] to solve the economic location problem reproduced in Table 3. Hurter and Martinich conclude, after numerous iterations of the algorithm, that "the optimal solution is actually (1.04, 3.13) with C*=4822.86". In point of fact the exact optimal solution, here given to four decimal places, is readily found by the barycentric formulas to be (1.0486, 3.1496) with C*=4822.98 at the optimal point. Not only is their estimated point, found after considerable computational effort, not optimal but the stated cost at that point is also in error; it is actually 4822.99 at their indicated "optimal" location.

The difficulties illustrated by this example are not unusual. Krarup and Pruzan [9] in fact remark that convergence problems are commonly encountered with iterative algorithms of this particular design.

Motivated by this general lack of accuracy in existing solution procedures Tellier [20] developed a set of equations which when sequentially solved can also provide the basis for an exact solution for junction point coordinates. While Tellier's procedure renders requisite accuracy it lacks the elegant simplicity, insightful structure and computational convenience of the barycentric formulas. It should be noted that by these three criteria the (*x, *y)-coordinate formulas provided by Greulich [5] are of similar lesser preference.

POSTSCRIPT

The interesting early history of this particular resection problem has been recounted by Bradley [4]. Bradley cites published trigonometric solutions to the three point surveying problem dating from as early as 1617 [19]. Alternative derivations of the barycentric formulas may be found in articles by Allan [2] and Klinkenberg [8]. The possibility of applying these procedures developed in the context of land surveying to the economic location problem appears to have gone unnoticed until now however.

ACKNOWLEDGMENT

The author would like to thank Arthur L. Allan, Emeritus Reader in Surveying, University College, London, and author of the cited surveying text, for his kind assistance in tracing early work on the barycentric formulas.

REFERENCES

[1] Allan, Arthur L. 1997. Personal correspondence.
[Return to text]

[2] Allan, Arthur L. 1975. "A proof of the barycentric resection formulae". Survey Review XXIII (177):106-108.
[Return to text]

[3] Allan, Arthur L., J.R. Hollwey and J.H.B. Maynes. 1968. Practical Field Surveying and Computations. American Elsevier Publishing Co., Inc., New York. 689 p.
[Return to text]

[4] Bradley, A.D. 1972. "The three-point problem". The Mathematical Teacher LXV (8):;703-706.
[Return to text]

[5] Greulich, F.E. 1995. "Road network design: optimal economic connection of three horizontal control points on flat, uniform terrain". Journal of Forest Engineering 7(1):73-82.
[Return to text]