Каждый день мы работаем над улучшением наших проектов. Будь то инициатива заказчика, продукт корпорации либо Ваш собственный. Изучая отзывы пользователей своего проекта, я столкнулся с запросом ускорить действия пользователя на одном из ключевых экранов. Это можно делать разными способами - разбиение экрана на несколько, улучшение UI… Но рано или поздно придется прорабатывать UX.

Проблема

Мой проект решает проблему подсчета хит фактора в спортивной стрельбе. Правила следующие - стрелок на время делает N выстрелов по мишени. Мишень делиться на 3 зоны:

• Alpha: +5 points

• Charley: +3 points

• Delta: +1 point

• Miss/Fee: -10 points

Далее, полученные очки делим на время = хит фактор. У кого больше - тот и молодец.

Рассмотрим первоначальный вариант.

В приложении есть экран с кликабельными зонами мишени и возможностью отметить промахи либо штрафы. Удобно и лаконично на первый взгляд….

Я захотел проверить полезность кнопок undo/redo и увидел - что redo используется довольно редко, а undo - довольно часто. Настолько часто, что при сравнении пропорций использования кликов по зонам и кликов undo оказалось, что эта пропорция равна 1/10. Это говорит о том, что каждый 10 раз клик пользователя по зоне является ошибочным. Что же может вызывать такое соотношение?

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

Второй момент - фрагментация экрана и не всегда зоны альфа и чарли могут покрыть толстый палец инструктора…

Гипотеза решения проблемы

Модифицируем экран и добавим отдельные 3 кнопки с вероятными зонами клика. Возможность отмечать попадания по мишени не исключаем. Оставим оба варианта для проверки гипотезы сравнения вариантов использования.

Как вы могли уже заметить, мишенька делится на 3 зоны, где каждая накладывается друг на друга. При нажатии на кнопку Альфа/Чарли/Дельта мы должны выбрать произвольную точку на мишени и отметить ее как попадание. Забегая вперед, я модифицировал экран и добавил дополнительные типы мишеней, которые могут пригодится для других дисциплин. Исходя из модификаций, сформируем требование:

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

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

Отмечу сложность решения проблемы и различными вариациями следующих мишений (например USPSA/IDPA), где зоны могут быть выражены в виде мультиполигонов.

Решение

Первое что приходит в голову - бинаризировать полигон, запустить Random и проверять “выколотую“ зону на пересечения. Но даст ли простой перебор минимального времени? Можем ли гарантировать что рандом не попадет в ту же точку в которой был? А если можем - то разместим вектор на матрице размером N*M, отметим все закрашенные точки как 1, а не закрашенные как 0. Затем перемешаем его начнем искать точки… Стоп, ведь такую матрицу мы можем легко превратить в линейный массив, просто отбросив нули и заменив значения координатами.

А что делать с пересечениями? Должны ли в случае кривой заполнять ее значениями или нет? Здесь нам помогают правила спортивной стрельбы, где любая перфорация считается попаданием. Плюс, при подготовке данных, мы можем исключить отрисовку контуров и при переведении в черно-белое изображение наложить пару фильтров. Но это уже нюансы….

Таким образом, мы получаем следующий массив:

val vectorC = setOf(
     Point(x = 6.0, y = 0),
     Point(x = 7.0, y = 0),
     Point(x = 8.0, y = 0),
		 // ...
)

Затем, перемешиваем его и получаем:

val vectorC = setOf(
     Point(x = 7.0, y = 10.0),
     Point(x = 11.0, y = 14.0),
     Point(x = 8.0, y = 15.0),
		 // ...
)

Таким образом, мы получаем множество искомых точек, которые можем разместить в стек/очередь и доставать их после каждого клика. Не забываем про соотношение реального экрана и размера подложки вектора, на котором он был заготовлен - это решается с помощью скаларного [произведения векторов](https://ru.wikipedia.org/wiki/Скалярное_произведение#:~:text=Скаля́рное произведе́ние (иногда называемое внутренним,векторов и угла между ними.).

Конечно, всю необходимую разметку можно сделать вручную, но слоев очень много, как и вариаций решений. По-этому, пишем алгоритм. Рисовать будем на compose canvas.

enum class ActionEvent { A, C, D, ; }
data class RandomSectorPointInput(
    val shield: Shield,
		val shieldSize: Size,
    val screenSize: Size,
    val actionEvent: ActionEvent,
)
fun create(input: RandomSectorPointInput): Set<Coordinates> {
        val imageBitmap = ImageBitmap(
            width = input.shieldSize.width.toInt(),
            height = input.shieldSize.height.toInt(),
            config = ImageBitmapConfig.Rgb565,
        )
        val composeCanvas = Canvas(imageBitmap)

				// Каждая мишень содержит в себе множество слоев наложенные друг на друга
        input.shield.layers.forEach { layer ->
            val path = drawPathFromPathData(
                pathData = layer.polygon.value,
            )
						
						// Каждый слой содержит в себе информацию о своей принаждежности
					  // сверяем с искомой точкой и определяем каким Pain будем закрашивать
            val paint = if (layer.actionEvent == selectedActionPoint) {
                fillPaint
            } else {
                zeroPaint
            }
            composeCanvas.drawPath(path = path, paint = paint)
        }

        val buffer = IntArray(imageBitmap.width * imageBitmap.height)
        val fillColorArgb = fillColor.toArgb()
				// считываем все пиксели в массив
        imageBitmap.readPixels(
            buffer = buffer,
            startX = 0,
            startY = 0,
            width = imageBitmap.width,
            height = imageBitmap.height,
        )
				// вычисляем множитель для правильной координаты на дисплее
        val scaleFactor = input.shieldSize.scaleToEtalon(input.screenSize.toComposeSize())
        return buffer.mapIndexed { index, colorValue ->
						// если точка в массиве является закрашенной - помещаем ее в результат
            if (colorValue == fillColorArgb) {
                val x = index % imageBitmap.width
                val y = index / imageBitmap.width
                Coordinates(x.toFloat(), y.toFloat()) / scaleFactor
            } else {
                null
            }
        }.filterNotNull().toSet()
    }

Мне было лень подготавливать для каждой из мишеней свои правильные вектора. Не забываем, мишеней большое количество и подготовка их - ручной труд.

Я просто накладывал их одну за одной и закрашивал в необходимый цвет. Можно было бы обойтись и конфигурацией только в альфа каналом. Но в этом случае, не получится лайфхак с наложением - непрозрачные зоны будут видно из прозрачных. По-этому подготовка ImageBitmap происходит с конфигом ImageBitmapConfig.Rgb565. Про метод drawPathFromPathData я писал в этой статье.

Проблема решена. Какие еще оптимизации возможно сделать для ускорения вычисления?

Все это можно проделать один раз и положить в массив подготовленных данных вместе со слоями. Возьмем для расчетов размер векторной подложки: 340*430 = 146 200. Даже сериализованные 10% возможного массива - слишком много для сериализации и хранении как исходный массив. Но задача выполнима и звучит себе вполне вменяемо для оптимизации вычислений на клиенте. Их тоже можно сериализовать с помощью векторного представления и распарсить обратно, но уже не как Path, а как множество искомых точек. Вопрос - сколько таких точек мы можем себе позволить? Ответ на этот вопрос, я оставлю на аналитике, результат которой можно будет вычислить после интеграции фичи пользователю.

По-этому, оптимизируем задачу максимально лениво - добавим Weak cache с калькуляцией на лету.

internal class AndroidRandomSectorPointUseCase(
    private val storage: FilledCoordinatesStorage,
    private val factory: FilledCoordinatesFactory,
) : RandomSectorPointUseCase {

    override suspend fun invoke(input: RandomSectorPointInput): RandomSectorPointResult =
        storage.getOrPut(input) { factory.create(input) }
            .randomOrNull()
            ?.let(RandomSectorPointResult::Success)
            ?: RandomSectorPointResult.Error
}

internal interface FilledCoordinatesStorage {
    fun getOrPut(
        input: RandomSectorPointInput,
        calculatorBlock: () -> Set<Coordinates>
    ): Set<Coordinates>
}

internal class WeakInMemoryFilledCoordinatesStorage : FilledCoordinatesStorage {
    private val map: MutableMap<RandomSectorPointInput, Set<Coordinates>> = WeakHashMap()
    override fun getOrPut(
        input: RandomSectorPointInput,
        calculatorBlock: () -> Set<Coordinates>
    ): Set<Coordinates> = map.getOrPut(input, calculatorBlock)
}

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