Improving the Android Geopositioning Accuracy Using Graham Scan Algorithm and Moment Centroid
Abstract
Geopositioning is the process of determining or estimating the geographic position of an object through the global positioning system (GPS). The calculations in geopositioning require measurements of distances or angles relative to known reference positions. In Android devices, achieving accuracy, speed, and power efficiency in geopositioning with GPS, cellular networks, and Wi-Fi can be challenging. This research aimed to improve the accuracy of the geopositioning process for cellular networks on Android devices through polygon triangulation using the Graham scan algorithm and determining a moment centroid for the improved estimation of geolocation data. The geolocation data were collected using an Android smartphone with a cellular network and disabled Wi-Fi. A filtering phase on the coordinates was established to obtain the closest distance coordinates from the other. The distances between each pair of coordinates were calculated using the haversine formula, and then the average distance of all pairs was calculated. Then, a polygon was formed by arranging the coordinates in a sequence, which was achieved using the Graham scan algorithm. After obtaining a set of triangles from the polygon triangulation results, the moment centroid of each formed triangle was determined. The centroid, as a result, was compared with another centroid calculation, the Lagrange interpolation polynomial. Based on the results obtained from quantifying the accuracy and precision using average Euclidean error (AEE) and root mean square error (RMSE), the coordinates derived from the moment centroid were more accurate and precise than the Lagrange interpolation polynomial.
References
M.J. Rycroft, “Understanding GPS. Principles and applications: Kaplan E. D. (ed.), 1996, 554 pp. Artech House, £75, hb, ISBN 0-89006-793-7,” J. Atmos. Sol. Terr. Phys., vol. 59, no. 5, pp. 598–599, Mar. 1997, doi: 10.1016/s1364-6826(97)83337-8.
R.J. Aughey, “Applications of GPS technologies to field sports,” Int. J. Sports Physiol. Perform., vol. 6, no. 3, pp. 295–310, Sep. 2011, doi: 10.1123/ijspp.6.3.295.
N. Lambrinos and F. Asiklari, “The introduction of GIS and GPS through local history teaching in primary school,” Eur. J. Geogr., vol. 5, no. 1, pp. 32–47, Mar. 2014.
K.M. Kafi and M.B.A. Gibril, “GPS application in disaster management: A review,” Asian J. Appl. Sci., vol. 4, no. 1, pp. 63–69, Feb. 2016.
S.B. Im, S. Hurlebaus, and Y.J. Kang, “Summary review of GPS technology for structural health monitoring,” J. Struct. Eng., vol. 139, no. 10, pp. 1653–1664, Oct. 2013, doi: 10.1061/(ASCE)ST.1943-541X.0000475.
M.R. Yousefi and A.M. Razdari, “Application of GIS and GPS in precision agriculture (a review),” Int. J. Adv. Biol. Biomed. Res., vol. 3, no. 1, pp. 7–9, Mar. 2015.
S. Lee, G. Tewolde, and J. Kwon, “Design and implementation of vehicle tracking system using GPS/GSM/GPRS technology and smartphone application,” in 2014 IEEE World Forum Internet Things (WF-IoT), 2014, pp. 353–358, doi: 10.1109/WF-IoT.2014.6803187.
P.K. Enge, “The global positioning system: Signals, measurements, and performance,” Int. J. Wirel. Inf. Netw., vol. 1, no. 2, pp. 83–105, Apr. 1994, doi: 10.1007/BF02106512.
A. Nait-Sidi-Moh, M. Bakhouya, J. Gaber, and M. Wack, Eds. Geopositioning and Mobility. London, England: Wiley-ISTE, 2013.
C.R. Rani et al., “Location based services in Android,” Int. J. Adv. Eng. Technol., vol. 3, no. 1, pp. 209–220, Mar. 2012.
A. Nadaf and B.K. Srinivas, “Android based fused location provider api for localization accuracy,” Int. J. Latest Trends Eng. Technol., vol. 8, no. 3, pp. 278–282, May 2017, doi: 10.21172/1.83.042.
N. Moayeri, C. Li, and L. Shi, “Indoor localization accuracy of major smartphone location apps,” in 2019 IEEE Wirel. Commun. Netw. Conf. (WCNC), 2019, pp. 1–8, doi: 10.1109/WCNC.2019.8885639.
M. Spreitzenbarth, S. Schmitt, and F. Freiling, “Comparing sources of location data from Android smartphones,” in Adv. Digit. Forensics VIII 8th IFIP WG 11.9 Int. Conf. Digit. Forensics, 2012, pp. 143–157, doi: 10.1007/978-3-642-33962-2_10.
Z. Farid, R. Nordin, and M. Ismail, “Recent advances in wireless indoor localization techniques and system,” J. Comput. Netw. Commun., vol. 2013, pp. 1–12, Sep. 2013, doi: 10.1155/2013/185138.
M. Werner, Indoor Location-Based Services: Prerequisites and Foundations. Cham, Switzerland: Springer, 2014.
H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of wireless indoor positioning techniques and systems,” IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.), vol. 37, no. 6, pp. 1067–1080, Nov. 2007, doi: 10.1109/TSMCC.2007.905750.
M. Bin Ismail et al., “Implementation of location determination in a wireless local area network (WLAN) environment,” in 2008 10th Int. Conf. Adv. Commun. Technol., 2008, pp. 894–899, doi: 10.1109/ICACT.2008.4493911.
“International Vocabulary of Metrology – Basic and General Concepts and Associated Terms (VIM) 3rd Edition,” International Organization of Legal Metrology, 2007.
S. Safavi and U.A. Khan, “Localization in mobile networks via virtual convex hulls,” IEEE Trans. Signal Inf. Process. Netw., vol. 4, no. 1, pp. 188–201, Mar. 2018, doi: 10.1109/TSIPN.2017.2673238.
R.E. Deakin, S.C. Bird, and R.I. Grenfell, “The centroid? Where would you like it to be be?” Cartography, vol. 31, no. 2, pp. 153–167, Dec. 2002, doi: 10.1080/00690805.2002.9714213.
Y. Sabri and N. El Kamoun, “A distributed method for localization in large-scale sensor networks based on Jarvis,” Int. J. Comput. Appl., vol. 165, no. 3, pp. 1–9, May 2017, doi: 10.5120/ijca2017913826.
S. Singh et al., “A novel framework to avoid traffic congestion and air pollution for sustainable development of smart cities,” Sustain. Energy Technol. Assess., vol. 56, pp. 1–9, Mar. 2023, doi: 10.1016/j.seta.2023.103125.
Y. Jiaxin et al., “Objectification of tooth-marked tongue in Chinese medicine based on morphological feature extraction,” Laser Optoelectron. Prog., vol. 59, no. 11, pp. 1–9, Jun. 2022, doi: 10.3788/LOP202259.1117001.
C. Na et al., “Intelligent interpretation of rock mass discontinuity based on three-dimensional laser point cloud,” Earth Sci., vol. 46, no. 7, pp. 2351–2361, Jul. 2021, doi: 10.3799/dqkx.2020.282.
M.R. Islam and J.M. Kim, “A centroid-GPS model to improving positioning accuracy for a sensitive location-based system,” in Ubiquitous Comput. Appl. Wirel. Sens., 2015, pp. 187–196, doi: 10.1007/978-94-017-9618-7_18.
M.M. Din, N. Jamil, and N.F.N.A. Aziz, “Adopting centroid and amended trilateration for better accuracy of range-based non-GPS localization,” in 2018 4th Int. Conf. Comput. Inf. Sci. (ICCOINS), 2018, pp. 1–6, doi: 10.1109/ICCOINS.2018.8510605.
N.M.S. Wibawa, I.M. Sukarsa, and I.K.A. Purnawan, “Correction position of coordinates from data GPS logger in Google maps by using lagrange interpolation method,” J. Theor. Appl. Inf. Technol., vol. 59, no. 2, pp. 263–268, Jan. 2014.
M. Horemuž and J.V. Andersson, “Polynomial interpolation of GPS satellite coordinates,” GPS Solut., vol. 10, no. 1, pp. 67–72, Feb. 2006, doi: 10.1007/s10291-005-0018-0.
M. Jang et al., “Improving positional accuracy using relative measurement between Android smartphones,” Sens. Mater., vol. 34, no. 1, pp. 349–366, Jan. 2022, doi: 10.18494/SAM3711.
L. Lee et al., “Comparison of accuracy and precision of GPS-enabled mobile devices,” in 2016 IEEE Int. Conf. Comput. Inf. Technol. (CIT), 2016, pp. 73–82, doi: 10.1109/CIT.2016.94.
G. Van Brummelen, Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry. Princeton, NJ, USA: Princeton Univ. Press, 2013.
G. Sharma, M.S. Singh, S.P. Aggarwal, and R. Romero-Andrade, “Integrated observations on crustal strain-ionosphere total electron content anomalies before the earthquake,” Acta Geophys., vol. 71, no. 3, pp. 1173–1185, Jun. 2023, doi: 10.1007/s11600-023-01030-7.
G.R. Anggani, A.Z. Arfianto, A. Arleiny, and B.T. Setiawan, “Ship collision realtime early warning system based on automatic identification system (AIS) data,” Indones. J. Eng. Res., vol. 3, no. 1, pp. 18–23, May 2023, doi: 10.11594/ijer.v3i1.42.
E. Wang et al., “Aircraft positioning accuracy evaluation using QAR data: A case study on four aircraft types,” J. Aeronaut. Astronaut. Aviat., vol. 55, no. 1, pp. 65–75, Mar. 2023, doi: 10.6125/JoAAA.202303_55(1).06.
R.L. Graham, “An efficient algorithm for determining the convex hull of a finite planar set,” Inf. Process. Lett., vol. 1, no. 4, pp. 132–133, Jun. 1972, doi: 10.1016/0020-0190(72)90045-2.
J. O’Rourke, “Polygon triangulation,” in Computational Geometry in C, 2nd ed. New York, NY, USA: Cambridge Univ. Press, 1998, pp. 1–43.
D. Eberly, “Triangulation by ear clipping,” Geometric Tools. Access date: 14-Oct-2023. [Online]. Available: http://www.geometrictools.com/
J.F. Oliveira et al., “Geometric and topological modelling of organs and vascular structures from CT data,” in Multi-Modality Imaging: Applications and Computational Techniques, M.A. de Souza, H.R. Gamba, and H. Pedrini, Eds., Cham, Switzerland: Springer, 2018.
C. Cai and Z. Tianlong, “An algorithm for triangulation applied to 3D GIS,” in 2010 Int. Conf. Comput. Appl. Syst. Model. (ICCASM 2010), 2010, pp. V9-146–V9-149, doi: 10.1109/ICCASM.2010.5623065.
C. Blut, T. Blut, and J. Blankenbach, “CityGML goes mobile: Application of large 3D CityGML models on smartphones,” Int. J. Digit. Earth, vol. 12, no. 1, pp. 25–42, 2019, doi: 10.1080/17538947.2017.1404150.
R.G. Budynas and J.K. Nisbett, Shigley’s Mechanical Engineering Design, 9th ed. New York, NY, USA: McGraw Hill, 2011.
F. Ayres and E. Mendelson, Theory and Problems of Differential and Integral Calculus, 3rd ed. New York, NY, USA: McGraw Hill, 1990.
Y. Lee and W. Lim, “Shoelace formula: Connecting the area of a polygon and the vector cross product,” Math. Teach., vol. 110, no. 8, pp. 631–636, Apr. 2017, doi: 10.5951/mathteacher.110.8.0631.
Geospatial Positioning Accuracy Standards Part 3: National Standard for Spatial Data Accuracy, FGDC-STD-007.3-1998, Subcommittee for Base Cartographic Data, Federal Geographic Data Committee, Virgina, USA, 1998.
© Jurnal Nasional Teknik Elektro dan Teknologi Informasi, under the terms of the Creative Commons Attribution-ShareAlike 4.0 International License.
1.png)
