Campus map in Android application
Hello everyone, I’m Leonid Solyanoy, Android developer from @UMNODigital, and today I’ll talk about my home project.
Even in my first year, I started developing a mobile application for viewing the schedule. The application grew, new features appeared, and after 3 years it was used by 5 thousand students daily, but it lacked one important detail, namely the territory map. The institute is large, it has 25 buildings, and it is not easy to find the right audience the first time. And on the site only pictures with building numbers. Where is room 24b-456? How to get to it? This has to be figured out on the spot in front of the couple and possibly late for her. Similar cases can be listed for a long time, and all of them are solved by an interactive scheme that will always be at hand.
Such libraries already exist, but they all cost a lot of money, and my application does not bring money, so a strong-willed decision was made to do everything on our own.
In the article, before the screws, I’ll tell you how I made custom cards and wrapped them in their android library.
Briefly about the concept
We help students not to get lost and find the shortest path to the right audience. The developed scheme should be easily imported into the application and updated independently of it. Otherwise, the new version of the map will reach the user only after checking in the store and updating the application.
From here we formulate the conditions for the scheme. The schema must:
display the location of audiences;
build and show routes;
drawn using a separate module;
lie on a separate server for quick updates.
Finished with the conversations, now you can start working.
Breaking down the diagram into components
To display the scheme of the institute, it is enough to draw roads and buildings. These are all objects that will be displayed on the map.
Roads:
come in different widths;
not all can be walked on, but for the sake of clarity of the scheme, such roads are also shown;
not all are equal: some paths are prioritized over others.
Having collected the conditions, we get a road description model:
data class RMRoad(
val id: String = "",
val name: String = "",
val address: String = "",
var type: Int = 0,
val start: RMPoint,
val end: RMPoint,
var status: Int = 2,
var connectedRoad: List<String> = listOf(),
var floor: Int? = null,
)
With buildings, the story is more interesting.
For indoor navigation, we set the number of floors, the location of stairs, entrances, auditoriums and paths along which you can go to the rooms.
Some of the buildings, like outbuildings, are displayed for clarity and do not require drawing the location of the rooms.
The entrance to the building is a floor parameter, not the entire building, since the building can be on a slope, and the entrances can be on two floors.
The staircase does not connect all floors, but only those to which there is an exit from it.
Building model:
data class RMStructure(
val id: String,
val name: String?,
val address: String?,
var points: MutableList<RMPoint>,
val type: Int,
val floors: List<RMFloor>,
val stairs: List<RMStair>,
)Buildings contain a set of points that describe their outline, a set of floors and a set of stairs.
Floor model:
data class RMFloor(
val number: Int,
val doors: List<RMPoint>,
val rooms: List<RMRoom>,
val walls: List<RMWall>,
val roads: List<RMRoad>,
)
data class RMWall(
val start: RMPoint,
val end: RMPoint,
)
data class RMRoom(
val id: String,
val name: String,
val position: RMPoint,
) : SerializableEach floor has rooms, walls, as well as routes that connect them + a list of building entrances.
Stair Model:
data class RMStair(
val floors: List<Int>,
val position: RMPoint,
val type: Int,
)A staircase includes a position in the building and a list of floors from which it can be accessed.
In total, we have a set of models, which is enough to describe a large number of rooms. The whole scheme looks like this:
data class RMRoadMap(
val id: String,
val scale: Double,
val roads: List<RMRoad>,
val structures: List<RMStructure>,
val geo: List<RMGeoPoint>,
)The list was left without explanation. geo, it associates the drawn scheme with geodetic coordinates. The diagram will display real geotags or the user’s position, but more on that later.
Also, for all objects, you can subtract an increase in the name RMthis is done in order to move the code to the library, as this will simplify the search for classes of our library and eliminate conflicts in class names, because for any there will be at least one person who will try to name his class as well as one of ours .
Creating a schema
To edit the schema, I wrote a simple editor in Qt. There you can change the fields of models and arrange objects on the map in the way I need. It was made as a draft version, rather crookedly, its main goal is to quickly prepare data for display in the application.
In the editor, we redraw the diagram from the map and send it to the server in JSON format, where it is saved from the map id. The application receives the JSON and renders it. In the future, it would be great to get data from OSM (open street maps) so as not to manually redraw the map, but the editor is still needed to draw the interior.
Starting to think about a mobile library
At this stage, there is a scheme of the territory in the form of models, which we draw in the editor and receive 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.
But how to draw a map in the application? The data volumes are large, and the card should not slow down. I considered two options: rendering the map through Canvas and through OpenGL, but in the end the solution turned out to be in the middle. The map is divided into two layers, on the first layer houses and roads are displayed, and they are drawn through OpenGL, and on the second layer markers and labels are drawn through Canvas.
The picture above shows a simplified diagram of the library. We receive a map object from the server, partially convert it to the desired view for display through OpenGL and pass it to GLRender, which also receives shaders as input. GLRender renders the main part of the map: roads, buildings and building floors, if needed. Canvas draws additional elements on top of the render, such as markers and a laid route.
First layer render
OpenGL only renders simple objects: triangles and lines, which are also made up of triangles. Therefore, the objects on the map will be divided into these primitives.
Building
Buildings are written as points that form a polygon. We break it into triangles. To do this, I used the simplest triangulation algorithm – cutting off the ears:
If the number of vertices <= 3 splitting is complete
Select the first vertex as current (N)
If it is impossible to draw a diagonal from it inside the polygon to the point N+2 and the vertex N+1 is not convex (we check through a left turn), then the next one becomes current, and so on. along the ring.
We “cut off” the triangle from the polygon, the vertices become one less due to the elimination of the N + 1 vertex.
Go to point 1
Left turn is checked like this:
private fun vectorMultiplicationAbs(p1: RMPoint, p2: RMPoint, p3: RMPoint): Boolean {
val x1: Double = p1.x - p2.x
val y1: Double = p1.y - p2.y
val x2: Double = p3.x - p2.x
val y2: Double = p3.y - p2.y
return x1 * y2 - x2 * y1 >= 0
}And the triangulation algorithm itself:
fun List<RMPoint>.toTriangles() : List<RMTriangle> {
val triangles = mutableListOf<RMTriangle>()
val points = mutableListOf<RMPoint>()
val startPointsSize = this.size
forEach { point ->
points.add(point.copy())
}
var maxIndex = 0
var max = Double.MIN_VALUE
for (i in points.indices) {
if (points[i].x > max) {
max = points[i].x
maxIndex = i
}
}
val vectorsOrientation = vectorMultiplicationAbs(
getLooped(maxIndex - 1),
getLooped(maxIndex),
getLooped(maxIndex + 1)
)
var i = 0
while (points.size > 3) {
if (vectorMultiplicationAbs(
points.getLooped(i),
points.getLooped(i + 1),
points.getLooped(i + 2)
) == vectorsOrientation
) {
var correct = true
for (j in points.indices) {
// если точка не принадлежит текущему треугольнику
// и лежит в нем, то мы не можем построить этот
// треугольник
if (points[j] != points.getLooped(i) && points[j] != points.getLooped(i + 1) && points[j] != points.getLooped(i + 2) &&
RMTriangle.pointIn(
points.getLooped(i),
points.getLooped(i + 1),
points.getLooped(i + 2),
points[j]
)
) {
correct = false
}
}
if (correct) {
triangles.add(
RMTriangle(
points.getLooped(i),
points.getLooped(i + 1),
points.getLooped(i + 2)
)
)
points.remove(points.getLooped(i + 1))
}
}
i++
if (i > startPointsSize * 200) return emptyList()
}
triangles.add(
RMTriangle(
points[0], points[1], points[2]
)
)
return triangles
}Thus, we got a list of triangles that OpenGL draws. The algorithm is not optimal, and imposes certain restrictions on buildings. The most critical thing in our case is that you cannot draw a polygon with a cutout.
Roads
Roads can be drawn with lines, but
in wide lines, the triangles that make up the lines will be clearly visible;
when scrolling the map, the triangles will jump from side to side;
sharp corners will be visible at the junctions of the roads.
All this does not suit us, so I decided to divide the roads into triangles myself. Here, no complex algorithms are needed; to triangulate the road, we perform the following steps:
We take the road vector from the starting point and multiply it by a factor to get a vector that is half the width of the road.
Rotate the vector by 90 degrees and take its end point.
Rotate the vector another 180 degrees and again take its end point.
We perform the same operations with the end point of the road segment.
The resulting 4 points are combined into two triangles.
We rotate the vector in the following way:
fun rotateV90(start: RMPoint, end: RMPoint): Pair<RMPoint, RMPoint> {
val endZero = RMPoint(end.x - start.x, end.y - start.y)
val rotatedEnd = RMPoint(endZero.y, -endZero.x)
return Pair(
RMPoint(start.x, start.y),
RMPoint(start.x + rotatedEnd.x, start.y + rotatedEnd.y),
)
}
fun rotateV180(start: RMPoint, end: RMPoint): Pair<RMPoint, RMPoint> {
val endZero = RMPoint(end.x - start.x, end.y - start.y)
val rotatedEnd = RMPoint(-endZero.x, -endZero.y)
return Pair(
RMPoint(start.x, start.y),
RMPoint(start.x + rotatedEnd.x, start.y + rotatedEnd.y),
)
}By rotating the vector, we get two triangles that make up the road rectangle:
fun lineToTriangles(start: RMPoint, end: RMPoint, w: Float = 1F): List<RMTriangle> {
val AB = start.distance(end)
val x1 = start.x
val x2 = end.x
val y1 = start.y
val y2 = end.y
val k = w / AB
val dx = (x2 - x1) * k
val dy = (y2 - y1) * k
val A1 = RMPoint(dx + x1, dy + y1)
val B1 = RMPoint( x2 - dx, y2 - dy)
val AC = rotateV90(start, A1)
val AE = rotateV180(AC)
val BF = rotateV90(end, B1)
val BD = rotateV180(BF)
return listOf(
RMTriangle(BD.second, AC.second, AE.second),
RMTriangle(AE.second, BD.second, BF.second),
)
}
Thus, roads made of rectangles were obtained. Obviously, gaps have formed at the junctions of the roads. We fill them with triangles if the roads meet at a sufficiently large angle.
It turns out such a picture: all the roads and houses are drawn in the application, and quite quickly. You can display a map of the whole city – quite a good result.
The second layer of the circuit
The second layer draws all dynamically changing information: markers, captions for audiences and rooms, and icons. Drawing so many objects through OpenGL is expensive in terms of development. Canvas does this job well. To do this, we override the onDraw method in the Map View and draw the rest using regular shapes:
override fun onDraw(canvas: Canvas?) {
super.onDraw(canvas)
// отрисовка второго слоя
}Now the question arises of translating the coordinates in which OpenGL lives into canvas coordinates. In OpenGL, coordinates on the screen are considered from -1 to 1, and in the canvas canvas from 0 to w, where w depends on the width of the screen. This is how we get the coordinates of a point from the first layer in the second layer:
private fun RMPoint.toCanvasPoint(): RMPoint {
val w = measuredWidth
val h = measuredHeight
val upCenterX = w/2.0
val upCenterY = h/2.0
return if (
mRender?.getLastCameraPosition() != null &&
mRender?.getLastZoom() != null
) {
val camera = mRender!!.getLastCameraPosition()!!
val zoom = mRender!!.getLastZoom()!!
RMPoint(
(((x * zoom) * w / 2.0 + upCenterX) + (camera.x) * w / 2.0),
(((y * zoom) * h / 2.0 * (mRender?.getK() ?: 1F) + upCenterY) + (camera.y) * h / 2.0)
)
} else RMPoint.zero()
}Here you can see that we are taking the position of the camera and zoom from the render layer. This is because OpenGL draws frames on its own thread, and it has nothing to do with rendering the second layer. Because of this, layering occurs when the map is scrolled or zoomed. To fix this error, I linked the layers through the above function. To display the second layer, the last coordinates from the first are taken, due to this the layers are drawn synchronously.
Almost done, now you can draw whatever you want on top of the map. In the screenshot above, you can see the diagram and the marker drawn on top of it.
Route search
Let’s calculate the route from one point to another, and the scheme will be almost ready. All roads on the map have a list of roads associated with them, so they are combined into a connected weighted graph. There are many different algorithms for finding a path in a graph. My choice was the A star algorithm, since it quickly calculates the path on large graphs. When building, you need to take into account all the roads and paths inside the premises. To do this, before searching for a route, I combine all the roads into one list and start counting:
fun findRoad(start: Point, end: Point, roadFilter: Int): List<Road> {
val correctRoads = roadMap.roads.filter {
if (roadFilter == ALL) true
else it.status != Road.NONE
}.toMutableList()
roadMap.structures.forEach { structure ->
structure.floors.forEach { floor ->
floor.roads.forEach { it.floor = floor.number }
correctRoads.addAll(floor.roads)
}
}
correctRoads.connectAll(roadMap.getStairs(), roadMap.getDoors())
val startRoad = correctRoads.findMinDistanceRoad(start)
val endRoad = correctRoads.findMinDistanceRoad(end)
val frontier = PriorityQueue<Road>()
frontier.put(startRoad, 0.0)
val cameFrom = mutableMapOf<Road, Road?>()
val costSoFar = mutableMapOf<Road, Double>()
cameFrom[startRoad] = null
costSoFar[startRoad] = 0.0
while (frontier.isNotEmpty()) {
val current = frontier.get()
if (current == endRoad) break
for (next in correctRoads.neighbors(current)) {
val newCost = costSoFar[current]!! + current.timeInMin(roadMap.scale)
if (!costSoFar.contains(next) || newCost < costSoFar[next]!!) {
costSoFar[next] = newCost + heuristic(endRoad.start, current.end)
frontier.put(next, newCost)
cameFrom[next] = current
}
}
}
return reconstructPath(cameFrom, startRoad, endRoad)
}
Just finding the shortest route is not enough, some of the paths are less prioritized. For example, there is a choice: walk along a narrow path between fences or walk along a large street, but spend a little more time on it. Leading people through the gates is not the best option, so you need to advise a more pleasant way.
To suggest the best route, we need additional parameters besides distance. To do this, the code above has a heuristic function to evaluate the approach to the end point of the route. She is responsible for determining the optimal direction of movement.
private fun heuristic(a: Point, b: Point): Double {
return Road(start = a, end = b).timeInMin(roadMap.scale)
}
fun timeInMin(scale: Double) = (sizeInMeters(scale) / 1000.0) / (NORMAL_SPEED * k()) * 60.0In it, I determine how long it will take the pedestrian to move to the end point. And depending on the status of the road, this time is multiplied by the desired coefficient. Thus, it turns out to lay the route mainly along the green paths, which I have marked as more desirable.
finish line
The scheme is there, but something is still missing. The most important element, namely binding to geographic coordinates. To do this, we use an array of points geo, which I mentioned in the process of describing the models. The vast majority of geotags are written in the form of latitude and longitude, and the scheme is drawn in rectangular coordinates with the origin at zero.
My task was to bind the scheme to real coordinates and convert them to rectangular ones. This is how the connection of coordinates looks like: we take several points and indicate their position on the diagram and the position in geographical coordinates:
data class RMGeoPoint(
val map: RMPoint,
val real: RMPoint,
)To convert geographic coordinates to rectangular (from WGS84 to CK-42), we use the Gauss-Kruger method:
fun RMPoint.toGausKruger(): RMPoint {
val dLon = x
val dLat = y
val zone = (dLon / 6.0 + 1).toInt()
val a = 6378245.0
val b = 6356863.019
val e2 = (a.pow(2.0) - b.pow(2.0)) / a.pow(2.0)
val n = (a - b) / (a + b)
val F = 1.0
val Lat0 = 0.0
val Lon0 = (zone * 6 - 3) * Math.PI / 180
val N0 = 0.0
val E0 = zone * 1e6 + 500000.0
val Lat = dLat * Math.PI / 180.0
val Lon = dLon * Math.PI / 180.0
val sinLat = sin(Lat)
val cosLat = cos(Lat)
val tanLat = tan(Lat)
val v = a * F * (1 - e2 * sinLat.pow(2.0)).pow(-0.5)
val p = a * F * (1 - e2) * (1 - e2 * sinLat.pow(2.0)).pow(-1.5)
val n2 = v / p - 1
val M1 = (1 + n + 5.0 / 4.0 * n.pow(2.0) + 5.0 / 4.0 * n.pow(3.0)) * (Lat - Lat0)
val M2 =
(3 * n + 3 * n.pow(2.0) + 21.0 / 8.0 * n.pow(3.0)) * sin(Lat - Lat0) * cos(Lat + Lat0)
val M3 = (15.0 / 8.0 * n.pow(2.0) + 15.0 / 8.0 * n.pow(3.0)) * sin(2 * (Lat - Lat0)) * cos(2 * (Lat + Lat0))
val M4 = 35.0 / 24.0 * n.pow(3.0) * sin(3 * (Lat - Lat0)) * cos(3 * (Lat + Lat0))
val M = b * F * (M1 - M2 + M3 - M4)
val I = M + N0
val II = v / 2 * sinLat * cosLat
val III = v / 24 * sinLat * cosLat.pow(3.0) * (5 - tanLat.pow(2.0) + 9 * n2)
val IIIA = v / 720 * sinLat * cosLat.pow(5.0) * (61 - 58 * tanLat.pow(2.0) + tanLat.pow(4.0))
val IV = v * cosLat
val V = v / 6 * cosLat.pow(3.0) * (v / p - tanLat.pow(2.0))
val VI = v / 120 * cosLat.pow(5.0) * (5 - 18 * tanLat.pow(2.0) + tanLat.pow(4.0) + 14 * n2 - 58 * tanLat.pow(2.0) * n2)
val N = I + II * (Lon - Lon0).pow(2.0) + III * (Lon - Lon0).pow(4.0) + IIIA * (Lon - Lon0).pow(6.0)
val E = E0 + IV * (Lon - Lon0) + V * (Lon - Lon0).pow(3.0) + VI * (Lon - Lon0).pow(5.0)
return RMPoint(E, N)
}It remains to fit the obtained coordinates into the coordinates of the scheme. This can be done just like this:
RMPoint(normalD.x / kx, normalD.y / ky)It turns out a point on the diagram recorded in real geographical coordinates, and this can be finished.
What happened in the end?
I imported the resulting module into the application in just one evening, and that most of the time was spent on finalizing the interface. Below are screenshots from my schedule application.
Now everyone can click on the name of the audience under the subject and see how to get there, or find the right dining room. Soon this set of features will probably fall into the hands of thousands of students and will be baptized by fire.
The solution itself turned out to be interesting and its development brought a lot pain and suffering positive emotions, and the potential for application is unlimited. A large number of indoor companies can build such schemes into their solutions, from airports to warehouse management applications.
Thank you all for your attention, I will be glad to hear your opinion about this creation!
