Find most unpopulated points in a coordinate system
(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:
- 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.
- 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>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>