Pull to refresh

Comments 17

UFO just landed and posted this here
Совершенно верно. Чтобы работать с объектами любой формы, нужно только доработать определение вхождения точки в объект (при клике и ховере). Передо мной такой задачи не стояло, но доработать недолго.
По поводу HTML схем: думаю, вы не будете спорить, что браузеру намного сложнее отрендерить dom элемент с кучей параметров и событий, чем кучку пикселей на канвасе? :)
Как раз решение перейти на канвас пришло после использования svg и html схем, результат порадовал.
Тут даже вопрос не в том, на чем лучше делать схемы залов, а сколько объектов на этих схемах.
Конечно, если элементов не более 500, проще сделать на дивах или свг. Все будет работать из коробки: клики, ховеры, повороты и прочее.
Но когда схема будет иметь 6к мест и у Вас популярный сервис (т.е. число пользователей условного ie большое), то встанет вопрос: «почему схема открывается 10 секунд?». Вот у нас примерно такая ситуация :)
А решение, описанное в статье, достойно тянет и 20к объектов даже в ie, пример

Как количество пользователей и то, какой у них браузер, влияет на скорость работы?

Напрямую: в разных браузерах и устройствах скорость отрисовки канваса разная. Ну и не только канваса, даже свг. Обычно хуже всего работает в ie.
Быстрая она в реализации или в работе? На машинке с i5-7440HQ(2.8Ghz), Win10, Firefox демка безбожно тормозит :-( Выделение места на карте отстает от курсора нa ~1-1.5 секунды.
Должна быть в работе, конечно :)
FF почему то на крупном масштабе работает примерно как ie, при приближении становится нормально. Еще не придумал, как это дело ускорить, но я в процессе.
На телефоне в хроме работает как надо.

Хорошая работа. Хотелось бы в следующей статье увидеть сравнительные нагрузочные тесты: canvas vs svg vs html для разных популярных браузеров. Например, для маленьких залов, согласен с предыдущим оратором, наверное проще отрендерить html на сервере?

Для маленьких да, проще html: не нужно возиться с обработкой событий и будет легко менять внешний вид.
В целом не плохо, но сразу видно, что можно улучшить. Смотрите, в чем состоит задача по нахождению квадрата. Я бы предложил Вам избавиться от Вашего дерева и просто делать бинпоиск, сейчас расскажу как. Это будет быстрее и, кстати, меньше кода. Условимся, что все места (квадраты) имеют одинаковый размер. Запихнем все координаты верхних левых углов в массив пар (x, y). Отсортируем вначале по координате x, потом по y. Понятно, что тогда массив разобьется на куски с одинаковой координатой x. Бинарным поиском найдем первую такую группу, что ее x координата больше либо равна координате курсора. Далее вторым бинарным найдем первую точку поиском найдем конец этой группы. И нам остается сделать бинпоиск чтобы найти первую координату y большую либо равную y курсора. Теперь Вы знаете предполагаемый квадрат, остается проверить принадлежность курсора, предполагаемому квадарту. Итого log2(n) ассимптотика и примерно 20 строчек кода. Намного проще и быстрее
Деление схемы на квадраты помогает не только искать объект по курсору, но и позволяет вообще не думать об объектах при рендере видимой области: место перебора объектов мы ищем узлы дерева, входящие в зону видимости и показываем все их объекты.
Спасибо за замечание, но если честно, мне кажется удобнее использовать дерево.
Кроме того, в нашей войне за производительность канваса время поиска занимает одно из последних мест, больше всего проблем именно со скоростью отрисовки.
На TypeScript не пишу, но на c++ это выгладяло бы примерно так:
arr — массив c верхними левыми координатами
sz — сторона квадрата
auto start = lower_bound(arr.begin(), arr.end(), {x_cur, y_cur});
auto end = upper_bound(arr.begin(), arr.end(), {start->first, INF}) — 1;
auto res = lower_bound(start, end, {start->first, — INF});
if (res->first + sz >= x_cur && res->second + sz >= y_cur) {
// курсор над квадратом res
} else {
// курсор не над квадратом
}
upper_bound — первый больший, lower_bound — первый больше либо равный

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


const BOX_HEIGHT = 100, BOX_WIDTH = 160;

// Распределяем места по массиву. Предполагается, что если место пересекает границу
// одной или более области, то добавляем место в смежные области.
let boxes = [];
for (let seat in seatList) {
  let topX = int(seat.X/BOX_WIDTH),
      topY = int(seat.Y/BOX_HEIGHT),
      bottomX = int((seat.X+seat.Width)/BOX_WIDTH),
      bottomY = int((seat.Y+seat.Height)/BOX_HEIGHT);

  boxes[topY][topX].push(seat);
  if (bottomX != topX) boxes[topY][bottomX].push(seat);
  if (bottomY != topY) boxes[bottomY][topX].push(seat);
  if (bottomX != topX && bottomY != topY) boxes[bottomY][bottomX].push(seat);
}

// Ищем ячейку массива, в которой есть нужное место.
let boxX = int(point.X/BOX_WIDTH), boxY = int(point.Y/BOX_HEIGHT);
if (boxes[boxY][boxX]) {
  for (let seat in boxes[boxY][boxX]) {
    if (seat.Contains(point)) {
      alert("Вы выбрали ряд " + seat.Row + " место " + seat.Number); 
    }
  } 
}

// Прошу прощения за возможные огрехи в синтаксисе, JS не мой основной инструмент.

Если у вас не вся область вмещается на "экран", то добавьте к point.X и point.Y смещение, если масштабирование — то умножьте/разделите на коэффициент масштабирования.

Если я правильно понял Ваш код, работать он будет только для точек в углах квадрата :)
Наведение внутрь объекта не даст результата, т.к. понятно, что не будет существовать таких индексов у Вашего массива. А чтобы они были — нужно разметить так каждую точку на схеме либо также перебирать уже 'boxes', что явно не оптимальнее поиску по дереву. Да и вы потратите кучу памяти, т.к. дублируете объект в массив 4 раза. В общем посыл я не понял, извините.
Теперь немного понял. Будет неправильно определяться, если размеры объекта будут больше разбиения в 2+ раза. В нашем случае это важно, т.к. есть крохотные места и большие сцены или сектора со свободной рассадкой.
А откуда исходные данные зала: координаты в вашей системе координат и ряды/места в системе координат бухгалтерии зала?

Долго не давала ваша задача мне покоя. Всё казалось, что незначительными изменениями можно существенно ускорить ваше решение.
Демо-стенд я бы долго делал, по этому опишу в кратце суть идеи.

Думаю можно в разы повысить быстродействие если:
1. Кешировать полномасштабную схему на диск в png рядом с scheme-data.js. (В вашем варианте это около 8000 на 8000px).
2. Ничего не перерисовывать при перетаскивании и масштабировании: таскать и масштабировать можно с помощью css (transform и overflow). Даже телефоны с этим быстро справляются
3. Ничего не перерисовывать при ховере. По сути нужно получить координаты Места (об этом ниже) и спозиционировать там html элмент с динамичным содержимым. Позиционирование одного элемента — это быстрая операция.

Как «по-быстрому» найти координаты объекта? По цвету :)
Чего проще: снять координаты мыши (или пальца), получить по этим координатам цвет пикселя с канваса.
Для этого рисуем схему на канвасе в полном размере (один раз) каждое Место уникальным цветом (у нас их 16 миллионов) на основе индекса объекта (конвертим int в hex)

Все исходные данные готовы — можно показывать:
1. показываем закешированный канвас юзеру, по которому он кликает и ховерит
2. по координатам клика/ховера получаем цвет из цветовой карты
3. конвертим hex цвет обратно в int (это индекс нашего объекта в массиве)
4. получаем данные из объекта и дальше показываем то-что надо

А вот, данные, которые должны оставаться на канвасе (при клике) или если они «недоступны»/«распроданы» и проч, нужно уже точечно рисовать, как вы и делаете.
Или, если хватит памяти на целевых устройствах, не по канвасу со схемой, а на новом канвасе (сделать верхним синхронным слоем)

При этом что мы выигрываем:
1. В scheme-data.js только сами «места» без лишних (балкон, портер) (и прочих bgcolor и font-size) — это котлеты
2. Дорисовать в фотошопе на сохранённую схему необходимые надписи с использованием дизайнерских шрифтов и прочего творчества — это мухи.
3. Скорость работы одинакова в любом масштабе.
5. Фактически мы не ограничены количеством в 5-6 тыщ. Мне кажется, что и карты размером в 16 000px будут нормально работать, а это зал на 25 000 мест — стадион.

Теоретически…
В общем я излился :) Возможно, я где-то ошибаюсь и что-то не учитываю.
Sign up to leave a comment.

Articles