Rebalancing a Quad Tree

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Rebalancing a Quad Tree

Postby MHD » Tue Jan 18, 2011 9:50 pm UTC

Say you have a Quad Tree with the keys being coordinates for a two dimensional plane.

If these keys change, how would one rebalance it?
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby Meteorswarm » Wed Jan 19, 2011 2:35 am UTC

This smells like homework - could you give us some context?
The same as the old Meteorswarm, now with fewer posts!

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby kmatzen » Wed Jan 19, 2011 3:03 am UTC

This article has details how to rebalance a quad tree. You just have some entities moving around a map and have to update their coordinates, right?

I don't care too much if this is for homework. This is easy to find via Google.
http://valis.cs.uiuc.edu/~sariel/teach/ ... adtree.pdf

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: Rebalancing a Quad Tree

Postby MHD » Wed Jan 19, 2011 6:38 am UTC

This isn't homework, my hobby projects are just pretty weird. I don't even have computer science as a class.

It's for a little challenge between me and a friend, where we build small games of little soldiers who kill each other in four teams and yadda yadda.

I code in haskell with openGL and he uses game maker.
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby kmatzen » Wed Jan 19, 2011 8:03 am UTC

MHD wrote:I code in haskell with openGL


I didn't realize people did this.

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: Rebalancing a Quad Tree

Postby MHD » Wed Jan 19, 2011 2:48 pm UTC

kmatzen wrote:
MHD wrote:I code in haskell with openGL


I didn't realize people did this.


The IO monad makes OpenGL a dream, GLUT eliminates all of the platform specifics and haskell is 40%-60% less code compared to C. Furthermore, a simple "cabal install opengl" nets you the library automatically, as for speed, it's about the same as Java.

Also, it's effing haskell.

Benefits: Many
Drawbacks: Few
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby kmatzen » Wed Jan 19, 2011 8:37 pm UTC

I don't know anything about Haskell, so I went on the website and read through the "Why Haskell matters" article. The section on Haskell vs. OOP was interesting to me. The way they describe how Haskell works sounds exactly how we were taught to do object-based programming in C when I took an OOP class. In that class we first learned how to use C for things like encapsulation, inheritance, polymorphism, etc, but it required extremely error prone code. I just find it odd that the article doesn't mention this, even as a quick history recap. It should be like, you know those methods you used in C? Well. We gave those tricks new names and made them type safe. Even this idea of type classes fits in which how the C++ STL was designed. There isn't really any inheritance going on in there. They just did some operator overloading so that iterators and arrays all work the same, containers work the same, etc. and just let the compiler enforce the existence of certain class functions so that the STL algorithms can go in an do their jobs. The class hierarchy would be a horrible mess otherwise. I guess in this case, they just don't use a compiler to enforce the requirement. It also strikes me odd that they don't just make an analogy to Java's interfaces at this point in the article.

I was thinking about the times where I was doing some game programming and the GC was the bottleneck. This was at least my experience on the Xbox 360, but then again, the GC on the Xbox is only a single generation so when it does get invoked it's sllllllllllllllooooowww as it goes over the entire heap.

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby Meteorswarm » Thu Jan 20, 2011 4:33 am UTC

MHD wrote:This isn't homework, my hobby projects are just pretty weird. I don't even have computer science as a class.

It's for a little challenge between me and a friend, where we build small games of little soldiers who kill each other in four teams and yadda yadda.

I code in haskell with openGL and he uses game maker.


So my instinct for rebalancing is to deal with each node as it changes - remove it from the tree and go upwards, merging up any empty cells as you go, then re-insert it in the new position.

That paper's a bit too mathematical for me to take in quickly, so this might be fatally flawed in some way.

Props for using haskell, though :D
The same as the old Meteorswarm, now with fewer posts!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Rebalancing a Quad Tree

Postby Yakk » Thu Jan 20, 2011 3:57 pm UTC

In my experience, naive "active" rebalancing requires log(n)^2 time or worse.

For fast rebalancing, you want to be able to maintain a "loose" invariant that requires "rare" large-scale rebalances. Hence things like Red-Black trees. The goal isn't a perfectly balanced tree, but rather one that is not too far out of balance, sort of. So long as you are close to being balanced, things stay fast. The hard part becomes making sure that taking a tree that has fallen out of balance, and bringing it back into closer to being balanced, and being able to this fast without having to rebuild everything (ie, you want to do it mostly locally, and rarely have to go far away)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Rebalancing a Quad Tree

Postby WarDaft » Fri Jan 21, 2011 9:51 pm UTC

kmatzen wrote:I don't know anything about Haskell, so I went on the website and read through the "Why Haskell matters" article. The section on Haskell vs. OOP was interesting to me. The way they describe how Haskell works sounds exactly how we were taught to do object-based programming in C when I took an OOP class. In that class we first learned how to use C for things like encapsulation, inheritance, polymorphism, etc, but it required extremely error prone code. I just find it odd that the article doesn't mention this, even as a quick history recap. It should be like, you know those methods you used in C? Well. We gave those tricks new names and made them type safe. Even this idea of type classes fits in which how the C++ STL was designed. There isn't really any inheritance going on in there. They just did some operator overloading so that iterators and arrays all work the same, containers work the same, etc. and just let the compiler enforce the existence of certain class functions so that the STL algorithms can go in an do their jobs. The class hierarchy would be a horrible mess otherwise. I guess in this case, they just don't use a compiler to enforce the requirement. It also strikes me odd that they don't just make an analogy to Java's interfaces at this point in the article.

They didn't say those things because that's not what Haskell is. That's just a pitch to people who like OOP as to why Haskell is good. Many of the Haskell Library functions will work on brand new types with little to no work on your end. However, Haskell is extremely type strict. More type strict than you think, unless you've actually used it. For example (3::Int) + (4::Integer) produces a type error. Because of this high level of type strictness, even the functions "arr :: Int -> Int -> Int" and "arr :: Integer -> Integer -> Integer" are not the same, and you can only have one. You can however, have an "arrInt :: Int -> Int -> Int" and another "arrInteger :: Integer -> Integer -> Integer" and use them for your Pirate class, by creating instances of the Pirate class function pirate for Ints and Integers using your arr functions. You could then do both 'pirate (3::Int) (4::Int)' and 'pirate (3::Integer) (4::Integer)' without writing a pattern matching pirate function. This would later allow you (or others) to incorporate more types that this pirate function could be defined over by writing the functions for those types and instantiating them for the Pirate class, rather than making one big messy pirate function. There are other benefits, and some really aren't obvious until you're really working deeper with the language - I'm not really qualified to explain those anyway.
Last edited by WarDaft on Fri Jan 21, 2011 11:02 pm UTC, edited 1 time in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Rebalancing a Quad Tree

Postby kmatzen » Fri Jan 21, 2011 10:32 pm UTC

Okay, sorry for misunderstanding. I just thought they were arguing for a non-hierarchical class system in the same way the STL did it.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Rebalancing a Quad Tree

Postby Yakk » Sat Jan 22, 2011 2:56 pm UTC

To continue the tangent, the STL-style type system is known as "ducktyping". (As in, "walks like a duck, quacks like a duck...")
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests