As long as the shapes are simple, in a UML diagram you have mostly boxes, some arrows, and text, AABB bounding boxes are easy to compute, as long as your not worrying about overlapping shapes which could be hollow:, i.e. you have a large rectangle with a small rectangle inside, the large one is NOT filled, but has a higher z-index, the inside-outsize line projection is reasonable and efficient. The question is, if the higher z-order rectangle in hollow ( you didn't fill it ), and your mouse falls within the smaller one inside, which did you mean to pick?
I knows Alfredo is right as I wrote most of Lienzo ;-) I have about 30 years working in structured graphics. It was EXACTLY for this reason, that it's not always trivial to do this kind of stuff if you are a beginner, that we decided to write it and make it Apache 2 and give it away, and would love if people used it and gave us feedback. Hey, it's free. Also, soon, we will be adding optimal DAG layout in a toolkit on top of Lienzo. Right now were taking a breather after getting 1.0 out the door and enjoying the holidays and family, as Lienzo was written after we got home from our day jobs, sometimes tlll 3 or 4am, much to the dismay of our loved ones ;-) On Thursday, December 20, 2012 1:00:15 PM UTC-5, RyanZA wrote: > > 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/-/zuzz4QjRyf4J. 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.
