R*Tree / In Memory Database / GUI Object Hit Testing

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

R*Tree / In Memory Database / GUI Object Hit Testing

Robert M. Münch
Hi, I’m wondering if the R*Tree index of Sqlite could be used to implement GUI object hit testing?

Scenario: We have a 2D scene-graph for our GUI, which does an automatic layout of objects following the CSS grid idea. So, we build up the graph, run layout and get back the coordinates where to render things.

We could populate a r*tree table with (runtime-object-memory-pointer, x0, y0, x1, y0) pretty easy. Now the user clicks the mouse somewhere, and we would like to get back all rectangles that were hit. Since we don’t have any overlapping we could even sort the rectangles by size and get the whole tree-path to the leaf rectangle back.

Since we would implement a R*Tree anyway for hit testing and use Sqlite in our app, I can imagine that using it might really be nice here. IMO if everything is running in memory, this should be very efficient. We are talking maybe about 5000 entries.

What do you think? Or maybe any experiences with such a setup?

--

Robert M. Münch, CEO
M: +41 79 65 11 49 6

Saphirion AG
smarter | better | faster

http://www.saphirion.com
http://www.nlpp.ch

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

signature.asc (537 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: R*Tree / In Memory Database / GUI Object Hit Testing

Clemens Ladisch
Robert M. Münch wrote:
> I’m wondering if the R*Tree index of Sqlite could be used to implement
> GUI object hit testing?

Yes, that would be possible.

> We could populate a r*tree table with (runtime-object-memory-pointer,
> x0, y0, x1, y0) pretty easy. Now the user clicks the mouse somewhere,
> and we would like to get back all rectangles that were hit. Since we
> don’t have any overlapping we could even sort the rectangles by size
> and get the whole tree-path to the leaf rectangle back.

In general, your object tree already is the equivalent of an R-tree,
i.e., just doing hit-testing in the objects themselves should be just
as efficient.

An (R-tree) index is more useful when you have a bunch of independent
object that are not already organized in a tree.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: R*Tree / In Memory Database / GUI Object Hit Testing

Robert M. Münch
On 20 May 2018, at 15:56, Clemens Ladisch wrote:

> Robert M. Münch wrote:
>> I’m wondering if the R*Tree index of Sqlite could be used to implement
>> GUI object hit testing?
>
> Yes, that would be possible.

Using this approach now for some time with a memory database and it works great!

> In general, your object tree already is the equivalent of an R-tree,
> i.e., just doing hit-testing in the objects themselves should be just
> as efficient.

Being able to formulate much more flexible queries on the object tree and getting back a flat result list is very valuable. Reaching the same level as the SQLite implementation would still need quite some time.

--

Robert M. Münch, CEO
M: +41 79 65 11 49 6

Saphirion AG
smarter | better | faster

http://www.saphirion.com
http://www.nlpp.ch

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

signature.asc (537 bytes) Download Attachment