A bounding box check isn't O(1), it's O(n) for n shapes, THEN you have to run edge detection, and only then if all your shapes are Polygons. The issue with bounding boxes is that, in all but the most trivial cases, they are expensive to compute. If you add in any Affine Transforms ( rotate, scale, shear ) the task becomes even worse, and worse still is the bounding boxes of Quadratic or Bezier curves.
With a large number of shapes, you can gain some speed using Quadtree's http://en.wikipedia.org/wiki/Quadtree and other types of spatial indexing. But you have 4 checks per "primitive", not 2 (x > box.left && x < box.right && y > box.top && y < box.bottom), so you need to keep 4 coordinates. For a large number of shapes, this uses memory, more memory if you choose to use a Quadtree or similar spatial indexing. So, I have found the color indexing option the best, it's not quite O(1), as it's performance depends on the hashmap lookup time. The downside is you only have 167772316 possible color keys, I feel this is acceptable limitation. This could be helped by having multiple "layers" with each layer having it's own full colorspace. Hashmap lookup time should be near optimal since an analysis of collisions with out keys yeilds about 1100 out of 167772316, which is pretty good. As a side note, HashMap in GWT is not an optimal implementation for this case. The other downside is you have to draw also in the "ghost canvas", but we found our drawing time so fast it was not a concern. isPointInPath only works while the Path is CURRENT in the Canvas context 2d, which you lose after drawing another shape or context.restore(), so it's only possible to test IMMEDIATELY after you draw the shape, before you do any context.restore(), which means you have to be drawing somewhere while your doing hit testing, probably another ghost canvas. This also only works for "closed shapes", not something like a PolyLine or Arc. On Thursday, December 20, 2012 8:29:40 AM UTC-5, RyanZA wrote: > > First option is definitely best, but you need to expand it slightly: > > Use a bounding box around every shape, so you can do an O(1) check if the > click is inside the bounding box (click.x < box.left, click.x > box.right, > etc) > If the click is inside the bounding box, then you can run normal edge > detect O(number of lines per poly) -- (drop a line to the axis, count > number of line intersections - check stackoverflow or similar for code) > > If you have Z index on your shapes, then start from the biggest Z index > and take the first match. > If you are drawing in a list, then start from the bottom of the list and > work upwards and take the first match. > > On Thursday, December 20, 2012 1:14:43 PM UTC+2, membersound wrote: >> >> I'm creating some kind of drawings/flowchart/UML-diagram like tool with >> GWT Canvas (Java). >> For hit-detection of my drawings I could imagine 3 different strategies, >> but I do not know which would work best for my goal. >> >> - Just keep track of all Shape coordinates and iterate all objects on >> mouseclick >> - draw all objects on a ghost-canvas on mouseclick, and use >> isPointInPath() after every object drawing >> - using a ghost-canvas and draw each object with its own color (like >> #000001, #000002), and keep reference of them in a Map<Color, Shape>. Then >> just detecting the mouseclick on the ghost-canvas and get the object >> belonging to the pixelcolor under mouse >> >> What would you prefer, and why? >> > -- You received this message because you are subscribed to the Google Groups "Google Web Toolkit" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-web-toolkit/-/yh3u7EtPQq4J. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-web-toolkit?hl=en.
