Find most unpopulated points in a coordinate system

Question

I have a coordinate system which basically represents a screen.
And I have an arbitrary amount of positions. E.g.:

population = [
    {x: 100.44, 200.54},
    {x: 123.45, 678.9},
    {x: 1300.23, 435.81},
    {x: 462.23, 468.37},
    {x: 956.58, 385.38},
];

I'm looking for an algorithm that finds the most unpopulated point.

The white mini circles represent the population and the red Xs mark points that appear very unpopulated to me:

My goal is run an animation that randomly moves all these white mini circles into random directions and as soon as a circle has left the screen it should get teleported to the most unpopulated spot so that the amount of big empty spaces gets reduced.

I have tried to achieve that by calculating the sum of distances from every integer coordinate to every circle and then choosing the coordinate that has the highest distance sum. That alone seems to be pretty CPU intensive already, but I noticed that this algorithm causes the circles to teleport to the borders of my coordinate system. So I also added the sums of the distances from each integer coordinate to every border integer coordinate. At that point, the script essentially freezes. So this is definitely not the right approach.

I'm running out of ideas. I guess I don't need a perfect algorithm, but rather one with a healthy balance between precision and performance. In the end I want to be able to run that algorithm multiple times per second on 1920x1080 canvas with around 80 of these minicircles. Ideally the algorithm would have a parameter to adjust the accuracy and thus how much CPU time it uses.

This was my approach mentioned above. I commented out the lines that caused the script to just freeze:

let circles = [
    {x: 60.44, y: 190.54},
    {x: 103.45, y: 18.9},
    {x: 390.23, y: 135.81},
    {x: 302.23, y: 28.37},
    {x: 56.58, y: 85.38},
]

function getDistance(p1, p2) {
    return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
}
function drawCircle(ctx,x,y,r,c) {
    ctx.beginPath()
    ctx.arc(x, y, r, 0, 2 * Math.PI, false)
    ctx.fillStyle = c
    ctx.fill()
}


const canvas = document.getElementById('canvas')
const ctx = canvas.getContext("2d")

let highestDistanceSum = 0
let coordWithHighestDistanceSum
for (let x=0; x<canvas.width; x++) {
    for (let y=0; y<canvas.height; y++) {
        let canvasCoord = {x: x, y: y}
        let distanceSum = 0
        for (let circle of circles) {
            distanceSum += getDistance(canvasCoord, circle)
        }
        /*
        // Pretend as if every pixel on the border is a circle
        // Causes massive CPU usage
        for (let x2=0; x<canvas.width; x2++) {
            distanceSum += getDistance(canvasCoord, {x: x2, y: 0})
            distanceSum += getDistance(canvasCoord, {x: x2, y: canvas.height})
        }
        for (let y2=0; y<canvas.height; y2++) {
            distanceSum += getDistance(canvasCoord, {x: 0, y: y2})
            distanceSum += getDistance(canvasCoord, {x: canvas.width, y: y2})
        }
        */
            
        if (distanceSum > highestDistanceSum) {
            coordWithHighestDistanceSum = canvasCoord
            highestDistanceSum = distanceSum
        }
    }
}


for (let p of circles) {
    drawCircle(ctx, p.x, p.y, 3, 'black')
}

drawCircle(ctx, coordWithHighestDistanceSum.x, coordWithHighestDistanceSum.y, 5, 'red')

<canvas id="canvas" width="400" height="200" style="border:1px solid #d3d3d3;"></canvas>

Answer 1

(Since it's white dot on black canvas, I'll call the white points star for easy distinction)

First of all your solution doesn't seem to fit your criteria. You don't need the point with largest sum of distance to all star. You need the point with furthest distance to its nearest star.

To elaborate, let's say for example a situation like this, where there's one star at the center and a large number of stars some distance away from the center:

The "largest distance sum" method would probably give a point somewhere in the red circle (which is too close or even overlap the center star), while what you want would more like something in the green circle:

With that in mind:

1. First of all we should divide the screen into reasonably-sized squares, we will build a distance map from those squares to find the one that has largest distance from any star.

The "reasonably-sized" part is quite important performance-wise. You used the 1920x1080 resolution, which is way too fine-grained in my opinion. To get a visually pleasing enough result, a resolution of 48x30 or even 32x20 would be more than enough.

2. To actually build the distance map, we can simply use a Breadth-first Search. We convert all stars' position to grid coordinate, and use those as BFS's starting positions.

The result would be something like this:

There's still one big problem here: the red-est square is at the bottom edge!

Turn out edge and corner squares have a "cheating" advantage over center coords, since there's no star toward one side (or even 3 sides, for corner squares). So it is very likely that a corner and edge square will have largest distance to any star.

It is not very visually pleasing for your, um, art piece? So we can cheat a bit by filtering out results that are within a certain padding. Luckily BFS' results are sorted by default, so we can just iterate over the result until we find one that fit within the desired area.

Below is the full code with comment. Even with distance map visible the whole process take 20ms, which should be enough for a webgl piece (which run @ max 30fps ~ 33ms/frame)

This solution will also take care of rare cases where several star move out of bound at the same frame. In that case just fetch several different coords from BFS's result.

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>

<body style="margin: 0; padding: 0;">
  <canvas id="canvas" style="display: block;"></canvas>
  <script>
    // higher GRID_WIDTH = better result, more calculation time
    // We will caculate gridHeight later based on window size
    const GRID_WIDTH = 48;
    const GRID_PADDING = 3;

    const heatMapColors = [
      '#ffffff',
      '#ffdddd',
      '#ffbbbb',
      '#ff9999',
      '#ff7777',
      '#ff5555',
      '#ff3333',
      '#ff0000'
    ]

    const init = () => {
      var circles = [];
      for (var i = 0; i < 90; i++) {
        circles.push({
          x: Math.random() * window.innerWidth,
          y: Math.random() * window.innerHeight
        });
      }

      const canvas = document.getElementById('canvas')
      canvas.width = window.innerWidth;
      canvas.height = window.innerHeight;
      const ctx = canvas.getContext("2d");

      const cellSize = window.innerWidth / GRID_WIDTH;
      const gridHeight = Math.ceil(canvas.height / cellSize);

      update(ctx, circles, GRID_WIDTH, gridHeight, cellSize);
    }

    const update = (ctx, circles, gridWidth, gridHeight, cellSize) => {
      const start = new Date();

      // Perform a BFS from all stars to find distance of each rect from closest star
      // After BFS visitedCoords will be an array of all grid rect, with distance-from-star (weight) sorted in ascending order
      var bfsFrontier = getGridCoordOfStars(circles, cellSize).map(coord => ({ ...coord, weight: 0 }));
      var visitedCoords = [...bfsFrontier];

      while (bfsFrontier.length > 0) {
        const current = bfsFrontier.shift();
        const neighbors = getNeighbors(current, gridWidth, gridHeight);

        for (let neighbor of neighbors) {
          if (visitedCoords.findIndex(weightedCoord => coordsEqual(weightedCoord, neighbor)) === -1) {
            visitedCoords.push(neighbor);
            bfsFrontier.push(neighbor);
          }
        }
      }

      // Visualize heatmap
      for (let coord of visitedCoords) {
        drawRect(ctx, coord.x * cellSize, coord.y * cellSize, cellSize, cellSize, heatMapColors[Math.min(coord.weight, heatMapColors.length - 1)]);
      }

      const emptiestCoord = getLastCoordWithinPadding(visitedCoords, gridWidth, gridHeight, GRID_PADDING);
      const emptiestPosition = {
        x: (emptiestCoord.x + 0.5) * cellSize,
        y: (emptiestCoord.y + 0.5) * cellSize
      }

      drawCircle(ctx, emptiestPosition.x, emptiestPosition.y, 5, 'yellow');
      for (let p of circles) {
        drawCircle(ctx, p.x, p.y, 3, 'black')
      }

      console.log(`Processing time: ${new Date().getTime() - start.getTime()} ms`);
    }

    const drawCircle = (ctx, x, y, r, c) => {
      ctx.beginPath()
      ctx.arc(x, y, r, 0, 2 * Math.PI, false)
      ctx.fillStyle = c
      ctx.fill()
    }

    const drawRect = (ctx, x, y, width, height, c) => {
      ctx.beginPath();
      ctx.rect(x, y, width, height);
      ctx.fillStyle = c;
      ctx.fill();
    }

    // Convert star position to grid coordinate
    // Don't need to worry about duplication, BFS still work with duplicates
    const getGridCoordOfStars = (stars, cellSize) =>
      stars.map(star => ({
        x: Math.floor(star.x / cellSize),
        y: Math.floor(star.y / cellSize)
      }))

    const coordsEqual = (coord1, coord2) => coord1.x === coord2.x && coord1.y === coord2.y;

    const getNeighbors = (weightedCoord, gridWidth, gridHeight) => {
      var result = [];
      if (weightedCoord.x > 0) result.push({ x: weightedCoord.x - 1, y: weightedCoord.y, weight: weightedCoord.weight + 1 })
      if (weightedCoord.x < gridWidth - 1) result.push({ x: weightedCoord.x + 1, y: weightedCoord.y, weight: weightedCoord.weight + 1 })

      if (weightedCoord.y > 0) result.push({ x: weightedCoord.x, y: weightedCoord.y - 1, weight: weightedCoord.weight + 1 })
      if (weightedCoord.y < gridHeight - 1) result.push({ x: weightedCoord.x, y: weightedCoord.y + 1, weight: weightedCoord.weight + 1 })

      return result;
    }

    // loop through a BFS result from bottom to top and return first occurence inside padding
    const getLastCoordWithinPadding = (coords, gridWidth, gridHeight, padding) => {
      for (let i = coords.length - 1; i > 0; i--) {
        const coord = coords[i];
        if (
          coord.x >= padding
          && coord.x < gridWidth - padding - 1
          && coord.y >= padding
          && coord.y < gridHeight - padding - 1
        ) return coord;
      }

      // This does not happen with current logic, but I leave it here to catch future code changes
      return coords[coords.length - 1];
    }

    init();
  </script>
</body>

</html>

---

Edit:

I've just read @ArneHugo 's answer, and I see adding the border together with the stars as BFS starting positions will work as well. It is slightly slower but give more pleasing result.

Here's another version that implement their idea:

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>

<body style="margin: 0; padding: 0;">
  <canvas id="canvas" style="display: block;"></canvas>
  <script>
    const GRID_WIDTH = 48; // We will caculate gridHeight based on window size

    const heatMapColors = [
      '#ffffff',
      '#ffdddd',
      '#ffbbbb',
      '#ff9999',
      '#ff7777',
      '#ff5555',
      '#ff3333',
      '#ff0000'
    ]

    const init = () => {
      var circles = [];
      for (var i = 0; i < 90; i++) {
        circles.push({
          x: Math.random() * window.innerWidth,
          y: Math.random() * window.innerHeight
        });
      }

      const canvas = document.getElementById('canvas')
      canvas.width = window.innerWidth;
      canvas.height = window.innerHeight;
      const ctx = canvas.getContext("2d");

      const cellSize = window.innerWidth / GRID_WIDTH;
      const gridHeight = Math.ceil(canvas.height / cellSize); // calculate gridHeight

      // cache border coords array since it's never changed
      const borderCoords = getBorderCoords(GRID_WIDTH, gridHeight);

      update(ctx, circles, GRID_WIDTH, gridHeight, cellSize, borderCoords);
    }

    const update = (ctx, circles, gridWidth, gridHeight, cellSize, borderCoords) => {
      const start = new Date();

      // Perform a BFS from all stars to find distance of each rect from closest star
      // After BFS visitedCoords will be an array of all grid rect, with distance-from-star (weight) sorted in ascending order

      var bfsFrontier = borderCoords.concat(
        getGridCoordOfStars(circles, cellSize).map(coord => ({ ...coord, weight: 0 }))
      );

      var visitedCoords = [...bfsFrontier];

      while (bfsFrontier.length > 0) {
        const current = bfsFrontier.shift();
        const neighbors = getNeighbors(current, gridWidth, gridHeight);

        for (let neighbor of neighbors) {
          if (visitedCoords.findIndex(weightedCoord => coordsEqual(weightedCoord, neighbor)) === -1) {
            visitedCoords.push(neighbor);
            bfsFrontier.push(neighbor);
          }
        }
      }

      // Visualize heatmap
      for (let coord of visitedCoords) {
        drawRect(ctx, coord.x * cellSize, coord.y * cellSize, cellSize, cellSize, heatMapColors[Math.min(coord.weight, heatMapColors.length - 1)]);
      }

      const emptiestCoord = visitedCoords[visitedCoords.length - 1];
      const emptiestPosition = {
        x: (emptiestCoord.x + 0.5) * cellSize,
        y: (emptiestCoord.y + 0.5) * cellSize
      }

      drawCircle(ctx, emptiestPosition.x, emptiestPosition.y, 5, 'yellow');
      for (let p of circles) {
        drawCircle(ctx, p.x, p.y, 3, 'black')
      }

      console.log(`Processing time: ${new Date().getTime() - start.getTime()} ms`);
    }

    const drawCircle = (ctx, x, y, r, c) => {
      ctx.beginPath()
      ctx.arc(x, y, r, 0, 2 * Math.PI, false)
      ctx.fillStyle = c
      ctx.fill()
    }

    const drawRect = (ctx, x, y, width, height, c) => {
      ctx.beginPath();
      ctx.rect(x, y, width, height);
      ctx.fillStyle = c;
      ctx.fill();
    }

    const getBorderCoords = (gridWidth, gridHeight) => {
      var borderCoords = [];
      for (var x = 0; x < gridWidth; x++) {
        for (var y = 0; y < gridHeight; y++) {
          if (x === 0 || y === 0 || x === gridWidth - 1 || y === gridHeight - 1) borderCoords.push({ x, y, weight: 0 })
        }
      }

      return borderCoords;
    }

    // Convert star position to grid coordinate and filter out duplicates
    const getGridCoordOfStars = (stars, cellSize) => stars.map(star => ({
      x: Math.floor(star.x / cellSize),
      y: Math.floor(star.y / cellSize)
    }))

    const uniqueCoord = (arr) => arr.filter((candidate, index) => arr.findIndex(item => coordsEqual(item, candidate)) === index);

    const coordsEqual = (coord1, coord2) => coord1.x === coord2.x && coord1.y === coord2.y;

    const getNeighbors = (weightedCoord, gridWidth, gridHeight) => {
      var result = [];
      if (weightedCoord.x > 0) result.push({ x: weightedCoord.x - 1, y: weightedCoord.y, weight: weightedCoord.weight + 1 })
      if (weightedCoord.x < gridWidth - 1) result.push({ x: weightedCoord.x + 1, y: weightedCoord.y, weight: weightedCoord.weight + 1 })

      if (weightedCoord.y > 0) result.push({ x: weightedCoord.x, y: weightedCoord.y - 1, weight: weightedCoord.weight + 1 })
      if (weightedCoord.y < gridHeight - 1) result.push({ x: weightedCoord.x, y: weightedCoord.y + 1, weight: weightedCoord.weight + 1 })

      return result;
    }

    init();
  </script>
</body>

</html>

Answer 2

Original solution (with edits)

Here is an example, though I think it might be more interesting if you have more circles.

• I only count the distance to a few of the closest circles
• As per your request, I've made the borders of the canvas repel new circles, so you're much less likely to get new circles on the border. This is done by counting in the distances to the edges ([canvas.width - coord.x, coord.x - 0, canvas.height - coord.y, coord.y -0]), along with the distances to each of the existing circles.

(I've also changed into a more functional style, because I found that to be easier, though that is not necessary.)

const numberOfCirclesToGetDistanceTo = 2

let circles = [
    {x: 60.44, y: 190.54},
    {x: 103.45, y: 18.9},
    {x: 390.23, y: 135.81},
    {x: 302.23, y: 28.37},
    {x: 56.58, y: 85.38},
]

function getDistance(p1, p2) {
    return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
}
function drawCircle(ctx,x,y,r,c) {
    ctx.beginPath()
    ctx.arc(x, y, r, 0, 2 * Math.PI, false)
    ctx.fillStyle = c
    ctx.fill()
}


const canvas = document.getElementById('canvas')
const ctx = canvas.getContext("2d")

function getCoordWithHighestDistanceSum() {
    const xList = Array(canvas.width).fill().map((_, index) => index)
    const yList = Array(canvas.height).fill().map((_, index) => index)
    const coords = xList.flatMap(x => yList.reduce((coords, y) => coords.concat({ x, y }), []))

    const ascending = (a, b) => a - b
    const sumTotal = (sum, next) => sum + next

    const coordsWithDistance = coords.map(coord => {
        const distances = [
            ...circles.map(circle => getDistance(coord, circle)),
            ...[canvas.width - coord.x, coord.x - 0, canvas.height - coord.y, coord.y -0],
        ]

        return {
            coord,
            dist: distances
                .sort(ascending)
                .slice(0, numberOfCirclesToGetDistanceTo)
                .reduce(sumTotal, 0)
        }
    })

    return coordsWithDistance
        .sort((a, b) => b.dist - a.dist)
        [0].coord
}

const coordWithHighestDistanceSum = getCoordWithHighestDistanceSum()

for (let p of circles) {
    drawCircle(ctx, p.x, p.y, 3, 'black')
}

drawCircle(ctx, coordWithHighestDistanceSum.x, coordWithHighestDistanceSum.y, 5, 'red')

<canvas id="canvas" width="400" height="200" style="border:1px solid #d3d3d3;"></canvas>

Interactive version

Here is a more interactive version so you can test how it works. As you'll see, most of the time, the least densely populated area is along the edge when the other circles are generated randomly. Additionally, the more circles you count in when checking the distance, the more you tend to go towards the edges and the corners when picking the least densely populated area.

The logic for finding least populated area is the same as in the original solution.

let circles = []
let coordWithHighestDistanceSum = void 0

const canvas = document.getElementById('canvas')
const ctx = canvas.getContext("2d")

const xList = Array(canvas.width).fill().map((_, index) => index)
const yList = Array(canvas.height).fill().map((_, index) => index)
const coords = xList.flatMap(x => yList.reduce((coords, y) => coords.concat({ x, y }), []))

function render() {
    ctx.clearRect(0, 0, canvas.width, canvas.height)

    function drawCircle(ctx,x,y,r,c) {
        ctx.beginPath()
        ctx.arc(x, y, r, 0, 2 * Math.PI, false)
        ctx.fillStyle = c
        ctx.fill()
    }

    circles.forEach(circle => drawCircle(ctx, circle.x, circle.y, 3, 'black'))

    if (coordWithHighestDistanceSum) {
        drawCircle(ctx, coordWithHighestDistanceSum.x, coordWithHighestDistanceSum.y, 5, 'red')
    }
}

function generateCircles() {
    const nofCircles = Number(document.getElementById('nofCircles').value)

    const randomCoord = () => coords[Math.floor(Math.random() * coords.length)]

    circles = Array(nofCircles).fill().map(randomCoord)
    findLeastPopulatedCoordinate()

    render()
}

function findLeastPopulatedCoordinate() {
    const nofCirclesToSumDistanceTo = Number(document.getElementById('nofCirclesToSumDistanceTo').value)

    const ascending = (a, b) => a - b
    const sumTotal = (sum, next) => sum + next

    function getDistance(p1, p2) {
        return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
    }

    coordWithHighestDistanceSum = coords
        .map(coord => ({
            coord,
            dist: []
                .concat(circles.map(circle => getDistance(coord, circle)))
                .concat([canvas.width - coord.x, coord.x - 0, canvas.height - coord.y, coord.y -0])
                .sort(ascending)
                .slice(0, nofCirclesToSumDistanceTo)
                .reduce(sumTotal, 0)
        }))
        .sort((a, b) => b.dist - a.dist)
        [0].coord

    render()
}

generateCircles()
findLeastPopulatedCoordinate()

<div>
    <label>Number of circles</label>
    <input type="number" id="nofCircles" value="30" />
</div>
<div>
    <label>Number of circles to sum distance to</label>
    <input type="number" id="nofCirclesToSumDistanceTo" value="1" />
</div>
<button onclick="generateCircles()">Generate circles</button>
<button onclick="findLeastPopulatedCoordinate()">Find least populated coordinate</button>
<canvas id="canvas" width="400" height="200" style="border:1px solid #d3d3d3;"></canvas>