Heads up: A frivolous and probably useless answer
However the question itself seems quite frivolous too. No real world use case has been provided yet and I can't think of any either. Similarly, in theory my answer could be useful, but you're more likely struck by an asteroid than finding yourself needing it.
The point of posting is more that it provides some perspective on the performance of the other proposed solution. You can see you need at least hundreds of elements before performance starts being a concern.
My "answer" only works if:
- items are rectangles
- items cannot overlap
The potential "performance problem"
Perhaps the "not a loop" requirement refers to having a solution that doesn't require you to loop through a potentially large amount of other items in JS? This could be a valid concern, if the number of items can ever get really large.
Say that the area you're testing is relatively small compared to the items, and there are thousands of items that may or may not be inside, looping all of them might be relatively costly. Especially if you need to give each an event listener.
As already pointed out, it would be nice if a native API similar to document.getElementFromPoint existed, as that would undoubtedly be more performant than implementing in JS.
However that API does not exist. Probably because nobody ever found themselves needing it in a real world use case.
Sampling points of the frame
Now you could just use the document.ElementFromPoint API on every single point of the frame. However that would scale even worse with the frame's size.
But do we need to check every point to guarantee we're detecting all elements? Not if the elements can't overlap: since the smallest element is likely still many pixels high and wide, we could create a grid of points with those minimum values. As long as the elements don't have changing dimensions (or they can only grow) we only need to loop them once (to determine the smallest), not on updates. Note I do loop them every time, to account for setting changes. If you're sure elements have fixed dimensions you only need it once at the start of your script.
Of course, you do now have to loop over points instead. However...
In the best case scenario, where the minimum element is equally wide and high (or bigger), you only need to check 4 points. In fact I used this in a function to generate random cubes, to avoid overlap with earlier cubes.
It doesn't work on overlapping elements as document.ElementFromPoint only knows about the topmost. You could work around that by temporarily setting a z-index, but I had to stop somewhere.
Does it perform better?
I'm not sure at all whether this would ever make sense to do, but I don't immediately see another way to handle large amounts of items.
In the best case of needing just 4 points (small area to check overlap), it's hard to imagine another approach being faster, if the other approach needs to go through thousands of elements in JS. Even with up to a few tens of points it'll probably still be "fast" regardless of how many elements on the page.
let allItems = [...document.querySelectorAll('.item')];
const frame = document.getElementById('frame')
function measureLoop() {
const start = performance.now();
const large = document.querySelector('#frame');
const largeRect = large.getBoundingClientRect();
const Left = largeRect.left;
const Right = largeRect.right;
const Top = largeRect.top;
const Bottom = largeRect.bottom;
const items = document.querySelectorAll('#frame ~ *');
let overlappers = [];
items.forEach(item => {
const itemRect = item.getBoundingClientRect();
const l = itemRect.left;
const r = itemRect.right;
const t = itemRect.top;
const b = itemRect.bottom;
if (((l <= Right) && (r >= Left)) && ((t <= Bottom) && (b >= Top))) {
overlappers.push(item);
}
});
document.getElementById('result-loop').innerHTML = overlappers.length;
document.getElementById('time-loop').innerHTML = performance.now() - start;
}
function randomColor() {
var letters = '0123456789ABCDEF';
var color = '#';
for (var i = 0; i < 6; i++) {
color += letters[Math.floor(Math.random() * 16)];
}
return color;
}
function within_frame(frame, items) {
const rect = frame.getBoundingClientRect();
const frameX = rect.left;
const frameY = rect.top;
const frameWidth = frame.clientWidth;
const frameHeight = frame.clientHeight;
const smallestWidth = Math.min(...(items.map(i => i.clientWidth)));
const smallestHeight = Math.min(...(items.map(i => i.clientHeight)));
const set = new Set();
let points = 0;
const lastY = frameHeight + smallestHeight;
const lastX = frameWidth + smallestWidth;
for (let y = 0; y < lastY; y += smallestHeight) {
for (let x = 0; x < lastX; x += smallestWidth) {
points++;
const checkX = Math.min(frameX + x, rect.right)
const checkY = Math.min(frameY + y, rect.bottom)
// Note there is always a result, but sometimes it's not the elements we're looking for.
// Set takes care of only storing unique, so we can loop a small amount of elements at the end and filter.
set.add(document.elementFromPoint(checkX, checkY));
}
}
set.forEach(el => (el === frame || el === document.documentElement || !items.includes(el)) && set.delete(el))
document.getElementById('points').innerHTML = points;
return set;
}
function measure() {
// Frame needs to be on top for resizing, put it below while calculating.
frame.style.zIndex = 1;
const start = performance.now();
const result = within_frame(frame, allItems)
const duration = performance.now() - start
document.getElementById('result').innerHTML = [...result.entries()].length;
document.getElementById('time').innerHTML = duration;
// Restore.
frame.style.zIndex = 3;
}
document.getElementById('measure').addEventListener('click', () => {measure(); measureLoop();})
const overlapsExisting = (el) => {
return within_frame(el, allItems);
}
let failedGenerated = 0;
function sleep(ms) {
return new Promise(resolve => setTimeout(resolve, ms));
}
async function spawnCubes() {
frame.style.zIndex = 1;
allItems.forEach(item => item.parentNode.removeChild(item));
const nPoints = document.getElementById('nCubes').value;
const cubeSize = document.getElementById('size').value;
let newItems = [];
let failedGenerated = 0;
for (let i = 0; i < nPoints && failedGenerated < 1000; i++) {
// Sleep so that stuff is drawn.
if ((i + failedGenerated) % 100 === 0) {
document.getElementById('nCubes').value = newItems.length;
await sleep(0);
}
const el = document.createElement('div');
el.className = 'item';
//el.innerHTML = i;
el.style.backgroundColor = randomColor();
el.style.top = `${Math.round(Math.random() * 90)}%`;
el.style.left = `${Math.round(Math.random() * 60)}%`;
el.style.width = `${cubeSize}px`;
el.style.height = `${cubeSize}px`;
frame.after(el);
const existingOverlapping = within_frame(el, newItems);
if (existingOverlapping.size > 0) {
i--;
failedGenerated++;
el.parentNode.removeChild(el);
continue;
}
newItems.push(el);
}
console.log('failedAttempts', failedGenerated);
allItems = newItems;
frame.style.zIndex = 3;
document.getElementById('nCubes').value = newItems.length;
}
frame.addEventListener('mouseup', () => {measure(); measureLoop()});
spawnCubes().then(() => {measure(); measureLoop();});
document.getElementById('randomize').addEventListener('click', e => {
spawnCubes().then(measure);
})
#frame {
height: 3rem;
width: 3rem;
display: inline-block;
resize: both;
border: solid black 0.1rem;
overflow: auto;
position: absolute;
z-index: 3;
}
.item {
height: 1rem;
width: 1rem;
position: absolute;
z-index: 2;
}
.controls {
position: fixed;
bottom: 4px;
right: 4px;
text-align: right;
}
<div id="frame"></div>
<div class="controls">
<button id="measure">
measure
</button>
<button id="randomize">
spawn cubes
</button>
<div>
N cubes:
<input id="nCubes" type="number" value="40">
</div>
<div>
Cube size:
<input id="size" type="number" value="16">
</div>
<div>
N inside large:
<span id="result">
</span>
</div>
<div>
Time (ms):
<span id="time">
</span>
</div>
<div>
Points:
<span id="points">
</span>
</div>
<div>
N inside large (loop):
<span id="result-loop">
</span>
</div>
<div>
Time (ms) (loop):
<span id="time-loop">
</span>
</div>
</div>
