# 18 Triangulation Algorithms for 2D Positioning (also known as the Resection Problem): benchmarking, software, source code in C, and documentation

Scientific paper available in PDF here [IEEE] or here; HTML version of the article here
Keywords: 2D positioning, triangulation, mobile robot positioning, algorithms, benchmarking, software, C source code, documentation, ToTal algorithm
This page complements the paper “A New Three Object Triangulation Algorithm for Mobile Robot Positioning”, published in IEEE Transactions on Robotics (see [15]); this algorithm was introduced in [14] and used for the Eurobot contest in an original setup (see [16]). It is important to note that the “three object triangulation problem” is also known as the “three point resection problem” in the surveying engineering research area.
We provide the C source code, programs, documentation, as well as the instructions to reproduce all the results given in the paper. In Section 2↓, we explain how to download and use the program. See Section 4↓ for the command lines used to generate the graphics and Section 1↓ for the command lines used to run the benchmark, reproduced in Table 1↓. We also remind our algorithm ToTal in Section 3↓.

# 1 Benchmarks

The last column of the following table provides the command and arguments to obtain the execution times of the different algorithms:
 Algorithm + × ⁄ √(x) trigo time (s) † Command line [14, 15] ToTal 1 30 17 2 0 2 0.163 ./triangulation -t3 -n1000000 -m1 [11] Ligas 1 29 22 2 0 2 0.171 ./triangulation -t3 -n1000000 -m18 [7] Font-Llagunes 1 23 17 2 0 5 0.223 ./triangulation -t3 -n1000000 -m3 [12] Cassini 2 19 8 3 0 4 0.249 ./triangulation -t3 -n1000000 -m22 [2] Cohen 1 37 15 3 2 4 0.272 ./triangulation -t3 -n1000000 -m10 [1] Easton 2 22 24 1 0 5 0.298 ./triangulation -t3 -n1000000 -m7 [4] McGillem 1 37 18 5 2 8 0.340 ./triangulation -t3 -n1000000 -m6 [6] Hmam 2 29 11 3 3 9 0.428 ./triangulation -t3 -n1000000 -m8 [2] Cohen 2 26 11 3 2 11 0.437 ./triangulation -t3 -n1000000 -m9 [10] Esteves 2 43 14 2 2 11 0.471 ./triangulation -t3 -n1000000 -m2 [12] Collins 2 34 10 2 2 11 0.485 ./triangulation -t3 -n1000000 -m21 [4] McGillem 2 29 9 3 2 11 0.501 ./triangulation -t3 -n1000000 -m5 [12] Kaestner 2 28 10 3 2 11 0.504 ./triangulation -t3 -n1000000 -m20 [13] Tsukiyama 1 52 22 3 5 14 0.596 ./triangulation -t3 -n1000000 -m12 [5] Casanova 1 52 21 4 5 14 0.609 ./triangulation -t3 -n1000000 -m4 [9] Tienstra 2 33 18 8 3 9 0.640 ./triangulation -t3 -n1000000 -m17 [8] Font-Llagunes 1 62 25 6 1 8 0.648 ./triangulation -t3 -n1000000 -m19 [3] Madsen 2 38 24 5 3 15 0.707 ./triangulation -t3 -n1000000 -m14
For 106 executions on an Intel(R) Core(TM) i7 920 @ 2.67GHz.
1 Geometric circle intersection 2 Trigonometric solution
Table 1 Comparison of various triangulation algorithms to our ToTal algorithm (see [15]).

# 2 Programs

Follow this link to get the programs and C source code [triangulation.zip]. The package contains programs that you can directly use:
bin_win32/triangulation.exe for Windows users.
bin_i686/triangulation for Linux 32 bits users.
bin_x86_64/triangulation for Linux 64 bits users.

## 2.2 Run the program by yourself

To run the program, copy the appropriate program (depending on your platform) into your current directory and type:
```./triangulation
```
It generates a 201 × 201 grayscale PGM image named “map.pgm”, and a 201 × 201 color PPM image named “map.ppm”. These images are the ones shown in Fig. 2↓. It also generates the corresponding scale images named “scale.pgm”, and “scale.ppm”.

## 2.3 Compile the code by yourself.

Take a look at the Makefile. There is no external library needed to compile the code, so the compilation should be rather straightforward.

# 3 ToTal Algorithm

## 3.1 Description

Given the three beacon coordinates {x1,  y1}, {x2,  y2}, {x3,  y3}, and the three angles α1, α2, α3:
1. compute the modified beacon coordinates:
x1 = x1 − x2,  y1 = y1 − y2,  x3 = x3 − x2,  y3 = y3 − y2,
2. compute the three cot(.):
T12 = cot(α2 − α1),  T23 = cot(α3 − α2),  T31 = (1 − T12T23)/(T12 + T23)
3. compute the modified circle center coordinates:
x12 = x1 + T12 y1,  y12 = y1 − T12 x1,
x23 = x3 − T23 y3,  y23 = y3 + T23 x3,
x31 = (x3 + x1) + T31 (y3 − y1),
y31 = (y3 + y1) − T31 (x3 − x1),
4. compute k31:
k31 = x1x3 + y1y3 + T31(x1y3 − x3y1),
5. compute D (if D = 0, return with an error):
D = (x12 − x23)(y23 − y31) − (y12 − y23)(x23 − x31),
6. compute the robot position {xR,  yR} and return:
xR = x2 + (k31(y12 − y23))/(D),  yR = y2 + (k31(x23 − x12))/(D).
Algorithm 1 Final version of the ToTal algorithm.

## 3.2 The ToTal algorithm in C code

A version of ToTal in C is available: total.c.

## 3.3 The ToTal algorithm in Matlab/Octave code

A Matlab/Octave version is also available: triangulationToTal.m.

# 4 Simulations

To reproduce the figures given in the paper, run the command with the arguments as mentioned under each corresponding figure:

You are allowed to use the programs and the source code for educational purposes and for your own usage only.
Distribution or any form of commercial usage is strictly prohibited. Please contact the authors if you want to use the program or source code outside the scope of the authorized usage.

# References

[1] A. Easton, S. Cameron. A Gaussian Error Model for Triangulation-Based Pose Estimation Using Noisy Landmarks. IEEE Conference on Robotics, Automation and Mechatronics:1-6, 2006. URL http://dx.doi.org/10.1109/RAMECH.2006.252663.

[2] C. Cohen, F. Koss. A Comprehensive Study of Three Object Triangulation. Mobile Robots VII, 1831:95-106, 1992. URL http://dx.doi.org/10.1117/12.143782.

[3] C.B. Madsen, C.S. Andersen. Optimal landmark selection for triangulation of robot position. Robotics and Autonomous Systems, 23(4):277-292, 1998. URL http://dx.doi.org/10.1016/S0921-8890(98)00014-1.

[4] C.D. McGillem, T.S. Rappaport. A Beacon Navigation Method for Autonomous Vehicles. IEEE Transactions on Vehicular Technology, 38(3):132-139, 1989. URL http://dx.doi.org/10.1109/25.45466.

[5] E.Z. Casanova, S.D. Quijada, J.G. García-Bermejo, J.R.P. González. A New Beacon-based System for the Localization of Moving Objects. IEEE International Conference on Mechatronics and Machine Vision in Practice, 2002. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.1615.

[6] H. Hmam. Mobile Platform Self-Localization. Information, Decision and Control:242-247, 2007. URL http://dx.doi.org/10.1109/IDC.2007.374557.

[7] J.M. Font-Llagunes, J.A. Batlle. Consistent triangulation for mobile robot localization using discontinuous angular measurements. Robotics and Autonomous Systems, 57(9):931-942, 2009. URL http://dx.doi.org/10.1016/j.robot.2009.06.001.

[8] J.M. Font-Llagunes, J.A. Batlle. New method that solves the three-point resection problem using straight lines intersection. Journal of Surveying Engineering, 135(2):39-45, 2009. URL http://dx.doi.org/10.1061/(ASCE)0733-9453(2009)135:2(39).

[9] J.M. Porta, F. Thomas. Simple Solution to the Three Point Resection Problem. Journal of Surveying Engineering, 135(4):170-172, 2009. URL http://dx.doi.org/10.1061/(ASCE)0733-9453(2009)135:4(170).

[10] J.S. Esteves, A. Carvalho, C. Couto. Position and Orientation Errors in Mobile Robot Absolute Self-Localization Using an Improved Version of the Generalized Geometric Triangulation Algorithm. IEEE International Conference on Industrial Technology (ICIT):830-835, 2006. URL http://dx.doi.org/10.1109/ICIT.2006.372345.

[11] M. Ligas. Simple Solution to the Three Point Resection Problem. Journal of Surveying Engineering, 139(3):120-125, 2013. URL http://dx.doi.org/10.1061/(ASCE)SU.1943-5428.0000104.

[12] R. Burtch. Three point resection problem. Surveying Engineering Department, Ferris State University, 2005.

[13] T. Tsukiyama. Mobile Robot Localization from Landmark Bearings. World Congress on Fundamental and Applied Metrology:2109-2112, 2009. URL http://www.imeko.org/publications/wc-2009/IMEKO-WC-2009-TC17-084.pdf.

[14] V. Pierlot, M. Van Droogenbroeck, M. Urbin-Choffray. A new three object triangulation algorithm based on the power center of three circles. Research and Education in Robotics (EUROBOT), 161:248-262, 2011. URL http://hdl.handle.net/2268/89435.

[15] V. Pierlot, M. Van Droogenbroeck. A New Three Object Triangulation Algorithm for Mobile Robot Positioning. IEEE Transactions on Robotics, 30(3):566-577, 2014. URL http://dx.doi.org/10.1109/TRO.2013.2294061.

[16] V. Pierlot, M. Van Droogenbroeck. BeAMS: a Beacon based Angle Measurement Sensor for mobile robot positioning. IEEE Transactions on Robotics, 30(3):533-549, 2014. URL http://dx.doi.org/10.1109/TRO.2013.2293834.