Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11631
Последний выпуск: 19.06.2015

Каков алгоритм поиска объектов под курсором?

88K
27 декабря 2014 года
SimplePoint
2 / / 27.12.2014
Хочу написать (на FPC или FB) очень даже простой векторный редактор типа старого АвтоКада,
получается проблема представить эффективный алгоритм определения какие объекты должны подсвечиваться при перемещении курсора или быть выбраны при нажатии!
Мне известен "игровой" алгоритм определения объектов через параллельную плоскость где по цвету под курсором определяется принадлежность точки объекту, я думаю он не подходит, так как не справится при наложении нескольких объектов, и для определения соседних объектов для подсвечивания.
Прямой перебор всех созданных объектов и сравнение координат может все функции что мне нужны но мне он представляется ужасно медленным!
Нужна помощь!
407
27 декабря 2014 года
Meander
487 / / 04.09.2011
Именно сравнение координат курсора с координатами объектов и используется. Если объектов очень много, то можно использовать хеширование координат и объектов. Как правило, алгоритмы проверки принадлежности точки объекту не очень сложные. Объекты можно классифицировать по их местоположению (разбив пространство на участки), а затем искать нужные предметы только в том участке, в котором находится курсор. Это методы похожие на алгоритмы поиска столкновений, например QuadTree, но в Вашем случае это поиск столкновения курсора с объектом.
Вот небольшой пример, не совсем по теме, но поиск под курсором есть.
Прикрепленные файлы:
480 Кб
Загрузок: 150
88K
27 декабря 2014 года
SimplePoint
2 / / 27.12.2014
Спасибо))
Но все равно что то гложут сомнения что это будет быстро.
И я не понял как можно применить здесь хеширование, что сворачивать?
Координаты узловых точек надо напрямую сравнивать, здесь хешированием ничего не выиграть - нечего упрощать в сравнении.
Для определения пересечения с промежуточной точкой отрезков, нужно решение уравнения - где здесь применять хеширование?
Также и при определении что курсор приближается к узловым точкам или соединяющих их линиям!

Если можешь, расскажи наглядно!
Или покажи цикл поиска, упрощенно - хоть на псевдокоде / комментариях
- пожалуйста!
407
27 декабря 2014 года
Meander
487 / / 04.09.2011
Предположим, область вывода графики имеет размеры 500 на 500 пикселей. Разобьем данную область на 100 подобластей размером 50 на 50 пикселей. Тогда, если мы поделим координаты курсора на 50, то получим координаты курсора в пространстве наших подобластей. Например координаты курсора x=24, y=20, целочисленно деля на 50 получим X=0, Y=0. Это означает, что курсор находится в верхней левой подобласти. Значит, искать попадание курсора в объект следует искать среди объектов, которые находятся в подобласти с координатами X=0, Y=0. Все объекты помещаются и хранятся в хеш таблице. Эта таблица может представлять из себя список из 100 элементов. Тогда, адрес элемента списка может быть вычислен по формуле Z=Y*50+X. По координатам X и Y мы попадаем в какой-то элемент списка, а элемент списка это список точек, или объектов среди которых придется осуществить прямой перебор, как ты и боялся делать. Просто, в данном случае перебор делается для гораздо меньшего числа объектов.
ЗЫ
Координаты узловых точек, скорее всего, не придется сравнивать напрямую, если не хочешь, конечно, заставлять пользователя целиться и попадать в конкретные пиксели экрана. Пользователь, все равно должен попадать в некоторую характерную область.
407
27 декабря 2014 года
Meander
487 / / 04.09.2011
Однако, для твоих целей лучше обратить внимание на алгоритм QuadTree.
1.9K
28 декабря 2014 года
Kuzya
183 / / 19.03.2008
Если векторный редактор - то сделай список объектов с определёнными аттрибутами в том числе и координаты, + еще как советует Meander, сделай кеш - это будет многомерный массив. Каждый элемент будет представлен куском пространства, в котором будут записываться айдишники объектов.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог