 |
|
Модераторы: feodorv, GremlinProg, xvr, Fixin |
 
|
|
Изменение Z-order-а, хранящегося в бинарном дереве, редактор векторной графики 
| KasMP |
|
|||
 Опытный  Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: нет Всего: 30 |
Приветствую вас, мои любимые
 !Позволю себе написать немного больше, чем нужно для ответа на мой вопрос - картина получится более полной, проще будет сориентироваться...Есть (точнее, будет) редактор векторной графики. В нем есть (будет) класс фигура и несколько его наследников (конкретных графических примитивов - линия, эллипс, прямоугольник, кривая Безье, что-то еще). Предположим, мы
Я вижу только один вариант: после любого щелчка запоминать его координаты и с учетом Z-order обходить весь массив, проверяя принадлежность координат щелчка каждой фигуре. Но ведь это нонсенс   !Помогите, пожалуйста. Добавлено через 3 минуты и 36 секунд Что-то название темы совсем не отражает ее суть  . Не знаю, как изменить его . |
|||
|
||||
Загрузка ...
| Lazin |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 8 Всего: 154 |
можно использовать эту структуру данных, для эффективного поиска по координатам
http://en.wikipedia.org/wiki/Quadtree |
|||
|
||||
| KasMP |
|
|||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: нет Всего: 30 |
Lazin, спасибо большое, посмотрю
.А других вариантов совсем нет  ? |
|||
|
||||
| Lazin |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 8 Всего: 154 |
AFAIK, проще только метод грубой силы
|
|||
|
||||
| Alexeis |
|
|||
 Амеба  Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 7 Всего: 459 |
Можно проще, сделать равномерную сетку, скажем 10х10 и соответствующую ей матрицу, каждый элемент это список фигур, которые пересекают эту клетку. Соответственно по координатам мыши путем округления сразу получаем нужную клетку, дальше остается перебор внутри этой клетки. В случае сетки 10х10 объем вычислений в среднем уменьшиться в 100 раз. Скажем при 1000 фигурах, перебор в среднем будет среди 10ти фигур, при 10000 их уже будет в среднем сотня. Для простого редактора этого должно быть достаточно. Я применял такой алгоритм, когда писал двумерную модель столкновения атомов. Задача была аналогичной не делать перебор n (n - 1) фигур на каждый кадр. -------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
| Lazin |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 8 Всего: 154 |
Alexeis, а что, если все фигуры будут пересекать одну клетку?
|
|||
|
||||
| Alexeis |
|
|||
|
Амеба Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 7 Всего: 459 |
Тогда будет полный перебор. Согласись это не типичный случай, тем более в случае редактора. Фигуры как-то распределены. Да и сетку можно варьировать, если площадь растет. Это не универсальное решение, зато оно проще. Если есть готовое решение Q-Tree, то конечно же лучше использовать его, но самому писать такое задача не для новичка. -------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
| Earnest |
|
|||
 Эксперт Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 33 Всего: 183 |
KasMP, не парься. Нормально написанная проверка PtInFigure занимает очень маленькое время при просмотре тысяч объектов (даже десятков тысяч). Сначала, конечно, проверь попадание точки в экстент фигуры. Пространственный индекс начинает быть нужным при 1) значительно бОльшем числе объектов 2) при необходимости реагировать, скажем, на движение мыши (а не на клики). Поверь, это было быстро еще несколько лет назад, при значительно менее мощных компьютерах. Во втором случае нужно строить пространственный индекс ребер, попавших в экран. Тогда тоже будет быстро. В смысле, не будет видимых пользователю задержек.
-------------------- ... |
|||
|
||||
| Lazin |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 8 Всего: 154 |
Earnest, в целом согласен, но все это добро еще нужно отрендерить, для этого нужно отсечь все то, что не будет видно, без пространственного индекса это сложно сделать
 |
|||
|
||||
| Earnest |
|
|||
|
Эксперт Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 33 Всего: 183 |
Смотря какой сложности фигуры. Если это полигоны с простыми текстурами (заливками), в количестве нескольких тысяч, то все будет летать без всякого индекса. Достаточно проверки попадания в экстент. Виндоус и сам прекрасно отсекает... Я имею в виду использование GDI.
Нет, конечно, можно постараться и написать тормозной код... видела и такое  Кстати, автор спрашивал только про поиск. Добавлено через 5 минут и 34 секунды Я это к тому, что поддержка индекса тоже кое-чего стоит, как на уровне дизайна, так и на уровне ресурсов и времени. Скажем, точки просто рассовать по кластерам, а уже с ребрами все сильно сложнее, чего уж говорить о полилиниях-полигонах. Да еще когда все это добро постоянно меняется... Размер кластера, кстати, тоже важно правильно выбрать - не мельчить ни в коем случае, только хуже будет. -------------------- ... |
|||
|
||||
| KasMP |
|
||||||||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: нет Всего: 30 |
А я не говорила про проще  .Но как красиво ты назвал самый примитивный перебор  !
Интересный вариант с округлением .Но здесь сразу же всплывают две сложно решаемые проблемы:
 Интересно.
Спасибо  ! Поразбираюсь с PtInFigure...Но что такое "экстент" ? Пожалуйста, пишите английские термины английскими буквами... Я еще не привыкла к ним настолько сильно .
Мммм... На всякий случай уточню: после нажатия левой кнопки (и определения фигуры, по которой щелкнули) мышка потащит фигуру куда-нибудь и там оставит (отпустили кнопку). Т.е. движение все-таки есть. Но как я понимаю, от массива объектов нам действительно нужен только поиск, выбор одного объекта, изменение его собственных параметров (новое местоположение) и изменение Z-order всего того, что связано с перемещением. |
||||||||||
|
|||||||||||
| Alexeis |
|
|||
|
Амеба Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 7 Всего: 459 |
Не будет такого. Все проверки остаются, только уменьшается список того что проверять, остается только список этой клетки, а он меньше во много раз. Большой перебор заменяется маленьким. -------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
| KasMP |
|
||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: нет Всего: 30 |
Упс, как все просто .Т.е. получается 2 этапа перебора, причем на первом многое (очень многое) отсекается. Понятно все. Хороший способ, вполне подходящий . Благодарю  .Посмотрим еще ...Добавлено через 3 минуты и 26 секунд
Это будут самые простые граф.примитивы - эллипсы, прямоугольники (даже не многоугольники!), прямые, кривые, ... . И их количество в самом страшном случае не превысит 30 .P.S.. Кстати, у меня возникает мысль, что решение проблемы кроется больше не в WinAPI, а в алгоритмах... |
||||
|
|||||
| Lazin |
|
||||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 8 Всего: 154 |
тогда забудь все что мы тут написали и
и делай все простым перебором |
||||
|
|||||
| Earnest |
|
|||
|
Эксперт Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 33 Всего: 183 |
Тогда можно делать в цикле раз 100 (ну, чтобы точно не ошибиться) Никто не заметит... Экстент - это прямоугольник со сторонами, параллельными координатным осям, описанный вокруг фигуры. Extent(s). Извини, если не точно выразилась, привыкла я эту хрень так называть. Вычисляется просто, можно хранить вместе с фигурой и проверка PtInRect очень простая и быстрая (если прямоугольник нормализован, т.е. left <= right и top <= bottom).... Функция "PtInFigure" - фигуральное выражение, для каждой фигуры надо писать свою проверку, и хорошо бы с учетом точности попадания. -------------------- ... |
|||
|
||||
|
|
| Правила форума "C/C++: Системное программирование и WinAPI" | |
|
|
На данный раздел распространяются Правила форума и Правила раздела С++:Общие вопросы . Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Chipset, Step, Fixin, GremlinProg, xvr. feodorv. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Системное программирование и WinAPI | Следующая тема » |
[ Время генерации скрипта: 0.1222 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |