<p>I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?"</p>

<p>The answer is that the data structures you have outlined are not sufficient by themselves to do the job; you need a bit more information. </p>

<p>The primitive events the OS produces tell you the positions of the mouse, and the scene graph gives you a logical decomposition of the structure of the GUI. Therefore, you need some additional data structures to translate between the widget tree and what it looks like geometrically. </p>

<p>The simplest case is when every widget is an axis-aligned rectangle. What you do then is:</p>

<ol>
<li>Every widget node stores its position and shape. </li>
<li>In addition to the widget tree, you keep  a separate doubly-linked list storing all of the clickable widgets in their z-order, so that the widget which is visually "on top" is at the head of the list. </li>
<li>You also keep track of the current mouse position (you have to do this anyway, because the OS only gives you relative position changes). </li>
</ol>

<p>When an event occurs, what you do is:</p>

<ol>
<li>When an event occurs you iterate through the z-order list, doing a simple hit test for the bounding box of each widget. </li>
<li>The first time the hit test succeeds, you know where the event occurred, and can do event dispatch. </li>
</ol>

<p>With fancier graphics geometry (say with vector graphics), each widget will store a data structure representing the shape, and your hit test gets more complicated to match. The things to Google for: </p>

<ul>
<li>"collision detection" or "hit detection". </li>
<li>"spatial indices" -- often these data structures <em>are</em> variants of quadtrees and the like. It really does work pretty well, even though the geometric data can be quite large, because user events are generally relatively infrequent. </li>
</ul>

CC BY-SA 3.0
2014-01-07T11:37:26.733Z
2014-01-07T11:37:26.733Z
Neel Krishnaswami
<p>A graphical user interface that contains more than a few tens of components would be very confusing for the user. This means that, whatever data structure is used, it doesn't have to scale to large instances. The user is unlikely to generate more than a couple of mouse-clicks per second, so whatever data structure is used, it doesn't even have to be processed very fast.</p>

<p>So it sounds like this is a problem that has already been solved as well as it needs to be solved and, in fact, that almost anything you could try would work on a modern computer.</p>

CC BY-SA 3.0
2013-12-30T10:52:35.223Z
I don't get your logic, an UI is usually way more complicated than what you are proposing, even a simple drop-down menu got at least 20-30 single elements that need to be responsive, there are also the widgets that are used in the main part of the UI. In a real world example even a simple UI is composed of something in the order of dozens and thousands elements. What exactly is your approach ? With what algorithms or data structures are you approaching this ?
user2485710
CC BY-SA 3.0
2013-12-30T10:39:17.303Z
2013-12-30T10:39:17.303Z
David Richerby
<p>I'm studying how, given:</p>

<ul>
<li>an input from the user ( like a click of the mouse or the input from a key )</li>
<li>a well defined data structure that represent the graphical layout inside a window ( a tree/graph like structure for now )</li>
</ul>

<p>I could possibly create what is generally called as a "G/UI toolkit", which means that I should be able to create a responsive UI and a mapping between the input from the user and the functionality given to the UI itself.</p>

<p>I found absolutely no paper, no technical explanation, no articles, about both the data structure and the algorithms used to perform this kind of mapping, and I'm wondering if someone could help me with this.</p>

<p>I found some sparse reference to some tree-like data structure like kd-tree or quadtree that are used to subdivide the 2D space in the window and so when the signal will be fired, the coordinates generated by the signal, the click of a mouse, will be injected in the tree to find the corresponding widget to activate.
This approach feels really old and I don't think it will scale that well.</p>

<p>I also found some reference to what is called the <a href="http://arstechnica.com/apple/2000/01/macos-x-gui/3/" rel="nofollow">third generation</a> of rasterizers and UIs which seems to be based on linear algebra/vectors and sounds really nice because it's highly scalable and simple to reason about, the problem is I can't see any implementation or algorithms or data structures.</p>

<p>Someone can point me in the right direction ?</p>

CC BY-SA 3.0
2013-12-30T11:29:23.567Z
This question is not on Theoretical computer science.
Arindam Pal
CC BY-SA 3.0
2013-12-31T10:15:58.367Z
Yes, it is! I am a theoretical computer scientist, and a good chunk of my research has been on the mathematical semantics of GUIs.
Neel Krishnaswami
CC BY-SA 3.0
2013-12-31T12:55:56.583Z
@ArindamPal why exactly ?
user2485710
CC BY-SA 3.0
2014-01-01T07:10:31.960Z
@NeelKrishnaswami could you suggest a starting point or an initial answer to my question ? A book ? Something ?
user2485710
CC BY-SA 3.0
2014-01-01T10:46:50.373Z
Sure, but only next week, I'm afraid.
Neel Krishnaswami
<graph-algorithms><data-streams>
What are the algorithms and the data structures for GUIs and input management?
user2485710
# What are the algorithms and the data structures for GUIs and input management?

(Asked by: username_0 on 2013-12-30)

I'm studying how, given:

* an input from the user ( like a click of the mouse or the input from a key )
* a well defined data structure that represent the graphical layout inside a window ( a tree/graph like structure for now )

I could possibly create what is generally called as a "G/UI toolkit", which means that I should be able to create a responsive UI and a mapping between the input from the user and the functionality given to the UI itself.

I found absolutely no paper, no technical explanation, no articles, about both the data structure and the algorithms used to perform this kind of mapping, and I'm wondering if someone could help me with this.

I found some sparse reference to some tree-like data structure like kd-tree or quadtree that are used to subdivide the 2D space in the window and so when the signal will be fired, the coordinates generated by the signal, the click of a mouse, will be injected in the tree to find the corresponding widget to activate.
This approach feels really old and I don't think it will scale that well.

I also found some reference to what is called the [third generation](http://arstechnica.com/apple/2000/01/macos-x-gui/3/) of rasterizers and UIs which seems to be based on linear algebra/vectors and sounds really nice because it's highly scalable and simple to reason about, the problem is I can't see any implementation or algorithms or data structures.

Someone can point me in the right direction ?

**Tags:** graph-algorithms, data-streams
> **Comments:**
> **username_1**: This question is not on Theoretical computer science.  
> **username_2**: Yes, it is! I am a theoretical computer scientist, and a good chunk of my research has been on the mathematical semantics of GUIs.  
> **username_0**: @ArindamPal why exactly ?  
> **username_0**: @NeelKrishnaswami could you suggest a starting point or an initial answer to my question ? A book ? Something ?  
> **username_2**: Sure, but only next week, I'm afraid.  

---

## 2 answers

### Answer by username_2 on 2014-01-07. Score: 3 | Accepted answer

I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?"

The answer is that the data structures you have outlined are not sufficient by themselves to do the job; you need a bit more information.

The primitive events the OS produces tell you the positions of the mouse, and the scene graph gives you a logical decomposition of the structure of the GUI. Therefore, you need some additional data structures to translate between the widget tree and what it looks like geometrically.

The simplest case is when every widget is an axis-aligned rectangle. What you do then is:

1. Every widget node stores its position and shape.
2. In addition to the widget tree, you keep a separate doubly-linked list storing all of the clickable widgets in their z-order, so that the widget which is visually "on top" is at the head of the list.
3. You also keep track of the current mouse position (you have to do this anyway, because the OS only gives you relative position changes).

When an event occurs, what you do is:

1. When an event occurs you iterate through the z-order list, doing a simple hit test for the bounding box of each widget.
2. The first time the hit test succeeds, you know where the event occurred, and can do event dispatch.

With fancier graphics geometry (say with vector graphics), each widget will store a data structure representing the shape, and your hit test gets more complicated to match. The things to Google for:

* "collision detection" or "hit detection".
* "spatial indices" -- often these data structures *are* variants of quadtrees and the like. It really does work pretty well, even though the geometric data can be quite large, because user events are generally relatively infrequent.


---

### Answer by username_3 on 2013-12-30. Score: 2

A graphical user interface that contains more than a few tens of components would be very confusing for the user. This means that, whatever data structure is used, it doesn't have to scale to large instances. The user is unlikely to generate more than a couple of mouse-clicks per second, so whatever data structure is used, it doesn't even have to be processed very fast.

So it sounds like this is a problem that has already been solved as well as it needs to be solved and, in fact, that almost anything you could try would work on a modern computer.

> **Comments:**
> **username_0**: I don't get your logic, an UI is usually way more complicated than what you are proposing, even a simple drop-down menu got at least 20-30 single elements that need to be responsive, there are also the widgets that are used in the main part of the UI. In a real world example even a simple UI is composed of something in the order of dozens and thousands elements. What exactly is your approach ? With what algorithms or data structures are you approaching this ?  

---

