RTree in haXe

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

RTree in haXe

tommedema
Hi there,

It took me a couple of days but I've finished my RTree in haXe. You can download my source below, I'd appreciate all improvements/comments/etc.

I'm pretty happy with the results on my Q9550 with Neko. Adding 10.000 randomly positioned and sized objects to a tree with infinite boundaries and a working node of -1e6x-1e6 and 1e6x1e6 took only 100ms.

Searching for 1 position in this node takes 0 milliseconds according to my timestamp (run the test yourself with the source below). Searching for a 5000x5000 range also returned instantly with a couple of results. Searching for a very huge area, eg. -50000x-50000 to 50000x50000 returned about 30 results of the 10.000 objects and took only a couple of milliseconds.

Note that the tree structure is based on a Rtree, but not identical.. maybe I should rename it. Anyway, you can set the amount of childs you want a node you have maximum to any value aslong as it's square root is an integer without decimals... see the source for an example.


Regards,
Tom

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

basvanmeurs
Nice programming! I've implemented BTree before in another language; it's a good programming exercise but in practice it's usually better to use a database if possible. How does this performance compare to the default 'Hash' performance in Haxe?
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

tommedema
Hey,

I didn't want to use a database because of simplicity. I'm already using a database for things that need to be stored on the hard disk rather than memory, too.

What do you mean with the Hash method?

Anyway, see this performance example (keep in mind that the last search covers an insanely big area with lots of objects):

Main.hx:8: Test launched.
Main.hx:15: Going to create 10000 randomly positioned objects.
Main.hx:30: Done, took 118.0000305 milliseconds.
Main.hx:33: Going to search for objects at 10x10 now with 200x200 overlap.
Main.hx:37: No results.
Main.hx:42: Done, took 0 milliseconds.
Main.hx:45: Going to search for objects within -5000x-5000 and 5000x5000 now with 200x200 overlap.
Main.hx:49: No results.
Main.hx:54: Done, took 0.9994506836 milliseconds.
Main.hx:57: Going to search for objects within -50000x-50000 and 50000x50000 now with 200x200 overlap.
Main.hx:64: Match: 26 result(s) found.
Main.hx:66: Done, took 0 milliseconds.
Main.hx:69: Going to search for objects within -1500000x-1500000 and 1500000x1500000 now with 200x200 overlap.
Main.hx:76: Match: 10000 result(s) found.
Main.hx:78: Done, took 12.0010376 milliseconds.

Regards,
Tom

2010/5/29 basvanmeurs <[hidden email]>

Nice programming! I've implemented BTree before in another language; it's a
good programming exercise but in practice it's usually better to use a
database if possible. How does this performance compare to the default
'Hash' performance in Haxe?
--
View this message in context: http://haxe.1354130.n2.nabble.com/RTree-in-haXe-tp5116360p5116489.html
Sent from the Haxe mailing list archive at Nabble.com.

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

tommedema
I forgot to mention: Neko seems to be very strange when it comes to milliseconds timing. This is why the earlier timestamps are not very accurate unfortunately.. I do not know of an accurate method in haXe.

Regards,
Tom

2010/5/29 Tom <[hidden email]>
Hey,

I didn't want to use a database because of simplicity. I'm already using a database for things that need to be stored on the hard disk rather than memory, too.

What do you mean with the Hash method?

Anyway, see this performance example (keep in mind that the last search covers an insanely big area with lots of objects):

Main.hx:8: Test launched.
Main.hx:15: Going to create 10000 randomly positioned objects.
Main.hx:30: Done, took 118.0000305 milliseconds.
Main.hx:33: Going to search for objects at 10x10 now with 200x200 overlap.
Main.hx:37: No results.
Main.hx:42: Done, took 0 milliseconds.
Main.hx:45: Going to search for objects within -5000x-5000 and 5000x5000 now with 200x200 overlap.
Main.hx:49: No results.
Main.hx:54: Done, took 0.9994506836 milliseconds.
Main.hx:57: Going to search for objects within -50000x-50000 and 50000x50000 now with 200x200 overlap.
Main.hx:64: Match: 26 result(s) found.
Main.hx:66: Done, took 0 milliseconds.
Main.hx:69: Going to search for objects within -1500000x-1500000 and 1500000x1500000 now with 200x200 overlap.
Main.hx:76: Match: 10000 result(s) found.
Main.hx:78: Done, took 12.0010376 milliseconds.

Regards,
Tom

2010/5/29 basvanmeurs <[hidden email]>


Nice programming! I've implemented BTree before in another language; it's a
good programming exercise but in practice it's usually better to use a
database if possible. How does this performance compare to the default
'Hash' performance in Haxe?
--
View this message in context: http://haxe.1354130.n2.nabble.com/RTree-in-haXe-tp5116360p5116489.html
Sent from the Haxe mailing list archive at Nabble.com.

--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

MarcWeber
In reply to this post by tommedema
Excerpts from Tom's message of Sat May 29 17:20:27 +0200 2010:
> Hey,
>
> I didn't want to use a database because of simplicity. I'm already using a
> database for things that need to be stored on the hard disk rather than
> memory, too.
>
> What do you mean with the Hash method?

HaXe has a native Hash object

vor h = new Hash();
h.add("key",value);
something like this.

I think the implementation depends on the target.

Marc Weber

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

tommedema
How could a hash table replace a tree? Eg. how would you get all objects in a given range?

Regards,
Tom

2010/5/29 Marc Weber <[hidden email]>
Excerpts from Tom's message of Sat May 29 17:20:27 +0200 2010:
> Hey,
>
> I didn't want to use a database because of simplicity. I'm already using a
> database for things that need to be stored on the hard disk rather than
> memory, too.
>
> What do you mean with the Hash method?

HaXe has a native Hash object

vor h = new Hash();
h.add("key",value);
something like this.

I think the implementation depends on the target.

Marc Weber

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

MarcWeber
Excerpts from Tom's message of Sat May 29 18:12:12 +0200 2010:
> How could a hash table replace a tree? Eg. how would you get all objects in
> a given range?

Of course it doesn't. Accessing elements by key is the only thing you
can benchmark and compare then.

Marc Weber

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

tommedema
Yes, so I don't see why a hash table is relevent to this discussion.

Anyway, if anyone would like to scan through my code for improvements, I'd appreciate that.

Regards,
Tom

2010/5/29 Marc Weber <[hidden email]>
Excerpts from Tom's message of Sat May 29 18:12:12 +0200 2010:
> How could a hash table replace a tree? Eg. how would you get all objects in
> a given range?

Of course it doesn't. Accessing elements by key is the only thing you
can benchmark and compare then.

Marc Weber

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: RTree in haXe

James W. Hofmann
I alluded to this before. Here is an (untested) example of hash-based infinite grids with AABB queries.

http://haxe.org/doc/snip/infinitegrid?lang=en

tommedema wrote
Yes, so I don't see why a hash table is relevent to this discussion.

Anyway, if anyone would like to scan through my code for improvements, I'd
appreciate that.

Regards,
Tom

2010/5/29 Marc Weber <marco-oweber@gmx.de>

> Excerpts from Tom's message of Sat May 29 18:12:12 +0200 2010:
> > How could a hash table replace a tree? Eg. how would you get all objects
> in
> > a given range?
>
> Of course it doesn't. Accessing elements by key is the only thing you
> can benchmark and compare then.
>