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

Ваш аккаунт

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

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

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

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

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

Если можешь, расскажи наглядно!
Или покажи цикл поиска, упрощенно - хоть на псевдокоде / комментариях
- пожалуйста!
446
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 мы попадаем в какой-то элемент списка, а элемент списка это список точек, или объектов среди которых придется осуществить прямой перебор, как ты и боялся делать. Просто, в данном случае перебор делается для гораздо меньшего числа объектов.
ЗЫ
Координаты узловых точек, скорее всего, не придется сравнивать напрямую, если не хочешь, конечно, заставлять пользователя целиться и попадать в конкретные пиксели экрана. Пользователь, все равно должен попадать в некоторую характерную область.
446
27 декабря 2014 года
Meander
487 / / 04.09.2011
Однако, для твоих целей лучше обратить внимание на алгоритм QuadTree.
1.8K
28 декабря 2014 года
Kuzya
184 / / 19.03.2008
Если векторный редактор - то сделай список объектов с определёнными аттрибутами в том числе и координаты, + еще как советует Meander, сделай кеш - это будет многомерный массив. Каждый элемент будет представлен куском пространства, в котором будут записываться айдишники объектов.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог