Collision detection circles using recursion in JavaScript

Question

I want to generate circles on random locations with a specific distance from the main circle. The circles should not intersect with each other. I've created a method that checks for each circle if it's not intersecting all other circles. The collision detection does its thing, but the recursion part in my code doesn't work:

if (collision > 0) {
    console.log("GENERATE NEW RANDOM COORDINATE")
    generateRandomCoordinate(d, r)
}

Result

As you can see in the output, my app generates new coordinates (158,290) when it detects collision (138,272). However, it still draws circle at (138,272).

Any idea why this happens? Please let me know if you know more efficient way...

generateRandomCoordinate function

function generateRandomCoordinate(d, r) {
    var phi = Math.random() * 2 * Math.PI
    var x = topicCoordinates[0].x + Math.round(d * Math.cos(phi))
    var y = topicCoordinates[0].y + Math.round(d * Math.sin(phi))
    var collision = 0
    for (var j = 0; j < topicCoordinates.length; j++) {
        var dx = x - topicCoordinates[j].x
        var dy = y - topicCoordinates[j].y
        var distance = Math.sqrt(dx * dx + dy * dy)

        if (distance < r + topicCoordinates[j].r) {
            collision++
            console.log("COLLISION DETECTED BETWEEN POINT(" + "x: " + x + ", y: " + y + ") AND  POINT(x1: " + topicCoordinates[j].x + ", y1: " + topicCoordinates[j].y + ")")
        }
    }
    if (collision > 0) {
        console.log("GENERATE NEW RANDOM COORDINATE")
        generateRandomCoordinate(d, r)
    }

    var topicCoordinate = {
        "x": x,
        "y": y,
        "r": r
    }
    return topicCoordinate
}

Calling the generateRandomCoordinate function

var randomCoordinate = generateRandomCoordinate(d, r)
x = randomCoordinate.x
y = randomCoordinate.y
r = randomCoordinate.r
}

console.log("ADDED POINT(x: " + x + ", y: " + y + ", r: " + r + ")")
var topicCoordinate = {
    "x": x,
    "y": y,
    "r": r
}
topicCoordinates.push(topicCoordinate)
drawCircle(x, y, r)

Output

UPDATE Working code

function generateRandomCoordinate(d, r) {
    var collision = true
    while (collision) {
        collision = false
        var phi = Math.random() * 2 * Math.PI
        var x = topicCoordinates[0].x + Math.round(d * Math.cos(phi))
        var y = topicCoordinates[0].y + Math.round(d * Math.sin(phi))
        for (var j = 0; j < topicCoordinates.length; j++) {
            var dx = x - topicCoordinates[j].x
            var dy = y - topicCoordinates[j].y
            var distance = Math.sqrt(dx * dx + dy * dy)

            if (distance < r + topicCoordinates[j].r) {
                collision = true
                console.log("COLLISION DETECTED BETWEEN POINT(" + "x: " + x + ", y: " + y + ") AND  POINT(x1: " + topicCoordinates[j].x + ", y1: " + topicCoordinates[j].y + ")")
            }
        }
    }

    var topicCoordinate = { "x" : x, "y" : y, "r" : r }
    return topicCoordinate
}

MBo MBo · Accepted Answer · 2016-10-29T17:16:49

There is no need in recursive function call. Just organize cycle (pseudocode)

 repeat
     iscollision = false 
     generate x,y
     for other circles check
         if collision occurs
             iscollision = true
             break  //no need to check later circles    
 until iscollision = false

Concerning your recursive confusion - for every recursive call level function instance contains own internal copies of variables, so outer function doesn't know about inner x,y - you don't return them in this code piece:

  if (collision > 0) {
    vvvvvvvvvvvvvvvvvv
    generateRandomCoordinate(d, r)
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}

Collision detection circles using recursion in JavaScript

1 Answers