Elements below the point (under cursor)

[whytwelve13]

Is there a way to find all elements that are "under" some point on the
screen in JavaScript? That is, given (x, y) find all elements of size
(w1, h1) whose absolute position compared to the document.body starting
point is (x1, y1), with constraints x1 <= x <= x1 + w1 and y1 <= y <=
y1 + w1. Assume absolute positioning of all elements (if in need, I
will try to generalize to other positioning types, but not now). Just
to note, I am searching for solution that works in at least Firefox and
IE.

A way is surely to loop through all elements and see if they satisfy
the above conditions. However, for large number of elements (1000s),
this is damn slow if you need to do quick actions lots of times. Is
there a way to do this more efficiently?

Basically, what I need is the following, the above is just a try to
solve the below. Assume you have three divs: div1, div2 and div3. div1
is a parent of div2 and div3. div2 and div3 partially overlap. Assume
z-indexes are 1, 2 and 3 for div1, div2 and div3, respectively. In this
case, div3 is on top of div2 where they overlap. When you e.g. click on
div3, it will propagate the click upwards through the hierarchy, so
div3, div1 and document.body will get the click event. However, I would
like the planar behavior of this - when I click on div3, I would like
all the divs below (in this case, div2) to get the click event.

A way to solve it is as I suggested above - loop through all elements
and see if they satisfy the conditions. In this (click) case, it
wouldn't be too slow, as these events are not so frequent, but for
events like mousemove, looping through all elements is a very time
consuming operation. Any other ways?

I was also thinking about making some 2D-sorted array of elements, so I
can use e.g. binary search to find elements quickly. I am, however, not
sure that this would be a good idea, since I would need a list of 1000s
of elements - huge structure for JavaScript. It would be necessary to
take care of all the changes in the structure of the elements (adding,
deleting, moving, resizing), so at the end, it might not be worth it.

 

[whytwelve13]

Thanks for the reply!

I probably wasn't clear enough, let me try to explain this better. I
will give you an example of the type of the problem I need to solve.
You know of Mahjong solitaire type of games? An online working example
can be found here:

http://www.by-art.com/mjong/mjong.php

Basically, you have blocks that you need to pair with other blocks and
they disappear. The blocks are stacked, so there are several layers of
them. This is the key.

Assume I would want something like the following. When you click on
some block, I would like to show all the blocks that are beneath it
(and thus at least partially hidden) in some separate part of the page.
So, looking from the top, there is a block on the top that is
completely visible, beneath it some other, beneath it some other and so
on. Blocks can overlap partially or one can completely hide the other,
as in the game.

One way is as I proposed - loop through all blocks (which is less then
all the elements on the page, but assume still 1000s of blocks can
exist) and find all that satisfy the criteria that the point of the
click is within their region.

I cannot just assign click handler, since the event propagation doesn't
go by z-index - it goes by hierarchy. The container that holds all the
blocks would get the propagated click event if you clicked on the
block, but not the blocks on the same position on the screen, as I
mentioned in my previous post's example. Basically, if you have clicked
on div3 on the position of the screen where div2 is beneath div3, div2
wouldn't get any event notification, but div1 would, since it's a
parent of div3. Siblings do not get events, parents do.

All the blocks are already part of one container and they can (and
probably will) be its direct children, but there are 1000s of them
anyway. Looping through them to find which contain the point is not a
quick task.

I gave the above example just to explain the need to find elements
under the mouse (or, generally at some point). It might be necessary to
have this search repeated while moving the mouse, not just when
clicking. So, whenever you move a mouse over one of the blocks, the
blocks beneath it need to be displayed. Surely, this is much more work
to be done compared to work being done only when clicking. This is
where a quick

var elements = getElementsFromPoint(x, y)

would come in handy.

Absolute/relative positioning is not important here in the context of
this problem, since nothing would be actually moving, but you are right
about the consequences.

Considering the previous, I couldn't understand what your solution to
this would be. If your solution still applies, can you please try to
explain it again?

 

[Jonas Raoni]

(e-mail address removed) escreveu:

A way is surely to loop through all elements and see if they satisfy
the above conditions. However, for large number of elements (1000s),
this is damn slow if you need to do quick actions lots of times. Is
there a way to do this more efficiently?

This is the "loop" way: <URL:http://jsfromhell.com/geral/hittest> :]

Hmmm, it depends of how often you're going to do such thing, if it's
really very rare, looping through the elements may be a good choice.
Otherwise I'm all for storing the origin point of every box in an
ordered array, maybe you can sort the end points too, then after
matching the "valid" origin points agains the valid end points will give
you the correct elements, ah, there are a lot of ways =]

You also can keep a tree structure with coordinates of the "filled"
regions, where the inner nodes of this tree just narrows the bigger
regions, but it might be expensive to initialize and update if you move
the boxes, if you don't move it can be quite fast to retrieve the nodes,
I'm just thinking, so maybe I'm wrong too...

 

[Jonas Raoni]

David Golightly escreveu:

The absolute crazy wrong way to do this is like you're saying, to
iterate through all the HTML nodes using getElementsByTagName or some
such nonsense.

Please, where did I talk about getElementsByTagName?.

Using getElementsByTagName would be needed only if he isn't creating the
boxes through JavaScript and if they aren't absolute positioned (if they
are, he can still output the JavaScript content and assign the nodes).

You want to create an object in JavaScript that will
encapsulate this, and create whatever data structure makes sense to
keep track of locations.

I just talked about possible structures, well, it's what the guy is
asking for...

The first one was looping through all the boxes...

The second is something like this:

Boxes = [
{x: 1, y: 2, w: 3, h: 4, o: box1},
{x: 5, y: 6, w: 7, h: 8, o: box2},
:
];

Index = {
startX = [3, 2, 1, ...], //boxes ordered by the x coodinate
startY = [0, 1, 2, ...],
endX = [0, 1, 2, ...],
endY = [0, 1, 2, ...]
};


By doing a search on these arrays, you will have all the possible
elements that may fall in the desired area, then by doing an
intersection of the results you'll have the right ones.

The third is just in my mind, something like this:

Region 0 [x, y, width, height]
Contained boxes: b1, b2, b3, b4
Sub-Region 0 [x + a, y + b, width - c, height - d]
Contained boxes: b1, b2
Sub-Region 1
:
:
:

There are a lot of other ways of achieving this, all of them have
advantages and disadvantages, I won't try to find the best one, it's
1:00 am here, got to sleep lol xD

 

[whytwelve13]

Guys, thank you for your answers. After all, seems that I will try to
use the newly-baptized "loop" method. I have done some testing of this
method, it is not very fast with 1000 elements, especially in IE. In
IE, I assume it is not slow due to JS, but due to the screen refresh -
you can "see" it doing the redraw. Not sure if this really is the
problem, but it works like 5 times slower then in FF. With little
number of elements (~100), it works acceptable in both (but still a lot
faster in FF). After all, it seems that doing a lot of sorting and
inserting and whatever the other possibilities might require will
probably make it slow either...

Good sites, both of you! Keep up the good work!

 

[Jonas Raoni]

David Golightly escreveu:

Sorry Jonas, I should have given you credit. You have the right idea,
and in fact it's the same general idea I'm talking about, and I wasn't
clear about saying that.

Ah, it's ok... Besides that, probably a lot of people had the same idea,
since it seems to be the easiest one :]

It was the OP's original idea of iterating
through the DOM for his app logic that I was referring to as crazy.

Well, that's the path he followed :]

 

[VK]

Guys, thank you for your answers. After all, seems that I will try to
use the newly-baptized "loop" method. I have done some testing of this
method, it is not very fast with 1000 elements, especially in IE.

For sake of fare I have to say that IE doesn't need anything like
this: only competing UA's will need a workaround. IE has an absolutely
cool method document.elementFromPoint. This method returns the topmost
element currently displayed on the screen (irrelevant to DOM three
relations). So in order to get all elements you have to hide them one
by one. Lucky there is another universal browser feature: the graphics
context doesn't get updated until the exit of the current execution
context. Thus if you hide some elements and show them again withing the
same function w/o any execution flaw breaks (like alerts etc) the user
will see nothing. In summary it will be (feel free to further adjust):

<script type="text/javascript">
function getElms(x,y) {
var a = new Array;
var obj = null;
if ('elementFromPoint' in document) {
do {
obj = document.elementFromPoint(x,y);
if (obj == document.body) {break;}
a.push(obj);
obj.style.display = 'none';
} while(true);
for (var i=0; i<a.length; ++i){
a.style.display = '';
}
return a;
}
}

function init() {
alert(getElms(100,100));
}
window.onload = init;
</script>

 

[VK]

IE has an absolutely
cool method document.elementFromPoint. This method returns the topmost
element currently displayed on the screen (irrelevant to DOM three
relations). So in order to get all elements you have to hide them one
by one. Lucky there is another universal browser feature: the graphics
context doesn't get updated until the exit of the current execution
context. Thus if you hide some elements and show them again withing the
same function w/o any execution flaw breaks (like alerts etc) the user
will see nothing. In summary it will be (feel free to further adjust):

<script type="text/javascript">
function getElms(x,y) {
var a = new Array;
var obj = null;
if ('elementFromPoint' in document) {
do {
obj = document.elementFromPoint(x,y);
if (obj == document.body) {break;}
a.push(obj);
obj.style.display = 'none';
} while(true);
for (var i=0; i<a.length; ++i){
a.style.display = '';
}
return a;
}
}

function init() {
alert(getElms(100,100));
}
window.onload = init;
</script>

For Gecko you may look at
<http://www.webxpertz.net/forums/archive/index.php/t-24624.html> *but*
I didn't use this solution so I cannot comment on it.

 

[whytwelve13]

For sake of fare I have to say that IE doesn't need anything like
this: only competing UA's will need a workaround. IE has an absolutely
cool method document.elementFromPoint.
<
Yes, I knew of this function, but I still have to agree with you only
partially.

First, judging at the path at the top of:

http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/elementfrompoint.asp

this is HTML-only solution (not sure, but I suppose Google would find
something on microsoft.com if you searched for
"document.elementFromPoint svg"). So, IE needs this for e.g. SVG. In my
example, I used divs, so I haven't been precise enough with this.

Second, you would have to do the logic completely different for
different browsers, at least considering your solution with hiding and
showing elements. I personally don't like such solutions. On the other
hand, it may not make sense not to use some feature just because you
have other browsers that don't have it.

Third, the problem with IE is not in finding speed (i.e. looping
through elements), but in drawing itself. Finding is very fast, most of
the time faster then in FF (comparing the looping method in both).
However, with e.g. 6000 elements, moving the element is very slow. It
goes so far that screen update can take literally two seconds in some
instances. This doesn't have to do anything with the function itself,
as is obvious, however points out one really important thing - having a
quick function and not being able to use it because of other quirks is
in practice the same as not having it at all. In FF, this doesn't go as
bad, although the looping itself takes almost 200 ms sometimes, so it's
much better when combined.

I agree it's a cool method, but I have to say I hate when the
competition goes so astray. We have 100s of "standards" and you have to
have a headache every time you try to do some in a cross-browser
manner.
For Gecko you may look at
<http://www.webxpertz.net/forums/archive/index.php/t-24624.html> *but*
I didn't use this solution so I cannot comment on it.
<
I will look at this, thank you!

 

[Jonas Raoni]

(e-mail address removed) escreveu:

Third, the problem with IE is not in finding speed (i.e. looping
through elements), but in drawing itself. Finding is very fast, most of
the time faster then in FF (comparing the looping method in both).
However, with e.g. 6000 elements, moving the element is very slow. It
goes so far that screen update can take literally two seconds in some
instances.

Hmmm, both IE and Firefox have the DocumentFragment object. You can move
them from the document to the DocumentFragment while you discard them,
and after finishing, add the DocumentFragment back to the document, or
just change the display attribute to none. Maybe it will improve the
speed, but I dont know if you need to show the things moving. ^^

For Gecko you may look at
<http://www.webxpertz.net/forums/archive/index.php/t-24624.html> *but*
I didn't use this solution so I cannot comment on it.
<
I will look at this, thank you!

I took a look and it seems that the buy initiates a mouse event on a
given position and gets the target.