Timeline for Search algorithm with co-ordinate (x,y) hints?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2022 at 6:24 | comment | added | Stephane |
I wonder what is meant with hash the leave nodes
|
|
| Jan 26, 2012 at 7:59 | comment | added | trojanfoe | Both, but mostly the number of text items will increase as the user interacts with the view. | |
| Jan 25, 2012 at 18:45 | comment | added | sebastiangeiger | The text items will grow in number or individual text items will change their size? If they change their size it might be an issue since you have to remove them from the tree and reinsert them with the new hit box. If they grow in number there is nothing that you can really do, except find a better datastructure/algorithm ;-) | |
| Jan 25, 2012 at 14:41 | comment | added | trojanfoe | This is an interesting point; the 'text items' will grow regularly as the user interacts with the application. Will this growth cause an issue? | |
| Jan 25, 2012 at 13:02 | comment | added | user8709 | I don't think "not a quadtree", just "not an explicit quadtree". Kind of like the binary heap data structure is built in an array without links rather than as a binary tree - just because you calculate the links on the fly rather than storing them doesn't mean it isn't a binary heap (or quadtree). | |
| Jan 25, 2012 at 12:32 | comment | added | sebastiangeiger | @Steve314 You're right, this is not really a quadtree. I abused the idea if anything, since the tree would always have a fixed number of nodes. As for the resizing problem I would imagine having a "workspace" or "canvas" that is independent from the window size or the viewport shown in the window. The (x,y) I am describing would then be already in workspace coordinates. | |
| Jan 25, 2012 at 12:22 | comment | added | user8709 | Nice answer, but the way you describe this, you don't need quadtree nodes with links. For any particular size window, the structure is fixed - with some careful integer math you can step up from single pixel to larger and larger areas in a way that mirrors the quadtree structure. A hash of the bounds can then be used to look up the list of all rectangles for that node. Simpler still, use exact quadrupling per step up the quadtree - slightly imbalanced, but you don't have to reindex for window resizing. | |
| Jan 25, 2012 at 12:09 | comment | added | sebastiangeiger | You're welcome. I'd be interested if this actually works :-) | |
| Jan 25, 2012 at 9:40 | comment | added | trojanfoe | Lovely answer - many thanks! I'll let you know how I got on with it. | |
| Jan 25, 2012 at 9:40 | vote | accept | trojanfoe | ||
| Jan 25, 2012 at 8:14 | history | edited | sebastiangeiger | CC BY-SA 3.0 |
Algorithm outline
|
| Jan 25, 2012 at 7:57 | history | answered | sebastiangeiger | CC BY-SA 3.0 |