Всем привет, я Леонид Соляной, Android разработчик из @UMNODigital, и сегодня я расскажу о своем домашнем проекте.

Еще на первом курсе я занялся разработкой мобильного приложения для просмотра расписания. Приложение росло, появлялись новые функции, и спустя 3 года им пользуются 5 тысяч студентов ежедневно, но в нем не хватало одной важной детали, а именно схемы территории. Институт большой, в нем 25 корпусов, и найти нужную аудиторию с первого раза непросто. А на сайте только картинки с номерами зданий. Где аудитория 24б-456? Как к ней пройти? Это приходится выяснять на месте перед парой и, возможно, опаздывать на нее. Похожие кейсы можно долго перечислять, и все они решаются интерактивной схемой, которая всегда будет под рукой.

Такие библиотеки уже есть, но все они стоят больших денег, а мое приложение денег не приносит, поэтому было принято волевое решение сделать все самостоятельно.

В статье до винтиков расскажу, как сделал кастомные карты и завернул в их android-библиотеку.

Кратко о концепте

Помогаем студентам не потеряться и найти кратчайший путь до нужной аудитории. Разработанная схема должна легко импортироваться в приложение и обновляться независимо от него. В противном случае новая версия карты дойдет до пользователя только после проверок в сторе и обновления приложения.

Отсюда формулируем условия для схемы. Схема должна:

• отображать расположение аудиторий;

• строить и показывать маршруты;

• рисоваться с помощью отдельного модуля;

• лежать на отдельном сервере для быстрого обновления.

Закончили с разговорами, теперь можно начинать работать.

Разбиваем схему на составляющие

Для отображения схемы института достаточно нарисовать дороги и здания. Это все объекты, которые будут отображены на карте.

Дороги:

• бывают разной ширины;

• не по всем можно ходить, но для наглядности схемы такие дороги тоже показаны;

• не все равнозначны: некоторые пути приоритетнее других.

Собрав условия получаем модель описания дороги:

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,
)

Со зданиями история интереснее. 

• Для навигации внутри помещений задаем количество этажей, расположение лестниц, входов, аудиторий и путей, по которым к комнатам можно пройти. 

• Часть зданий, как служебные постройки, отображается для наглядности и не требует прорисовки расположения комнат.

• Вход в здание — параметр этажа, а не всего здания, так как корпус может находиться на склоне, и входы могут быть на двух этажах. 

• Лестница соединяет не все этажи, а только те, на которые с нее есть выход.

Модель здания:

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>,
)

Здания содержат в себе набор точек, описывающих их контур, набор этажей и набор лестниц.

Модель этажа:

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,
) : Serializable

На каждом этаже есть комнаты, стены, а также маршруты, которые их соединяют + список входов в здание.

Модель лестницы:

data class RMStair(
   val floors: List<Int>,
   val position: RMPoint,
   val type: Int,
)

Лестница включает в себя положение в здании и список этажей, откуда на нее можно выйти.

Итого, получился набор моделей, которого хватает для описания большого количества помещений. Целиком схема выглядит так:

data class RMRoadMap(
   val id: String,
   val scale: Double,
   val roads: List<RMRoad>,
   val structures: List<RMStructure>,
   val geo: List<RMGeoPoint>,
)

Без объяснения остался только список geo, он связывает нарисованную схему с геодезическими координатами. На схеме будут отображаться реальные геометки или положение пользователя, но об этом далее.

Также у всех объектов можно вычитать в названии прибавку RM, это сделано для того, чтобы вынести код в библиотеку, так как это упростит поиск классов именно нашей библиотеки и исключит конфликты в названиях классов, по тому что по любому найдется хотя-бы один человек, который попробует назвать свой класс также как один из наших.

Создаем схему

Чтобы редактировать схему, я написал простой редактор на Qt. Там можно менять поля моделей и располагать объекты на карте нужным мне образом. Сделан он как черновой вариант, достаточно криво, его основная цель — быстрая подготовка данных для отображения в приложении.

В редакторе перерисовываем схему с карты и отправляем на сервер в формате JSON, где он сохраняется с id карты. Приложение получает JSON и отрисовывает его. В будущем было бы здорово получать данные с OSM (open street maps), чтобы не перерисовывать карту вручную, но редактор все равно нужен для прорисовки внутренних помещений.

Начинаем думать над мобильной библиотекой

На данном этапе есть схема территории в виде моделей, которую мы рисуем в редакторе и получаем с сервера. Карта реализована в виде кастомного View элемента. При создании MapView идет запрос на сервер, через Retrofit.

Но как отрисовать карту в приложении? Объемы данных большие, а карта не должна тормозить. Я рассматривал два варианта: рендер карты через Сanvas и через OpenGL, но в итоге решение оказалось посередине. Карта разделилась на два слоя, на первом отображаются дома и дороги, и рисуются они через OpenGL, а на втором слое маркеры и надписи, которые рисуются через Canvas.

На картинке выше представлена упрощенная схема библиотеки. Мы получаем с сервера объект карты, частично преобразуем в нужный вид для отображения через OpenGL и передаем в GLRender, который также на вход получает шейдеры. GLRender отображает основную часть карты: дороги, строения и этажи строений, если это необходимо. Canvas дорисовывает поверх рендера дополнительные элементы, вроде маркеров и проложенного маршрута.

Рендер первого слоя

OpenGL отображает только простые объекты: треугольники и линии, которые тоже состоят из треугольников. Следовательно, объекты на карте будем разбивать на эти примитивы.

Здания

Здания записываются в виде точек, которые складываются в многоугольник. Его разбиваем на треугольники. Для этого я использовал самый простой алгоритм триангуляции —  отрезание ушей:

1. Если число вершин <= 3 разбиение закончено

2. Выбираем первую вершину как текущую (N)

3. Если из неё нельзя провести диагональ внутри многоугольника к точке N+2 и вершина N+1 не выпуклая (проверяем через левый поворот), то текущей становится следующая и т.д. по кольцу.

4. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1.

5. Переходим к пункту 1

Левый поворот проверяется таким образом:

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
}

И сам алгоритм триангуляции:

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
}

Таким образом получили список треугольников, которые рисует OpenGL. Алгоритм неоптимальный, и накладывает на здания определенные ограничения. Самое критичное в нашем случае то, что нельзя нарисовать многоугольник с вырезом.

Дороги

Дороги можно рисовать линиями, но

• в широких линиях будут отчетливо видны треугольники, из которых линии состоят;

• при скроллинге карты треугольники будут прыгать из стороны в сторону;

• на стыках дорог будут видны острые углы.

Все это нам не подходит, поэтому я решил разбить дороги на треугольники сам. Тут никакие сложные алгоритмы не нужны, для триангуляции дороги выполняем следующие шаги:

1. Берем вектор дороги, идущий из начальной точки, и умножаем его на коэффициент, чтобы получить вектор длиной в половину ширины дороги.

2. Поворачиваем вектор на 90 градусов и берем его конечную точку.

3. Поворачиваем вектор еще на 180 градусов и опять берем его конечную точку.

4. Проделываем те же операции с конечной точкой отрезка дороги.

5. Полученные 4 точки объединяем в два треугольника.

Поворот вектора выполняем таким образом:

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),
   )
}

За счет поворота вектора получаем два треугольника, из которых состоит прямоугольник дороги:

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),
   )
}

Таким образом, получились дороги, сложенные из прямоугольников. Очевидно, что на стыках дорог образовались разрывы. Их заполняем треугольниками, если дороги стыкуются под достаточно большим углом.

Получается такая вот картинка: в приложении рисуются все дороги и дома, причем достаточно быстро. Можно отобразить схему целого города — вполне неплохой результат.

Второй слой схемы

Вторым слоем отрисовываем всю динамически изменяющуюся информацию: маркеры, подписи к аудиториям и помещениям и иконки. Рисовать такое количество объектов через OpenGL затратно в плане разработки. С этой задачей отлично справляется Canvas. Для этого переопределяем метод onDraw во View карты и отрисовываем оставшееся с помощью обычных фигур:

override fun onDraw(canvas: Canvas?) {
   super.onDraw(canvas)

   // отрисовка второго слоя

}

Теперь встает вопрос перевода координат, в которых живет OpenGL, в координаты канваса. В OpenGL координаты на экране считаются от -1 до 1, а в холсте канваса от 0 до w, где w зависит от ширины экрана. Вот так вот получаем координаты точки из первого слоя во втором слое:

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()
}

Тут видно, что мы берем положение камеры и зума из слоя рендера. Это связано с тем, что OpenGL рисует кадры в своем потоке, и он никак не связан с отрисовкой второго слоя. Из-за этого при скролле или зуме карты возникает расслоение. Для фикса этой ошибки я связал слои через вышеописанную функцию. Для отображения второго слоя берутся последние координаты из первого, за счет этого слои рисуются синхронно.

Почти готово, теперь можно рисовать все что угодно поверх карты. На скрине выше видно схему и маркер, нарисованный поверх нее.

Поиск маршрута

Рассчитаем маршрут из одной точки в другую, и схема будет почти готова.  Все дороги на карте имеют список связанных с ними дорог, так они объединяются в связный взвешенный граф. Для поиска пути в графе есть много разных алгоритмов. Мой выбор остановился на алгоритме A star, поскольку он достаточно быстро считает путь на больших графах. При построении нужно учесть все дороги и пути внутри помещений. Для этого перед поиском маршрута я объединяю все дороги в один список и начинаю считать:

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)
}

Просто найти кратчайший маршрут недостаточно, некоторые из путей менее приоритетны. Например, есть выбор: пройти по узкой тропе между заборами или прогуляться по большой улице, но потратить на это немного больше времени. Водить людей по подворотням не лучший вариант, поэтому нужно посоветовать более приятный путь.

Чтобы предложить лучший маршрут, нам нужны дополнительные параметры помимо расстояния. Для этого в коде выше есть эвристическая функция для оценки приближения к конечной точке маршрута. Она и отвечает за определение оптимального направления движения.

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.0

В ней я определяю, сколько времени потребуется пешеходу на движение до конечной точки. И в зависимости от статуса дороги это время умножается на нужный коэффициент. Таким образом, получается прокладывать маршрут преимущественно по зеленым путям, которые отмечены мной как более желательные.

Финишная прямая

Схема есть, но чего-то все еще не хватает. Самого главного элемента, а именно привязки к географическим координатам. Для этого используем массив точек geo, о котором я упоминал в процессе описания моделей. Подавляющее число геометок записываются в виде широты и долготы, а схема рисуется в прямоугольных координатах с началом в нуле. 

Передо мной стояла задача привязать схему к реальным координатам и преобразовать их в прямоугольные. Вот так выглядит связь координат: берем несколько точек и указываем их положение на схеме и положение в географических координатах:

data class RMGeoPoint(
   val map: RMPoint,
   val real: RMPoint,
)

Для преобразования географических координат в прямоугольные (из WGS84 в CK-42) используем метод Гаусса-Крюгера:

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)
}

Осталось подогнать полученные координаты в координаты схемы. Это можно сделать просто через подобие:

RMPoint(normalD.x / kx, normalD.y / ky)

Получается точка на схеме записанная в реальных географических координатах, и на этом можно заканчивать.

Что в итоге получилось?

Получившийся модуль я импортировал в приложение всего за вечер, и то основное время заняла доработка интерфейса. Внизу приведены скрины из моего приложения с расписанием.

Теперь каждый может кликнуть на название аудитории под предметом и посмотреть, как туда добраться, или найти нужную столовую. Скоро этот набор фичей возможно попадет в руки тысяч студентов и пройдет боевое крещение.

Решение само по себе получилось интересным и его разработка принесла много боли и страданий положительных эмоций, а потенциал применения безграничен. Большое количество компаний связанных с работой в помещениях могут встраивать в свои решения такие схемы, от аэропортов до приложений для управления складом.

Всем спасибо за внимание, буду рад услышать ваше мнение о данном творении!