Comments 12
На самом деле, в грубом алгоритме незачем проверять весь экран, достаточно только новые пиксели. А если еще подумать, то нужно иметь размеченную карту, чтобы просто bounding box-ы объектов сравнивать с viewport-ом, а не пиксели
Как с языка сняли. Тоже подумал, что тут какое-то велосипедостроение излишнее
Как я понимаю, описываемая автором программа по сути это GUI к некоей серверной части, которая отдает готовые картинки в заданном формате PCX. Поэтому в эту часть у него просто нету доступа.
Для грубого поиска неголубых пикселей можно было просто использовать прореживание - то есть проверять не все пиксели, а только сетку с шагом 8, например. Это бы уменьшило требуемые ресурсы в 64 раза. Да, есть небольшая вероятность пропустить маленькие объекты, что в данной задаче совершенно несущественно.
Не понимаю, откуда взялось впечатление о какой-то серверной и клиентской части. Вроде нигде об этом не написано. Есть только одна программа, читающая файлы карт в память и распаковывающая отображаемый фрагмент в реальном времени. Если фрагмент получился одноцветным, отображать его бессмысленно и берется фрагмент другого масштаба. Вся программа полностью доступна, поэтому исправления получились такими маленькими.
нужно иметь размеченную карту
Что имеется ввиду? Например в программе одно из семейства карт - это бесплатная TrueMarble разрешением 1 пиксель - 250 м на земле.
Всего 32 файла размером 21600х21600х24бит. Если это представить в формате BMP то потребуется 44,8 Гбайт. И чего там должно быть размечено? И сколько еще Гигов это займет?
В простейшем случае — просто квадратики, вмещающие в себя острова, большие континенты просто покрыты пересекающимися прямоугольниками чтобы более-менее следовать береговой линии. Нам же не требуется большая точность. Можно пойти дальше, и береговую линию рисовать все же полигонами. Когда в viewport-е нет ни одного полигона с сушей, вычисляете, насколько нужно увеличить viewport, чтобы произошло пересечение хоть с одним полигоном.
Думаю, эту информацию вполне можно впихнуть в несколько сотен мегабайт.
Прошу прощения, если я неправильно понял задачу, но если нужно определять "комфортный" для наблюдателя уровень зума карты, то зачем его считать в реальном времени по "входящим" видеопикселям?
Если известна плановая траектория станции и/или фактические координаты станции, то можно же заранее рассчитать значение зума для каждой области карты / точки траектории. В масштабах многомегабайтных изображений на каждый кадр хранение одного дополнительного килобайтного массива [время -> зум левел] не должно быть проблемой...
Да, можно моделировать полет как в прошлом (по архиву орбитальных данных) так и в будущем (по прогнозу). Эта основная задача программы. И можно запоминать времена переключения карт. Но делать это придется для всех масштабов карт и для заданного размера экрана. И в среднем каждые два дня орбитальные данные уточняются. И опять моделируй все сначала. А зачем, когда сейчас и так все успевает. Без всякого гемороя с запоминанием каких-то таблиц и их проверкой потом.
Если у обработчика есть текущие координаты центра картинки, а не только само изображение, то я бы сделал проще. Я бы заранее составил табличку, в которую записал оптимальный масштаб картинки для каждой точки земной поверхности, где может оказаться МКС. И затем периодически проверял бы текущие координаты центра картинки по этой табличке, меняя при необходимости целевой масштаб.
Прикинем грубо размер такой таблички в простейшем варианте. В самом крупном масштабе картинка примерно 2х2 градуса? Тогда точность позиционирования центра картинки достаточно взять
с шагом в 0.3 градуса
Это дает точность позиционирования примерно 1/6 картинки. При такой точности, в зависимости от разметки, в двух крайних случаях масштаб будет меняться либо когда море заняло 5/6 изображения, либо когда ближайшая суша уехала на 1/6 за край картинки. На практике можно разметить карту так, чтобы был какой-то средний вариант, который почти всегда будет менять масштаб примерно в момент выхода суши за край изображения.
При такой точности нам нужно иметь в табличке 1200 записей - по одной для каждого значения долготы. Каждая запись будет содержать список диапазонов широт, где масштаб отличается от стандартного. Например, для долготы 0 градусов этот список может выглядеть
примерно так:
[-52:+5], Max_Size ! Южная Атлантика
[36.5:37.8], Medium_Size ! Средиземное море
Каждый раз, когда долгота приближается к следующему размеченному значению, лезем в эту табличку и ищем: попадает ли текущая широта в один из предопределеных диапазонов. В большинстве случаев для каждой долготы будет всего несколько диапазонов (обычно меньше 10 шт) - проверка займет пренебрежимо малое время. Дальше все просто: если данная широта "особая" (т.е. она внутри одного из диапазонов == центр карты над океаном), то запрашиваем карту в том масштабе, который указан в табличке. Если нет - то используем стандартную карту.
Да, размер таблички получится не нулевой, но это все равно
кило (а не мега) байты
Даже если делать простой массив, а не список записей переменной длины, получим 1200 записей не более 100 байт в каждой. (Понятно, что при шаге по широте 0.4 градуса значения широт легко упаковываются в байт, а масштабов вообще будет несколько штук всего. Если нужна чуть большая точность, то можно не полениться и упаковать каждый диапазон в 4 байта - например, по 14 бит на широты и 4 бита на масштаб)..
Конечно, придется сперва разметить карту и заполнить табличку. Зато в ходе такой разметки при необходимости можно подобрать свой оптимальный масштаб для каждого региона, чтобы изображение было максимально информативным.
UPD: пока я разглагольствовал, BioLogIn уже выступил с почти той же идеей. Только он предлагает индексировать не координаты, а время. Это упростит табличку, но потребует регулярно ее обновлять, так как Земля вращается и траектория не повторяется на следующих витках...
В общем, альтернативных решений хватает ;-)
Я бы заранее составил табличку, в которую записал оптимальный масштаб картинки для каждой точки земной поверхности, где может оказаться МКС.
МКС оказывается над любой точкой земной поверхности от 51,8 с.ш. до 51,8 ю.ш. Поэтому гипотетические таблицы нужны очень и очень большие. И постоянные проверки. А на другой чаше весов - всего лишь 4 (прописью: четыре) ассемблерные команды, которые делают ненужными и таблицы и проверки. И работают они одинаково для всех масштабов карт и всех размеров экрана.
Поэтому гипотетические таблицы нужны очень и очень большие.
Зачем рассуждать гипотетически? Я в своем посте привел конкретные цифры: если таблицу не оптимизировать, плюс потребовать хорошую точность, то всего нужно около 1Мб. Если оптимизировать (переменная длина записи), то можно еще раз в пять сжать, т.к. для подавляющего большинства долгот 25 диапазонов не нужно.
И постоянные проверки.
Это да. Проверять придется каждые несколько секунд. А при обычном обновлении карты разве не так? В этом смысле все баш на баш. Зато сама проверка - это не сравнение пикселей (причем довольно многих), а поиск в индексированной таблице. По количеству операций это даст выигрыш на пару порядков примерно... Но, разумеется, выигрыш не бесплатный, а ценой 1Мб памяти на табличку плюс существенное усложнение кода. Впрочем, я согласен, что если алгоритм пиксельного анализа и так работает достаточно быстро, то более быстрые алгоритмы не особо нужны.
Главное достоинство (и одновременно недостаток) моего варианта - не в скорости, а в возможности индивидуальной "ручной" донастройки оптимального масштаба карты для каждой точки земной поверхности. Если чуть-чуть повозиться с разметкой, то можно удовлетворить любое пожелание БигБосса об индивидуальной подгонке масштаба для разных зон. Например, чтобы масштаб карты не укрупнялся (в ущерб отображению контуров материка) ради одного никому не нужного микроострова посреди океана, или наоборот.
Что лучше - полностью автоматический алгоритм, который не требует (не допускает) индивидуального подхода к отдельным точкам поверхности, или алгоритм, который позволяет эксперту что-то подкрутить на свое усмотрение - это, я думаю, вопрос философский. Т.е. все зависит от ситуации, а в общем случае он однозначного правильного решения не имеет. Материал в статье хорошо подан, поэтому задачка многим понравилась и стала поводом "мозгового штурма". Но мозговой штурм тем и интересен, что генерирует множество совершенно безумных идей, большинство из которых затем отбрасывается. А иногда такая идея вполне может и вырасти во что-то полезное.
Я бы для этой задачи взял coastlines (а возможно и другие данные) из openstretmap, посчитал бы по ним distance field и определял бы зум за один (ну или 4 если хочется плавно) лукап. В общем виде это только так и решается, потому что если в качестве подложки использовать спутник, с одной стороны вода будет неоднородной, с другой - на сплошной лес тоже неинтересно смотреть.
Как найти часть суши, окруженную водой