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.

Keywords

• geopositioning
• graham scan algorithm
• moment centroid
• android phone