Как обнаружить клик по краю мультиграфа?

Я написал приложение с графическим интерфейсом на основе Win32 API, которое использует функции GDI+, такие как DrawCurve() и DrawLine().

Это приложение рисует линии и кривые, которые представляют мультиграф.

Структура данных для ребра представляет собой просто структуру из пяти целых чисел. (x1, y1, x2, y2 и идентификатор)

Если между двумя вершинами есть только одно ребро, отрезок прямой линии рисуется с помощью DrawLine(). Если имеется более одного ребра, кривые рисуются с помощью DrawCurve(). Здесь я расширяю прямолинейные ребра вокруг средней точки двух вершин, делая их кривыми. Точка, отстоящая от нее на несколько единичных пикселей, вычисляется с использованием уравнения нормальной линии. Если добавляется больше ребер, то выбирается пиксель, отстоящий от средней точки на два единичных пикселя, затем в следующий раз — на 3 единичных пикселя и так далее.

Теперь у меня есть два вопроса по обнаружению щелчка по краям.

  1. Что мне делать при поиске прямых ребер, чтобы минимизировать время поиска?
    Проверить, находится ли выбранный пиксель на сегменте прямой, довольно просто, но сравнение всех ребер будет неэффективным, если количество ребер велико. Кажется возможным сделать это за O(log n), где n — количество ребер.
    РЕДАКТИРОВАТЬ: на данный момент ребра (класс Edge) хранятся в std::map, который отображает идентификатор ребра (int)' s в объекты Edge, и я подумываю объявить еще один контейнер, который сопоставляет пиксели с идентификаторами ребер.
    Я рассматриваю возможность использования бинарных деревьев поиска, но что может быть ключом? Или я должен использовать только массив 2D-пикселей?

  2. Могу ли я получить массив точек, используемый DrawCurve()? Если это невозможно, то я должен пересчитать кардинальный сплайн, получить массив точек и проверить, соответствует ли точка, по которой щелкнул пользователь, какой-либо точке в этом массиве.


graph winapi edge-detection gdi+
person Jeffrey Goines    schedule 06.11.2012    source источник
comment
Цель состоит в том, чтобы просто определить, был ли щелчок по краю, или вам нужно получить значение в зависимости от того, где на краю был щелчок?   -  person    schedule 06.11.2012
comment
Просто определить, какой край нажат, это нормально. Затем будет получен идентификатор ребра и будет выполнен поиск std::map‹id, ​​Edge*›.   -  person Jeffrey Goines    schedule 06.11.2012

Ответы (1)


arrow_upward
0
arrow_downward

Если у вас есть линии сложной формы, вы можете сделать следующее:

  • Создайте внутреннее растровое изображение размером с график и залейте его черным цветом.
  • Когда вы визуализируете свой график, также визуализируйте в этом растровом изображении ребра, которые вы хотите иметь кликабельными, но визуализируйте их другим цветом. Сохраните эти значения цвета в таблице вместе с соответствующим идентификатором. Здесь важно, чтобы цвета были разными (уникальными).
  • Когда график щелкнут, перенесите координаты X и Y во внутреннюю растровую карту и прочитайте пиксель. Если цвет не черный, найдите значение цвета в таблице и получите соответствующий идентификатор.

Таким образом, вам вообще не нужно беспокоиться о форме, а также нет необходимости использовать свой собственный алгоритм кривой и так далее. Стоимость дополнительной памяти, это будет учитываться, но если это не огромный график (в этом случае вы можете буферизовать рисунок), в большинстве случаев это не проблема. Вы можете визуализировать внутреннее растровое изображение во втором проходе, чтобы основная графика отображалась быстрее (как обычно).

Надеюсь это поможет!

(Совет: вы можете визуализировать «внутренние» линии более широким пером, чтобы оно стало более чувствительным).

person Community    schedule 06.11.2012
comment
В разрешении 1920 x 1080 с 32 битами на пиксель (таким образом, максимальное количество ребер, которые можно нарисовать за раз, равно 2^32), требуется примерно 8 МБ пространства для обнаружения щелчка по краю для каждого представления графика (здесь я предположил, что холст размер фиксирован, так как частое перераспределение буфера растрового изображения может значительно снизить производительность). Я думаю, что это самый простой и быстрый (O(1)) способ реализации, но сначала казалось, что он занимает слишком много места (O(xy)~=O(n^2)). Тем не менее, я мог бы понизить bpp и уменьшить размер буфера растрового изображения, поскольку практически кривые больше нескольких тысяч даже не видны при объединении. - person Jeffrey Goines; 06.11.2012
comment
Конечно, если не видно = нельзя щелкнуть, так что вы можете исключить перекрывающиеся экземпляры. И, как вы говорите, можно также квантовать точки щелчка, уменьшив вдвое растровое изображение, а также координаты x/y, или даже уменьшить растровое изображение до 1/4, имея каждую доступную для щелчка точку в области 4x4 пикселя, но если у вас одновременно присутствует много ребер, что может быть не так удобно. Я бы использовал только 24 бита на пиксель (2 ^ 24 или 16,8 миллионов разных цветов - или даже 16-битное растровое изображение), так как в пространстве 1920x1080 вы все равно никогда не сможете использовать весь этот цвет, поскольку есть только примерно 2 миллиона. пикселей, доступных на экране. - person ; 06.11.2012