Карта точек элемента для элемента холста html5, нужен алгоритм

Question

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

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

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

Answer 1

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

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

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