Element point map for html5 canvas element, need algorithm
I am currently working on a pure html 5 canvas implementation of the "flying tag cloud", which many of you will no doubt see as a flash object in some pages.
The tags are rendered fine and the performance is satisfactory, but there is one thing about the canvas element that violates this idea: you cannot identify the objects you have drawn on the canvas, as it is just a flat "image" ..
What I need to do in this case is to catch the click event and try to "guess" which element was clicked. Therefore, I must have some kind of matrix that stores a reference to the tag object for every pixel in the canvas, and I need to update this matrix on every redraw. Now this sounds incredibly inefficient, and before I even start trying to implement this, I want to ask the community - is there some "well known" algorithm that will help me in this case? Or maybe I'm just missing something and the answer is around the corner? :)
a source to share
This is called the point location problem , and it is one of the main topics in computational geometry. There are many methods you could use, this would be much faster than the approach you are thinking of, but the details depend on what you want to accomplish.
For example, each text line is contained within a bounding box. Do you just want to check if the user has clicked anywhere in this field? Then just store the minimum and maximum coordinates of each displayed line and check the point on each bounding box to see if it is contained within that range. If you have a lot of points to test, you can create any number of data structures to speed this up (like an R-tree ), but for one point, the overhead of creating such a structure is probably not worth it.
If you're wondering if the point falls within the opaque area of the stroked characters, the problem is a little more complicated. One solution would be to use a bounding box approach to eliminate most of the possibilities first, and then display the remaining lines one at a time to the shutter buffer, checking each time to see if the target point has been affected.
a source to share