Recently, we successfully finished the prototype phase on a project with the goal of developing a map tool similar to Google Maps for the Android platform. The initial use-case for the prototype was the following: Their employees regularly walk through remote regions with a map that contains location-specific information, observe the area and take notes that are relevant for their business goal. However, these areas often lack mobile internet, therefore an online solution like Google Maps was no option. We took up the challenge to find the best solution for our customer and within a few weeks built a prototype that solved two major technical challenges: How to integrate custom map-data into an Android app and how to make the app offline-usable.
Previously, my colleague Riina Pakarinen, who worked with me on the project, wrote an extensive article about solving the first challenge in her blog entry. Therefore, this article will only briefly recap that and then mainly focus on solutions for the second challenge.
Integrating custom map-data in your Android Application
With Zühlke experts in Geographic Information Systems, and the requirements given by our customer, we were able to evaluate different systems and decided to go with OpenStreetsMaps for Android (OSMdroid) which was a great decision. Within a few days, we were up and running, could display offline maps that our customer provided or online maps like Basemap (if a connection is available). OSMdroid has a look-and-feel which is very similar to Google Maps but is by itself not as extensive. However, there is a complementary bonus-pack which gives you KML-support, overlays, markers and many more features straight out of the box.
Making the app offline-usable
The next step was integrating the boundaries of certain areas into the map, so the user could click somewhere and get information about that particular area. This functionality is often referred to as Maps Engine and usually implemented on a server which computes the result and sends it back to the device. Since the app should work offline as well, we had to find another way.
A first attempt was to simply add the polygon boundaries as visible overlay to the map. We quickly realised, that this approach had significant drawbacks. Not only were those polygons always visible (regardless of the zoom-level) but after adding more than 100 areas of interest, the program became unresponsive, and the visual experience was terrible. When zooming out, only a big black blob of cluttered boundaries was displayed, which was simply unacceptable, especially given the requirement that more than 30.000 polygons should be available to the user.
There was only one way out of this dilemma: We had to implement the Maps Engine functionality on our own. Luckily, this problem is not new in the world of computer science and a lot of research (Guttman84, Beckmann90 and Sellis87) has been conducted to efficiently solve a multi-dimensional search in a large dataset and to efficiently test if a point lies within a polygon (which might have any shape and consist of over 100 points and even holes).
So we searched for implementations of an R-Tree in Java and found the Java Spatial Index library besides others. The library is free, works great and solved our problems with one severe limitation: All of the data had to be in the memory, which means they have to be loaded when the app starts and retained until the application stops. This led to one ugly and one bad thing: The ugly thing was that the app had to load the entire data from the SD-card upon start, which meant that the user had to wait about 30 seconds for a larger dataset, before he could start querying the app for areas. But the really troublesome thing tough was, that the app consumed a significant amount of memory, causing lags, app-freezes and ultimately app-crashes if the required amount of memory exceeded the device’s capacities.
A better solution
When searching for alternatives, we came across the R*-Module for SQLite which turned out to be exactly what we were searching for: A high-performance spatial index with a low memory-footprint, and an easy integration into our Java application. We were able to quickly put it into the app and moved the search to the R*-Tree in SQLite. With this solution, we are no longer limited by the available memory, there is no loading-time required each time the application starts and the end-user can start working right away. That made our customer and us very happy.
So the final work-flow is the following:
- Read in the polygon-data from an external source (e.g. a JSON-file, a KML-file or potentially any online source)
- Parse the data and write them into an SQLite database, where one table contains the approximated boundaries of each polygon. (The first two steps can of course be done in advance so any new device may receive the pre-processed database along with the offline map-data.)
- Upon clicking of the user, query the respective table in the database to obtain the candidate IDs of polygons that enclose the given coordinate.
- Load the points that correspond to those polygons from another table of the same database and check which of the candidates truly contains the given coordinate.
Currently this prototype is being tested by the end-users in the field to collect first impressions and generate new ideas for features yet to come. We are looking forward to their responses and future collaboration with our customer.