Структура точечных данных для приложения для создания эскизов

Question

В настоящее время я разрабатываю небольшое приложение для создания эскизов на основе элемента Canvas HTML5. Есть одна конкретная проблема, для которой мне пока не удалось найти правильное решение.

Идея состоит в том, что пользователь сможет свободно манипулировать существующими данными (точками) штрихов. Это включает в себя перемещение данных о точке (т. Е. Магнитный инструмент) и манипулирование ими прихоти в противном случае (т. Е. Изменение цвета).

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

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

Любые указатели приветствуются. :)

Answer 1

стандартное решение для работы со списками произвольных точек в 2d - это разбиение пространства на четыре дерева: http://en.wikipedia.org/wiki/Quadtree

Answer 2

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

• кД дерево
• вп дерево
• простой индекс сетки

Answer 3

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

У вас должен был бы быть список пикселей, сопоставляемых каждому «мазку кисти», если вы хотите иметь взаимодействия отмены / мазка кисти, но это похоже на другой объект - вам просто нужно, чтобы все мазки кисти указывали на эту центральную матрицу (для фактического содержания точек, на которые они влияли - возможно, у них были бы «веса» относительно того, сколько цвета они внесли в точку, или что-то в этом роде).

Answer 4

Я бы пошел с простой матрицей int pixels[][], где для данного пикселя в x, y значением матрицы является ее цвет.

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