Каков алгоритм поиска объектов под курсором?
Хочу написать (на FPC или FB) очень даже простой векторный редактор типа старого АвтоКада,
получается проблема представить эффективный алгоритм определения какие объекты должны подсвечиваться при перемещении курсора или быть выбраны при нажатии!
Мне известен "игровой" алгоритм определения объектов через параллельную плоскость где по цвету под курсором определяется принадлежность точки объекту, я думаю он не подходит, так как не справится при наложении нескольких объектов, и для определения соседних объектов для подсвечивания.
Прямой перебор всех созданных объектов и сравнение координат может все функции что мне нужны но мне он представляется ужасно медленным!
Нужна помощь!
получается проблема представить эффективный алгоритм определения какие объекты должны подсвечиваться при перемещении курсора или быть выбраны при нажатии!
Мне известен "игровой" алгоритм определения объектов через параллельную плоскость где по цвету под курсором определяется принадлежность точки объекту, я думаю он не подходит, так как не справится при наложении нескольких объектов, и для определения соседних объектов для подсвечивания.
Прямой перебор всех созданных объектов и сравнение координат может все функции что мне нужны но мне он представляется ужасно медленным!
Нужна помощь!
Именно сравнение координат курсора с координатами объектов и используется. Если объектов очень много, то можно использовать хеширование координат и объектов. Как правило, алгоритмы проверки принадлежности точки объекту не очень сложные. Объекты можно классифицировать по их местоположению (разбив пространство на участки), а затем искать нужные предметы только в том участке, в котором находится курсор. Это методы похожие на алгоритмы поиска столкновений, например QuadTree, но в Вашем случае это поиск столкновения курсора с объектом.
Вот небольшой пример, не совсем по теме, но поиск под курсором есть.
Вот небольшой пример, не совсем по теме, но поиск под курсором есть.
Спасибо))
Но все равно что то гложут сомнения что это будет быстро.
И я не понял как можно применить здесь хеширование, что сворачивать?
Координаты узловых точек надо напрямую сравнивать, здесь хешированием ничего не выиграть - нечего упрощать в сравнении.
Для определения пересечения с промежуточной точкой отрезков, нужно решение уравнения - где здесь применять хеширование?
Также и при определении что курсор приближается к узловым точкам или соединяющих их линиям!
Если можешь, расскажи наглядно!
Или покажи цикл поиска, упрощенно - хоть на псевдокоде / комментариях
- пожалуйста!
Но все равно что то гложут сомнения что это будет быстро.
И я не понял как можно применить здесь хеширование, что сворачивать?
Координаты узловых точек надо напрямую сравнивать, здесь хешированием ничего не выиграть - нечего упрощать в сравнении.
Для определения пересечения с промежуточной точкой отрезков, нужно решение уравнения - где здесь применять хеширование?
Также и при определении что курсор приближается к узловым точкам или соединяющих их линиям!
Если можешь, расскажи наглядно!
Или покажи цикл поиска, упрощенно - хоть на псевдокоде / комментариях
- пожалуйста!
Предположим, область вывода графики имеет размеры 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 мы попадаем в какой-то элемент списка, а элемент списка это список точек, или объектов среди которых придется осуществить прямой перебор, как ты и боялся делать. Просто, в данном случае перебор делается для гораздо меньшего числа объектов.
ЗЫ
Координаты узловых точек, скорее всего, не придется сравнивать напрямую, если не хочешь, конечно, заставлять пользователя целиться и попадать в конкретные пиксели экрана. Пользователь, все равно должен попадать в некоторую характерную область.
ЗЫ
Координаты узловых точек, скорее всего, не придется сравнивать напрямую, если не хочешь, конечно, заставлять пользователя целиться и попадать в конкретные пиксели экрана. Пользователь, все равно должен попадать в некоторую характерную область.
Однако, для твоих целей лучше обратить внимание на алгоритм QuadTree.
Если векторный редактор - то сделай список объектов с определёнными аттрибутами в том числе и координаты, + еще как советует Meander, сделай кеш - это будет многомерный массив. Каждый элемент будет представлен куском пространства, в котором будут записываться айдишники объектов.