Я разрабатываю веб-приложение для планирования сборок Minecraft.По сути, это 2D пиксельный редактор.Я буду ссылаться на точки как на «плитки», чтобы избежать путаницы с фактическими отображаемыми пикселями.(У каждой плитки вместо цвета есть идентификатор типа блока, разница в значительной степени несущественная.)
Требования:
- Размер "холста" неограничен.Для пользователя не должно быть дорого окрашивать плитку за пределами изображения.
- Плитки по умолчанию пусты.Пользователь не может заполнить бесконечную внешность (или, если это возможно, приложение «обманет» каким-то неуказанным способом).
- Программа должна обрабатывать видимую область размером 1000 на 1000 плиток.
- Программа должна эффективно представлять операции в очень больших регионах, таких как квадрат 1000 на 1000.
- Мелкие правки должны быть мгновенно быстрыми (т. Е. <100 мс). </li>
Программа должна поддерживать следующие операции:
- Раскраска отдельных пикселей.
- Поиск связанных компонентов одного цвета (которые могут быть очень большими).
- Объединение нескольких холстов.
- Перевод холста.
- Поворот холста на четверть оборота или переворачивание его по горизонтали или вертикали.
- Отмена и восстановление правок.
Чтобы справиться с этими требованиями, я хочу использовать базовую структуру данных:
- Квадро.
- Смещение по x, y, представляющее центр дерева квадрантов.
- Значение размера, представляющее логическую глубину квадродерева.
Я считаю, что это должно позволить эффективно реализовать необходимые операции редактирования в реалистичных условиях использования.(Бесплатного обеда нет; я согласен, что большой рисунок шахматной доски будет медленным.) Насколько я понимаю:
- Перемещение холста будет тривиальным (простое обновление смещения).
- Вращение или переворачивание холста может быть рекурсивно обработано в O (n) (где n - количество узлов в дереве).
- Нахождение связанного компонента будет O (n).
- Редактировать одну точку будет O (log (size)).
Объединение немного сложнее, потому что квадродерева должны быть выровнены, но мы сохраняем отдельное смещение, чтобы сделать перевод эффективным.Насколько я понимаю, перед слиянием нам просто нужно выполнить «реальный» перевод за O (n + m), где m - количество узлов в новом квадродереве.Предположительно, перед выполнением слияния мы выполним эту операцию на меньшем квадродереве (т. Е. Наименьшей логической глубине, чтобы избежать проверки фактического размера).
Редактирование истории - вопрос открытый.Очевидно, мы не можем копировать холст все время.Некоторые из операций (например, перевод или вращение) по своей природе обратимы, а другие (прямое редактирование или объединение), вероятно, могут быть выполнены путем «копирования» холста, но с повторным использованием неизмененных узлов.Похоже, что в большинстве случаев это должно занимать место в журнале.
У меня есть следующие вопросы:
- Есть ли какие-либо серьезные недостатки в этом подходе, которые я упустил из виду?
- Есть ли хорошая существующая реализация квадродерева, которую я должен использовать в качестве отправной точки?
- Есть ли какая-либо документация по сохранению истории редактирования с квадриами?
- Учитывая, что я не первыйчеловек, чтобы создать (в основном) редактор растровых изображений, где еще мне следует искать руководство?