-3

I read through documentation and searched on google, but couldn't find a specific answer. Currently, I have an object that subscribes to a click event. I am trying to understand how a view that receives a mouse event with an (x,y), determines if it's within that object with the mouse event. To be specific, a view receives an event with an x and y, what are the steps that are taken to return the object, if it has a mouse event.

Does it search through every object and see if that click is inside it and if it has a listener? Does it go through a list of UI element layers starting from the top and check if the x,y is inside it? Like is there a method that takes in an x,y and returns the element?

I found this. Is this what I'm looking for? https://dom.spec.whatwg.org/#dispatching-events

2

Your Query is fairly vague, so I cannot tell if you are asking:

  • how a Browser (or any program) selects the correct control and its bound event handlers to invoke on receiving a mouse event?
  • how can an event handler retrieve a reference to the control object that generated the event?

OS event to Browser Control

I cannot say how any particular program translates a click event (x, y) received from the OS layer, locates, and invokes the correct function with the events details; but most solutions will be in the form of an R-Tree.

  • This might be implicit in that each larger region has children that it searches and then forwards to after receiving the event.
  • It might be explicit in that every region registers with the R-Tree and the search is co-ordinated by a single function that returns intersecting regions from which one region(a.k.a. control) is given the event.

The mouse movement and click may in-fact be split, with the co-ordinates being used to "Focus" a control which directly receives all subsequent events, only going the long way and searching when that control says "not me".

Obtaining a Reference to the Event's Control Object

It has been explained here.

Briefly:

  • The simplest way is to receive the this argument as a parameter.
  • The control is also passed as part of the event structure, though this is somewhat browser dependent.
  • Alternately JavaScript libraries like JQuery provide cross-browser means to access the JavaScript object.

Edit: How a GUI works

A Graphical program is just a really good at drawing pictures. At the most fundamental there are two representations for pictures: Vector and Raster.

A Vector image is made by drawing lines, triangles, circles, rectangles, etc... in a co-ordinate space. It similar to the way you use a pen to write your name: move pen here, apply pen to paper, follow this line, raise pen, move here, etc... For 2-D pictures that's it, for 3-D pictures a second step is done. This takes a point (or region) of view, and produces a 2-d picture by projecting what can be seen onto a 2-d surface. The Controls on a web-page will (for the most part) draw themselves using descriptions with vectors.

A Raster image is made by colouring dots arranged in a co-ordinate space. If that space is 3-d, the dots are called voxels. Blocks in games like MineCraft are essentially a "coloured dot" in a 3-D raster image. Like with 3-d pictures a second step is needed to reduce these down to 2-D images for the monitor. 2-D raster images are fairly universal, jpeg and png are two formats, the dots they store are called pixels. Most pictures are stored and presented this way including on computer (and tv) screens.

Each program has one or more windows registered with the OS: some may be minimised, or invisible, some may be fullscreen, and others various sizes in-between. The OS will maintain a spatial data structure like an R-Tree that lets it quickly identify which windows occupy which areas of the screen, and then it asks each program to draw the relevant portion of their window to that location of the screen.

Moving the Mouse

The OS is also tracking where the mouse is located in (x, y) pixels from a corner of a screen. When the mouse is moved the OS consults its spatial data structure to see if the mouse has moved in/out/within which windows. It will give the (x, y) pixel offset relative to a corner of the window to the program along with what happened.

Now the program has an (x, y) relative to the window and needs to identify what that click means to it. This could happen in a number of ways.

A Naive Solution

One method is to redraw the picture again but this time instead of letting the controls determine the colour, each control is assigned a colour and perhaps asked to draw their "hit" box. Now all the program needs to do is lookup the colour of the pixel at (x, y), and then find the specific control associated with that colour. Needless to say this can be pretty wasteful, to interpret one mouse event (and mice are moved a lot) an entire picture must be drawn and every other pixel in that picture is essentially wasted effort.

An Improved Solution

Instead lets flip the problem on its head, we want to know which controls occupy a given pixel. Lets imagine that every control is a rectangle. A rectangle has four sides that conveniently are vertical, or horizontal. Therefor each side can be describe by a single x or y offset from a corner of the window. So that is two x co-ordinates (left and right), and two y co-ordinates (top and bottom): (x1, x2, y1, y2).

Now with this (x1, x2, y1, y2) description of a rectangle, we can easily tell if a pixel (x, y) is not in it using: x < x1 or x2 < x or y < y1 or y2 < y. If we had a list of all these rectangles we could find all the controls that contain that rectangle in O(N) time. If there are fewer rectangles than pixels this is a speed up over the previous solution.

O(N) is still slow with many mouse events and many Controls that comes to O(KN) which is roughly O(N^2) for large N and K. If the rectangles changed very often this is probably the best that can be done, because the cost of maintaining the data structure may outweigh its benefits. This though is a very exceptional circumstance, much better can be done.

A Sorted Solution

When searching, sorting something tends to make it faster to find, because we can employ divide and conquer strategies.

  • Notice that a pixel is not in a rectangle if any of these are true: x < x1or x2 < x or y < y1 or y2 < y.

  • Also notice that if a pixel at x is true for x < x1 and there is another rectangle (x3, x4, y3, y4) and x1 < x3 then we already know that x < x3 because x < x1 < x3.

So if we sorted the list of rectangles by x1 we can use a binary search to find the first rectangle that does not satisfy x < x1. Unfortunately we will still need to check each rectangle from this point on in the list.

A Doubly Sorted Solution

The problem with the sorting of the list is that we can control only for one of the conditions: x < x1or x2 < x or y < y1 or y2 < y. Whichever condition we pick allows us to eliminate all the rectangles that satisfy it quickly, but then we have to linear search through all the other rectangles.

Why?


   x1             x2
 A |--------------|          
 B |-------------------------|
   x1     C |-------|        x2
           x1       x2

How should these 3 rectangles be sorted?

  • A, B, C
  • B, A, C
  • B, C, A

Sorting by x1 makes x2 unusable for divide and conquer. Sorting by x2 makes x1 unsuitable for divide and conquer.

On the other hand it would work fine only if we could force both x1 and x2 to be sorted in the same list. This way we can find the first rectangle to check by a binary search on x < x1 and find the last rectangle to check by a binary search on x2 < x


   x1             x2
 D |--------------|          
 E |-------------------------|
   x1                        x2
                         F |-------|
                          x1       x2

We can sort this as: D, E, F and it would work allowing us to cut off the top and bottom of the list. But now we have to deal with those rectangles that don't play nice.

A Rectangle along an x or y axis is described by just two points (x1, x2) or (y1, y2) these are its axis boundaries. Any two rectangles can occupy an axis boundary described by (min(x1, x1), max(x2, x2)) (similarly (min(y1, y1), max(y2, y2))). Following the first example A and C could be merged to form an axis boundary (A.x1, C.x2) that behaves with B for the double sort.

Now instead of having a sorted list of rectangles, we have a doubly sorted list of axis boundaries, each has an unordered child list of rectangles. The axis Boundary list can be quickly searched to discard rectangles that won't match. A Few boundaries might contain the pixel and only the rectangle lists associated with those candidate boundaries need to be checked.

Elegance in a Tree

We can still do better. Before we could only binary search on one axis, but rectangles are 2D not 1D. We have already struck on the technique in the previous solution - create children with different search rules.

The Trick is to have three kinds of children.

  1. Children that are just unordered (or single sorted) (rectangle, control) lists.
  2. Children that are doubly sorted (x axis boundary, child) list.
  3. Children that are doubly sorted (y axis boundary, child) list.

This is the essence of most spatial trees, including the R-Tree I mentioned above. Some Trees will organise their divide and conquer around another sorting technique like: a single sorted axis list, or a pivot point.

The problem now is deciding how to group the rectangles, and which axis to use. These are not trivial problems. When done right locating the controls that were clicked on becomes log(N), or log(N)K over the K mouse events. When done wrong the tree becomes slower than an unordered list search. This is because an unbalanced tree is just a linked list, and a tree with highly overlapping nodes is performing a linear search.

Some good heuristics:

  • only allow overlapping rectangles/axis boundaries to be merged. If they don't overlap merging them only makes the search more linear (ie. slower).
  • a child should use a different axis to the parent. If they used the same axis then that same information could have been placed in the parent. The only exception is when the parent has a maximum capacity for children.
  • if a parent and its children share the same sorted axis they need to occasionally be rebalanced. There are many ways to do this B-Tree, Red/Black trees, etc...

For learning it can be instructive to write your own, in production though its usually best to rely on a third-party battle hardened spatial-collection library. There are many many gotchas hidden quietly in the details of how to manage such data-structures that will show up weirdly at run time.

  • Thanks for the quick response. I am trying to understand, step by step, how a "particular program translates a click event (x, y) received from the OS layer" to locating the object. In other words, how do I know what I clicked on? R-Trees seem pretty confusing, but what you said about how "every region registers with the R-Tree and the search is co-ordinated by a single function that returns intersecting regions from which one region" sounds about right? – Caelan Dailey Dec 27 '18 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.