(так как это белая точка на черном холсте, я назову белую точку звездой для легкого различения)
Прежде всего, ваше решение не соответствует вашим критериям.Вам не нужна точка с наибольшей суммой расстояния до всей звезды.Вам нужна точка с самым дальним расстоянием до ее ближайшей звезды .
Чтобы уточнить, скажем, например, такую ситуацию, когда одна звезда находится в центре, а большое количество звезд несколькорасстояние от центра:
Метод "сумма наибольшего расстояния", вероятно, даст точку где-то в красном круге (который слишком близко илидаже перекрывают центральную звезду), а то, что вы хотите, больше похоже на что-то в зеленом круге:
Имея это в виду:
- Прежде всего мы должны разделить экран на квадраты разумного размера, мы построим карту расстояний из этих квадратов, чтобы найти ту, которая имеет наибольшее расстояние от любой звезды.
Часть «разумного размера» очень важна с точки зрения производительности.Вы использовали разрешение 1920x1080, которое, на мой взгляд, слишком детально.Чтобы получить визуально приятный результат, разрешение 48x30 или даже 32x20 будет более чем достаточно.
Чтобы действительно построить карту расстояний, мы можем просто использовать
Поиск в ширину .Мы преобразуем положение всех звезд в координаты сетки и используем их в качестве начальных позиций BFS.
Результат будет примерно таким:
Здесь все еще есть одна большая проблема: красный квадрат находится у нижнего края!
Получите, что края и угловые квадраты имеют «обманное» преимущество перед центральными координатами, так как нет звездыв сторону (или даже 3 стороны, для угловых квадратов).Таким образом, очень вероятно, что квадрат угла и края будет иметь наибольшее расстояние до любой звезды.
Это не очень приятно для вашего художественного произведения?Таким образом, мы можем немного обмануть, отфильтровав результаты, которые находятся в пределах определенного отступа.К счастью, результаты BFS сортируются по умолчанию, поэтому мы можем просто перебирать результаты, пока не найдем тот, который помещается в нужную область.
Ниже приведен полный код с комментарием.Даже при отображении карты расстояний весь процесс занимает 20 мс, что должно быть достаточно для фрагмента webgl (который работает при макс. 30 к / с ~ 33 мс / кадр)
Это решение также позаботится о редких случаях, когда несколько звезд выходятсвязаны в том же кадре.В этом случае просто получите несколько разных координат из результата BFS.
<!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>
Редактировать :
Я только что прочитал ответ @ArneHugo и вижу добавление границы вместесо звездами в качестве стартовых позиций BFS также будет работать.Это немного медленнее, но дает более приятный результат.
Вот еще одна версия, которая реализует их идею:
<!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>