Reducing the number of times a helper function is run

Question

I am trying to create a word cloud. In order to render text to the screen I am generating a random position for each word. This works perfectly, however there are a lot of overlapping words. In order to solve this I am storing the position and size of the elements in an array and then I created a helper function that checks for collisions, generates a new position for the element if it finds one, and then calls it's self again to check again from the start of the array. When I run my code the first 2-3 words render just fine but then I get an error saying Maximum call stack size exceeded. I saw there was already a post on this same issue on stack overflow.

I saw that the other person was using a forEach function and so was I so I converted it into a for loop like the answer suggested but it did not do anything. I think the issue boils down to the fact that there are so many collisions but I am not sure how to best approach the issue. Is there another way that I can generate unique positions for elements while still avoiding collisions?

Code:

function calculatePosition(parent, child) {
    return Math.random() * parent - (child / 2)
}

// needed for rendering position of span elements
var ranges = []
var totalWidthOfWords = 0
var totalHeightOfWords = 0

// reposition element if there is a collision
function checkForCollisions(element, height, width, wordCloud, injectedSpan) {
 for(var i = 0; i < ranges.length; i++) {
        let current = ranges[i]
        if(element.left >= current.width[0] && element.left <= current.width[1]) {
          injectedSpan.style.left = calculatePosition(wordCloud.clientWidth, width) + "px";
          checkForCollisions(element, height, width, wordCloud, injectedSpan)
        }
        if(element.top >= current.height[0] && element.top <= current.height[1]) {
      injectedSpan.style.top = calculatePosition(wordCloud.clientHeight, height) + "px";
      checkForCollisions(element, height, width, wordCloud, injectedSpan)
      }
      }
}

// Create content in DOM
const injectedContent = data.map(line => {
const injectedSpan = document.createElement("span")
const injectedWord = document.createElement("p")
const wordCloud = document.querySelector(".word-cloud")

// mod weight value to get more managable inputs
let weightValue = (line.weight * 100).toFixed(2)

// sets values of words and renders them to the screen
injectedWord.innerText = line.word
injectedSpan.appendChild(injectedWord)
wordCloud.appendChild(injectedSpan)

// sets style attribute based on weight value
injectedWord.setAttribute("style", `--i: ${weightValue}`)

// flips words
if(Math.random() > 0.75) {
    injectedWord.style.writingMode = "vertical-rl";
  }


// Entrance animation
let left = innerWidth * Math.random()
let top = innerHeight * Math.random()
if(Math.random() < 0.5) {
  injectedWord.style.left = "-" + left + "px";
  injectedSpan.style.left = calculatePosition(wordCloud.clientWidth, injectedSpan.clientWidth) + "px";
} else {
    injectedWord.style.left = left + "px";
  injectedSpan.style.left = calculatePosition(wordCloud.clientWidth, injectedSpan.clientWidth) + "px";
}
if(Math.random() < 0.5) {
  injectedWord.style.top = "-" + top + "px";
  injectedSpan.style.top = calculatePosition(wordCloud.clientHeight, injectedSpan.clientHeight) + "px";
} else {
    injectedWord.style.top = top + "px";
  injectedSpan.style.top = calculatePosition(wordCloud.clientWidth, injectedSpan.clientWidth) + "px";
}


// Get position of span and change coordinites if there is a collision
let spanPosition = injectedSpan.getBoundingClientRect()
console.log(spanPosition)

if(spanPosition) {
  checkForCollisions(spanPosition, spanPosition.height, spanPosition.width, wordCloud, injectedSpan)
}



totalWidthOfWords += spanPosition.width
totalHeightOfWords += spanPosition.height

ranges.push({width: [spanPosition.left, spanPosition.right], height: [spanPosition.top, spanPosition.bottom]})
})

Link: https://jsfiddle.net/amotor/mdg7rzL1/4/

each time you have a collision, you update the position of the element and then recall checkForCollisions, which is fine in my opinion but the for loop from which you are calling the method just keeps on running! Try to add a "break;" after each recursive checkForCollisions call. This should already reduce the amount of loops. — Cobra_8, Aug 08 '21 at 23:51
`checkForCollisions` could just return whether or not there is a collision and the calling function could handle calculating a new one and calling it again, this would avoid your stack depth issue. However your code seems to have a collision if an element is at the same vertical or horizontal plane as another element, but not necessarily both. I don't know if that's intended or not. — IllusiveBrian, Aug 09 '21 at 00:02
Thank you for pointing that out @IllusiveBrian. That was not intentional. I will update the code. — Alex Motor, Aug 09 '21 at 23:06
I updated the code and changed the checkForCollisions function to return true if the height and width was within the range of an existing element and return false otherwise. In the map function that renders each element I set up a while loop to check if there are any overlapping elements. I thought this would work and it actually did reduce the number of overlapping words, but there are still a few words that overlap. I thought this was a space issue, but there is still plenty of room in the parent div to move the words. I updated the jsFiddle with the new code. — Alex Motor, Aug 10 '21 at 02:46

Cobra_8 · Answer 1 · 2021-08-09T00:37:50.807

There is still a lot of work to do to make sure that it works properly, especially to make sure that the code does not produce any errors!

The general idea would be to follow IllsuiveBrian's comment to make sure, that checkForCollision only does the work of checking if there is a collision and that another function takes care of recalculating the position if necessary and then reevaluating a potential collision.

function checkForCollisions(element, wordCloud, injectedSpan) {
   for(var i = 0; i < ranges.length; i++) {
     let current = ranges[i];
     // return true if there is a collision (you probably have to update the code you are using here to truly avoid collisions!)
     if (collision) { return true; }
   }
    return false; // return false otherwise
}

Finally this part would take care of recalculating position and and rechecking for collision:

ranges.forEach(function(injectedSpan) {

    // Get position of span and change coordinites if there is a collision
    let spanPosition = injectedSpan.getBoundingClientRect();
    if (spanPosition) {
        while (checkForCollisions(spanPosition, wordCloud, injectedSpan)) {
            injectedSpan.style.left = calculatePosition(wordCloud.clientWidth, element.width) + "px";
            injectedSpan.style.top = calculatePosition(wordCloud.clientHeight, element.height) + "px";
    }
 }

});

Here is a quick idea on how to go into this direction: https://jsfiddle.net/euvbax1r/4/

Thanks for this. I did update my code and was able to get words rendered to the screen but the word cloud still renders with overlapping words. My checkForCollisions function now just takes in one argument which is the injectedSpan and loops through the ranges array and compares the width and height. If they are both in range then it returns true. If not then it returns false. I also figured that I can just forgo the forEach function and just extract the while loop. I THOUGHT that this would run, find any collisions, and then check again. I updated the code on the jsFiddle linked above — Alex Motor, Aug 10 '21 at 02:29
I'm glad it helped at least with the crash! Unfortunately the link to the jsFiddle in your post above does not seem to be updated ? — Cobra_8, Aug 12 '21 at 11:39
Apparently when I saved the old file it generated a new link. Sorry about that but I updated the link in my original post — Alex Motor, Aug 12 '21 at 22:18

Reducing the number of times a helper function is run

1 Answers1