12 Aug
2010
12 Aug
'10
6:05 p.m.
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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
12 Aug
12 Aug
6:21 p.m.
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
6:30 p.m.
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 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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
6:48 p.m.
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
8:09 p.m.
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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
8:20 p.m.
On 12.08.2010, at 20:09, Alexandre Bergel wrote:
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
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.
8:52 p.m.
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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
13 Aug
13 Aug
11:36 a.m.
On 12 août 2010, at 20:09, Alexandre Bergel wrote:
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
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.
14 Aug
14 Aug
12:04 a.m.
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
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
5002
days inactive
5003
days old
8 comments
3 participants
participants (3)
-
Alexandre Bergel -
Norbert Hartl -
Simon Denier