Campus Map in Android App

This article has been translated from its original publication at https://habr.com/ru/articles/729650/

Greetings, I'm Leonid Solyanoy, an Android developer at UMNO.Digital, and today I'd like to present my personal project.

During my first year at university, I developed a mobile app aimed at providing schedule information. Over the course of three years, the application has evolved with the addition of new features, garnering a daily user base of over 5,000 students.

However, one vital element was missing: a comprehensive campus map. With a sprawling campus encompassing 25 buildings, locating the correct auditorium on the first attempt proved to be a daunting task. The existing website only provided static images displaying building numbers, leaving students to grapple with questions like "Where can I find room 24b-456?" and "How do I navigate there?". Such uncertainties often resulted in students arriving late to their classes. Considering these challenges, the implementation of an interactive map became imperative — a solution that would be readily available to students could solve numerous similar problems.

Although there were available libraries designed for this specific purpose, they typically came with a hefty price tag. Considering that my application would not generate any revenue, I made a resolute choice to develop something from scratch.

In this article, I will provide an in-depth explanation of the process I undertook to create personalized maps and package them into an Android library.

Concept Overview

The main objective is to assist students in navigating the campus and finding the shortest path to their classrooms. The map should be seamlessly integrated into the application and be capable of independent updates. Otherwise, users would only receive the updated map version after verifying and updating the application through the store.

Let’s establish the necessary map conditions based on these requirements,:

Displaying the precise locations of the classrooms.
Constructing and illustrating the optimal routes for users.
Creating the map using a dedicated module.
Hosting the map on a separate server to facilitate swift updates.

Now that we have outlined the key considerations, we can proceed with the implementation phase.

Deconstructing The Map Into Components

To display the institute's map, it is sufficient to include roads and buildings as the primary objects to be displayed. These elements form the foundation of the map representation.

Roads:

Vary in width to accommodate different types of traffic.
Some roads are designated for pedestrian use only, although they are still depicted on the map to enhance clarity.
Not all roads are equal, as certain paths hold higher priority or significance than others.

By combining these factors, we establish a comprehensive road model description that serves as a framework for the map's depiction:

Buildings introduce a more intricate aspect to the map design.

Navigating within buildings involves specifying the number of floors, positions of stairs, entrances, classrooms, and room pathways.
Service buildings, however, are displayed for clarity without requiring detailed room layouts.
Building entrances are determined by the floor parameter rather than the entire building, accommodating cases where entrances may exist on multiple floors due to slopes.
The staircase provides access only to the floors it connects.

Building model:

Buildings contain a set of points describing their contour, a set of floors, and a set of stairs.

Floor model:

The floors of the building consist of rooms, walls, connecting routes, and a list of entrances to the building.

Staircase model:

The stairs are defined by their position within the building and the list of floors from which they can be accessed.

Overall, a set of models is utilized to effectively describe a wide range of rooms. The complete scheme can be summarized as follows:

There is one remaining component, the geo list, which associates the drawn scheme with geodetic coordinates. This allows the diagram to display real-world geometry or the user's position, but more on that below.

The RM prefix in the name of all objects can be subtracted to ensure code compatibility with the library. This approach simplifies the search for classes within our library and helps avoid naming conflicts with user-defined classes, as someone might inadvertently choose the same name for their class as one of ours.

Designing A Schema

I wrote a simple editor using Qt to modify the schematic. The editor helps modify the model's fields and arrange objects on the map in accordance with user preferences. While the editor may not be the most polished or refined, its primary function is to swiftly prepare the data so that it can be displayed in the app.

In the editor, we recreate the schematic based on the map and transmit it to the server in JSON format, associating it with the map ID for storage. The application retrieves the JSON data and renders the schematic accordingly. While it would be beneficial to obtain data from OpenStreetMap (OSM) in the future to eliminate the need for manual map drawing, the editor remains essential for accurately depicting interior rooms and their arrangements.

Exploring Mobile Library Development

At this stage, we have a territory map represented as models, which we draw using the editor and retrieve from the server. The map is implemented as a custom View element. When creating a MapView, a request is made to the server through Retrofit.

Now the question arises: How do we efficiently render the map within the application? Considering the large amount of data involved, it is crucial to ensure that the map remains responsive. I have considered two options: rendering the map using Canvas or OpenGL. However, the optimal solution lies somewhere in between.

To address this, the map is divided into two layers. The first layer handles the rendering of buildings and roads, utilizing OpenGL for efficient drawing. The second layer consists of markers and labels, which are rendered using Canvas.

The diagram above provides a simplified representation of the library's architecture. Initially, we fetch a map object from the server, which is then partially transformed into a suitable format for rendering via OpenGL. This transformed data, along with shaders, is passed to GLRender. The GLRender component is responsible for displaying the primary elements of the map, such as roads, buildings, and building floors, if required.

In addition to GLRender, Canvas renders supplementary elements on top of the renderer. This includes markers and a predetermined route.

Drawing The First Layer

OpenGL displays only simple objects: triangles and lines, which also consist of triangles. Consequently, the objects on the map will be divided into these primitives.

Buildings

Buildings are defined as a collection of points that are added to a polygon. To facilitate rendering, the polygon is divided into triangles. For this purpose, I utilized a basic triangulation algorithm known as "ear clipping"

If the number of vertices in the polygon is less than or equal to 3, the partitioning process is considered complete.

The algorithm follows these steps:

Select the first vertex as the current vertex (N).
If it is not possible to draw a diagonal from the current vertex (N) to vertex N+2 within the polygon, and vertex N+1 is not convex (determined by performing a left turn check), proceed to the next vertex in the polygon and repeat this step until a suitable vertex is found.
"Cut off" the triangle formed by the current vertex (N), vertex N+1, and vertex N+2 from the polygon, resulting in one less vertex in the remaining polygon.
Return to step 1 and continue until the entire polygon is triangulated.

The left turn check is performed as follows:

The Triangulation Algorithm:

As a result, we obtain a list of triangles that can be rendered by OpenGL. It's important to note that the algorithm used for triangulation is not optimal and imposes certain limitations on the shapes of buildings. One significant constraint is that polygons with cutouts cannot be properly rendered.

Roads

While roads can be initially drawn using lines, this approach presents several challenges:

Wide lines will reveal the underlying triangles used for rendering.
When scrolling the map, the triangles may appear to jump from side to side.
Sharp corners at road junctions will be visible.

For this reason, I decided to manually divide the roads into triangles. This approach eliminates the aforementioned problems. The triangulation process for a road segment involves the following steps:

Take the vector representing the road segment originating from the starting point and multiply it by a factor to obtain a vector with a length equal to half the width of the road.
Rotate the vector by 90 degrees and take the end point of the resulting vector.
Rotate the vector by an additional 180 degrees and once again take its end point.
Repeat the same operations with the end point of the road segment.
Combine the resulting four points to form two triangles.

By carefully following these steps, we can ensure that the roads are represented by smooth, visually appealing triangles without the previously mentioned issues.

Rotate the vector as follows:

By rotating the vector we get two triangles that make up the road rectangle:

As a result, the road segments were divided into rectangles. However, it became evident that there were gaps at road junctions. Considering this issue, we introduced additional triangles to fill these gaps, but only when the roads meet at a significantly large angle.

This is the achieved outcome: the application quickly renders all the roads and buildings. The ability to display the schematic of an entire city is a notable accomplishment.

The second layer of the map focuses on rendering dynamically changing information, such as markers, captions for classrooms and rooms, and icons. Utilizing OpenGL for drawing a large number of objects in this layer can be development-intensive. In order to resolve this, we leverage the power of Canvas. By overriding the onDraw method in Map View, we can efficiently draw these additional elements using regular shapes.

The second map layer

The second layer focuses on rendering dynamically changing information, such as markers, captions for rooms, and icons. Using OpenGL for drawing a large number of objects in this layer can be development-intensive. As a solution to this, we leverage the power of Canvas. By overriding the onDraw method in Map View, we can efficiently draw these additional elements using regular shapes.

Now we face the challenge of translating coordinates between OpenGL and Canvas. In OpenGL, screen coordinates are typically represented on a scale of -1 to 1, while in Canvas, the coordinate system ranges from 0 to the width of the canvas (which depends on the screen width). Consequently, we need to transform the coordinates of points from the first layer to align with the coordinate system used in the second layer.

In the implementation, you will notice that we retrieve the camera and zoom positions from the render layer. This is necessary because OpenGL operates in its own thread and is independent of the rendering of the second layer. As a result, when scrolling or zooming the map, misalignment between the layers may occur. To fix this problem, I have established a connection between the layers using the aforementioned function. By retrieving the latest coordinates from the first layer, the second layer can be drawn synchronously, ensuring proper alignment between the two layers.

With the implementation described above, we have the flexibility to draw any additional elements on top of the map. As shown in the screenshot, we can overlay diagrams and markers, allowing for further customization and enhanced visual representation.

Route search

To complete the model, we need to incorporate the functionality of calculating routes from one point to another. All roads on the map are connected and form a weighted graph. To achieve this, I have implemented the A star algorithm, which efficiently calculates paths on large graphs. When calculating routes, it is important to consider all the roads and paths within buildings. I combine all the roads into a single list and begin the pathfinding process.

Simply finding the shortest route is not sufficient, as certain paths may be less desirable. For instance, there may be a choice between taking a narrow path between fences or walking along a larger street, even if it takes slightly longer. Directing people through narrow passages is not always the best option, so we need additional parameters to suggest a more pleasant route.

To determine the optimal route, the code incorporates a heuristic function that considers factors beyond just distance. This function evaluates the proximity to the endpoint of the route, enabling the algorithm to determine the optimal direction of travel. By considering these factors, we can provide users with a more favorable and enjoyable route suggestion.

The heuristic function plays a crucial role in estimating the time it will take for pedestrians to reach their destination. By considering the road conditions, such as the status or desirability of each road, the function applies a coefficient to the estimated travel time. This approach allows us to prioritize and lay the route predominantly along the green paths, which have been identified as more desirable.

Finish Line

To establish a connection between the schematic coordinates and real-world geographic coordinates, we utilize an array of geopoints. Throughout the process of describing the models, I mentioned the geotags, which are typically represented as latitude and longitude values. However, the schematic is drawn using rectangular coordinates with the origin at zero.

To bridge this gap, I implemented a method to correlate the positions on the diagram with their corresponding geographical coordinates. By selecting several reference points and mapping their positions both on the schematic and in terms of geographical coordinates, we establish a conversion mechanism. This allows us to accurately convert between the two coordinate systems, enabling seamless integration of the scheme with real-world geographic locations.

To convert geographic coordinates to rectangular (from WGS84 to CK-42), we use the Gauss-Kruger method:

It remains to fit the obtained coordinates into the coordinates of the scheme. This can be done simply through the similarity:

It turns out to be a point on the diagram recorded in real geographical coordinates, and we can finish our work there.

The result?

Now, students can simply click on the name of a classroom or facility associated with a subject and effortlessly navigate to their destination. Whether it's finding the right auditorium or locating a specific dining room, the app provides a convenient solution. I believe that soon, thousands of students will have access to these features, and they will be put to the test in real-world scenarios.

The development process itself was both challenging and rewarding, filled with a range of emotions. The potential applications of this solution are vast, extending beyond the realm of educational institutions. Various indoor-focused businesses, from airports to warehouse management applications, can benefit from incorporating similar schematics into their solutions.