Quadtree in Mondrian
Locked
 
|
Hi!
Thanks to Simon, there is a MOQuadTree class and its tests in Mondrian. Quadtree is a tree data structure that is used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. We could imagine plenty of new caches using quad trees. I haven't seen any complain about speed anymore. However, I feel you restraint _yourself_ from pushing Mondrian to its limits :-) If you experience any slowdown, please keep a description of what you have done before changing your visualization. QuadTree are probably the way to go if we want to reach 1,000,000 nodes :-) Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
On 12 août 2010, at 18:05, Alexandre Bergel wrote: > Hi! > > Thanks to Simon, there is a MOQuadTree class and its tests in Mondrian. Quadtree is a tree data structure that is used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. We could imagine plenty of new caches using quad trees. Thanks Alex But does it mean you started to use QuadTree or not? It may be the way to go, but last time I tried I was a bit deceived. I think my implementation currently lacks some optimization. First step, we could do some benchmarks on QuadTree. > > I haven't seen any complain about speed anymore. However, I feel you restraint _yourself_ from pushing Mondrian to its limits :-) > If you experience any slowdown, please keep a description of what you have done before changing your visualization. > > QuadTree are probably the way to go if we want to reach 1,000,000 nodes :-) -- Simon _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
>> Thanks to Simon, there is a MOQuadTree class and its tests in Mondrian. Quadtree is a tree data structure that is used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. We could imagine plenty of new caches using quad trees.
> > Thanks Alex > > But does it mean you started to use QuadTree or not? Not yet. I am cleaning Mondrian and I stumbled on this class. > It may be the way to go, but last time I tried I was a bit deceived. I think my implementation currently lacks some optimization. First step, we could do some benchmarks on QuadTree. I would also like to have some scenarios that show the current limit of Mondrian. A simple one is "view nodes: (1 to: 100000)". It takes time since the search is linear. QuadTree should considerably speed the thing up. Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
In reply to this post by Alexandre Bergel
On 12.08.2010, at 18:05, Alexandre Bergel wrote: > Hi! > > Thanks to Simon, there is a MOQuadTree class and its tests in Mondrian. Quadtree is a tree data structure that is used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. We could imagine plenty of new caches using quad trees. > > I haven't seen any complain about speed anymore. However, I feel you restraint _yourself_ from pushing Mondrian to its limits :-) > If you experience any slowdown, please keep a description of what you have done before changing your visualization. > > QuadTree are probably the way to go if we want to reach 1,000,000 nodes :-) > Hmmm, I'm looking for a quad tree implementation :) Is it bound to Mondrian? Norbert _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
> Hmmm, I'm looking for a quad tree implementation :) Is it bound to Mondrian?
Yeah! Load Mondrian (http://www.squeaksource.com/Mondrian.html), it contains MOQuadTree. It comes with very few tests however. MOQuadTree is not bound to Mondrian. However, I find convenient to leave it in Mondrian. What you need it for? Just curious. Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
On 12.08.2010, at 20:09, Alexandre Bergel wrote: >> Hmmm, I'm looking for a quad tree implementation :) Is it bound to Mondrian? > > Yeah! > Load Mondrian (http://www.squeaksource.com/Mondrian.html), it contains MOQuadTree. It comes with very few tests however. > MOQuadTree is not bound to Mondrian. However, I find convenient to leave it in Mondrian. > > What you need it for? Just curious. > I build a fun application using pier. It is still small and very experimental. It's about wine. And spatial/geographical information is important for the site. Quadtrees are extremely useful for geographical applications. Usually the world is divided into a mesh of equal distant squares. This squares map onto the deepness levels of a quadtree. Tile graphics like google maps are managed in a similar way. This way round it is easy to find important spots (called POI = points of interest) fast. You just need to convert latitude/longitude in x/y dimensions and with an additional parameter of zoom a quad tree gives you everything you wanna know. For the opposite direction (finding areas of most interest without having discrete dimensions) R-Trees are pretty useful. They are not balanced by area they occupy but balanced through the amount of data that is in or near to a certain spot. Just in case you wanted to know the longer version Norbert _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
> I build a fun application using pier. It is still small and very experimental. It's about wine.
About wine, that's interesting > And spatial/geographical information is important for the site. Quadtrees are extremely useful for geographical applications. Usually the world is divided into a mesh of equal distant squares. This squares map onto the deepness levels of a quadtree. Tile graphics like google maps are managed in a similar way. This way round it is easy to find important spots (called POI = points of interest) fast. You just need to convert latitude/longitude in x/y dimensions and with an additional parameter of zoom a quad tree gives you everything you wanna know. > For the opposite direction (finding areas of most interest without having discrete dimensions) R-Trees are pretty useful. They are not balanced by area they occupy but balanced through the amount of data that is in or near to a certain spot. That is interesting. I would love to have a reliable and fast quadtree implementation. If there is anything I could try out, let me know. I would love to. Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
In reply to this post by Alexandre Bergel
On 12 août 2010, at 20:09, Alexandre Bergel wrote: >> Hmmm, I'm looking for a quad tree implementation :) Is it bound to Mondrian? > > Yeah! > Load Mondrian (http://www.squeaksource.com/Mondrian.html), it contains MOQuadTree. It comes with very few tests however. > MOQuadTree is not bound to Mondrian. However, I find convenient to leave it in Mondrian. > > What you need it for? Just curious. I made a quick review of my code this morning. I'm happy to see that it's still readable and quite easy to understand (provided one knows the basics of QuadTree) :) There is no specific dependency to Mondrian. The only requirement is that elements added to the quadtree should respond to #bounds, like MOGraphElement (which was the basic element to be stored in MOQuadTree). When we tested MOQuadTree in Mondrian last year, there was some deception because it was difficult to plug efficiently a recursive structure like QuadTree in the Mondrian rendering loop, which is already recursive. In the end, it was not efficient because we had to rely on a slow Set implementation. Nowadays, I think there will be still trouble with this aspect (plug both recursive structures together?). However, I also made a quick review of other QuadTree today and it appears I may have made a wrong hypothesis (namely that elements are only stored in leaves, not in the composite nodes of a quadtree, hence Set should not be needed). See http://www.codeproject.com/KB/recipes/QuadTree.aspx So what to be done? 1) perform code review of the current MOQuadTree. I would be more than happy if you could review the code, as I am no specialist. And as said above, I believe there are some mistakes. 2) write benchmarks before changing the implementation. -- Simon _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
|
|
> So what to be done?
> 1) perform code review of the current MOQuadTree. I would be more than happy if you could review the code, as I am no specialist. And as said above, I believe there are some mistakes. > 2) write benchmarks before changing the implementation. > Yes, this will be cool! Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
«
Return to Moose
|
1 view|%1 views
| Free forum by Nabble | Edit this page |