Элементная точка для элемента html5 canvas, нужный алгоритм

Question

В настоящее время я работаю над реализацией холста pure html 5 «облачной облачности летающих тегов», которую многие из вас, несомненно, рассматривают как флеш-объект на некоторых страницах.

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

Что мне нужно сделать в этом случае - это поймать событие click и попытаться «угадать», какой элемент был нажат. Поэтому у меня должна быть какая-то матрица, которая хранит ссылку на объект тега для каждого пикселя на холсте, и мне нужно обновить эту матрицу при каждом перерисовании. Теперь это звучит невероятно неэффективно, и, прежде чем я даже начну пытаться реализовать это, я хочу спросить сообщество - есть ли какой-то «хорошо известный» алгоритм, который мне помог бы в этом случае? Или, может быть, я просто что-то упустил, и ответ за углом? :)

Answer 1

Это называется point location problem, и это одна из основных тем в вычислительной геометрии. Есть много методов, которые вы могли бы использовать, это было бы намного быстрее, чем подход, о котором вы думаете, но детали зависят от того, что именно вы хотите выполнить.

Например, каждая текстовая строка содержится в ограничивающей рамке. Вы просто хотите проверить, нажал ли пользователь где-нибудь в этом поле? Затем просто сохраните минимальную и максимальную координаты каждой отображаемой строки и проверьте точку на каждом ограничивающем поле, чтобы увидеть, содержится ли она в этом диапазоне. Если у вас есть большое количество очков для тестирования, вы можете построить любое количество структур данных, чтобы ускорить это (например, R-trees), но для одной точки накладные расходы на создание такой структуры, вероятно, не стоят.

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