The check itself is obviously O(1) per check, as opposed to O(num of lines) for his original proposal (iterate all shape components) - and the 'etc' should have kind of implied to you there were 4 checks and not 2...
Also, he is not making a 3d engine here and is very unlikely to need anything more than AABB bounding boxes. You don't need a minimum bounding box for this, just a general one. He is making flowcharts/UML diagrams, and is unlikely to have more than a few hundred shapes - which performs exceptionally well on AABB bounding boxes and simple polygon checks. If he is implementing this himself, then spending the next year developing a perfect object selection engine feels a bit overkill for his needs? Alfredo has the right idea though - nearly always best to go with a library that has already had all of this done for him - provided he can fit his flowchart/UML code into the Lienzo scene graph. :) On Thursday, December 20, 2012 6:28:54 PM UTC+2, Dean S. Jones wrote: > > 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/-/DArDlQ0dzLUJ. 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.
