(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>
Nnumber of circles maybemin(canvas.width, canvas.height)/10with a rayon ofmin(canvas.width, canvas.height)/15or something like that, then check the the circles that contain the fewest points – evgeni fotia