LINUX.ORG.RU

Алгоритм выделения точки

 , , ,


0

2

Всем привет!Перейду сразу к делу.

Использую последний Qt.В приложении есть область для рисования/операций над вершинами и ребрами. Рисование осуществляется при помощи OpenGL в виджете, который наследует QOpenGLWidget и QOpenGLFunctions. То есть имеется динамический массив вершин, которые потом будут отрисоваваться как GL_POINTS. Ну и динамический массив индексов массива вершин (для отрисовки ребер как GL_LINES в функции glDrawElements)

Размер области рисования может меняться. Матрица проекций генерируется функцией glOrtho(0.0,1.0,0.0,1.0,-1.0,1.0). То есть левый нижний угол всегда имеет координату (0.0,0.0), а правый верхний (1.0,1.0)

Помимо добавления вершин, их нужно еще выделять для разных преобразований над ними (двигать, соединить пару ребром и т.д.)

Вот у меня вопрос как раз относительно алгоритма выделения - хочется чтобы он был наиболее оптимальным по быстродействию.

Что приходит на ум: вершины,как мне кажется, стоить хранить в хэш-таблице (В Qt для этого QHash есть). Но есть 2 для меня проблемы:

1)Что именно сделать ключом вершины? Простое произведение x-координаты на y-координату не даст инъективного отображения.

Думаю проинвертировать биты x-координаты и полученное число умножить на y-координату и результат сделать ключом (можно инвертировать и y, без разницы, главное что-то одно). Однако беда в том, что точки на прямой x=y все еще будут иметь один и тот же ключ. Есть у кого предложения, по какому алгоритму считать ключ?

2)Когда я буду тыкать в область виджета, я 99,9% не попаду точно в точку, которая была ранее нарисована, а где-то рядом. То есть преобразовать координаты тыкнутого места в ключ и по нему смотреть вершину в хэш-таблице не получится..... то есть при тыкании нужно получать что-то вроде диапазона ключей, размер которого зависит радиуса выделения (тыкнутая точка - центр окружности) и потом ,oh my god!, проверять, если что-то из диапазона ключей в хэш-таблице, и не просто есть ли, а самое ближайшее к ключу тыкнутой точки. Сомневаюсь я, что это будет быстро. Однако всякие Blender-, 3dMax-ы, Maya : тыкнешь в окне проекций - и вершина тут же выделена, и она будет выделена также быстро в том числе и в окне перспективы - а там и вовсе работа с трехмерным.

Вот какой алгоритм? Может я что упускаю/туплю/не знаю? Наверняка у всего этого должно быть какое-то изящное решение.

Не особо в теме, но с OpenGL есть как минимум 2 варианта: см. разделы 3.10 Трансформационный реверс и 14.6 Выбор объектов с помощью заднего буфера.

xaizek ★★★★★
()

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

Frost ★★★
()
Последнее исправление: Frost (всего исправлений: 2)

Разбей окошко на сетку, номера ячеек будет хеш-значениями для точек. Чтобы быстро найти ближайшую к курсору точку, смотрим на ячейку под курсором, а также на ячейки вокруг неё.

kvap
()

Храни в хэшмапе вершины с их окрестностями. Сделай функцию сравнения окрестностей такой: окрестности совпадают, если они пересекаются. Пользователь выбирает точку, ты берёшь окрестность этой точки, и ищешь в хэшмапе. Функция сравнения позволит выбрать именно нужные тебе окрестности и соответственно нужные вершины. В жабе ЕМНИП сравнение может вестись как по equals так и по hashCode нужно быть осторожным с этим. Как в с++ не знаю. Как кодировать прямоугольные окрестности точек в ограниченном множестве X*Y - ну блин, для точки это x*N+y, где N>=max(x,y) по всем x из X и y из Y.

anonymous
()
Ответ на: комментарий от Frost

Пойду курить «OpenGL руководство по программированию» по совету xaizek. Если выйдет нормально, оставлю.Если нет, буду париться с хэшами и окрестностями.

Nerevarino
() автор топика
Ответ на: комментарий от Nerevarino

буду париться с хэшами и окрестностями.

Так точно не надо. Есть K-мерные деревья. В данном случае 2d-дерева может хватить, они быстрые (логарифмическая сложность) и могут реализовывать операцию выборки в диапазоне. Т.е. выделяется прямоугольная область, а на выходе список точек в ней. При клике можно просто генерировать прямоугольную окрестность и использовать её. Я не стал это упоминать сразу, тут вроде были специалисты по графике, думал они откомментируют.

Реализация такого у меня даже есть, но на Java, хотя суть от этого не меняется, главное структура данных и алгоритм. Так что если надо, могу как-нибудь передать.

xaizek ★★★★★
()
Ответ на: комментарий от xaizek

Пока не надо, я после сообщения на форуме этим не занимался, гляну завтра.Но все равно спасибо)

Nerevarino
() автор топика
Ответ на: комментарий от xaizek

для плюсов есть реализации r-tree ему хватит

Deleted
()

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

Deleted
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.