在坐标系中找到最多未填充的点
Find most unpopulated points in a coordinate system
我有一个基本上代表屏幕的坐标系。
我有任意数量的头寸。例如：
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},
];
我正在寻找一种算法来找到人口最少的点。
白色的小圆圈代表人口，红色的 Xs 标记点在我看来人口稀少：
我的目标是 运行 将所有这些白色迷你圆圈随机移动到随机方向的动画，一旦圆圈离开屏幕，它就会被传送到最无人居住的地方，这样大的空白区域减少了。
我试图通过计算从每个整数坐标到每个圆的距离总和然后选择距离总和最大的坐标来实现这一点。仅此一项似乎就已经 CPU 密集了，但我注意到该算法会导致圆圈传送到我坐标系的边界。所以我还添加了从每个整数坐标到每个边界整数坐标的距离之和。那时，脚本基本上冻结了。所以这绝对不是正确的做法。
我运行没主意了。我想我不需要一个完美的算法，而是一个在精度和性能之间取得健康平衡的算法。
最后，我希望能够在 1920x1080 canvas 上每秒多次 运行 该算法，其中大约有 80 个这样的小圆圈。理想情况下，该算法将有一个参数来调整准确性，从而调整它使用的 CPU 时间。
这就是我上面提到的方法。我注释掉了导致脚本冻结的行：
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>
原始解决方案（经过编辑）
这里有一个例子，不过我觉得如果你有更多的圈子可能会更有趣。
- 我只计算到几个最近的圆圈的距离
- 根据您的要求，我已将 canvas 的边框排斥新的圆圈，因此您不太可能在边框上获得新的圆圈。
这是通过计算到边缘的距离 (
[canvas.width - coord.x, coord.x - 0, canvas.height - coord.y, coord.y -0]) 以及到每个现有圆的距离来完成的。
（我也换成了更实用的风格，因为我发现这样更容易，虽然这不是必需的。）
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>
互动版
这是一个更具交互性的版本，您可以测试它的工作原理。正如您将看到的，大多数时候，当其他圆圈是随机生成时，人口密度最低的区域位于边缘。此外，你在检查距离时计算的圆圈越多，你在选择人口最少的区域时就越倾向于向边缘和角落移动。
寻找人口最少的区域的逻辑与原始解决方案中的逻辑相同。
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>
(因为是黑底白点canvas，为了方便区分，就把白点叫做星星)
首先，您的解决方案似乎不符合您的标准。您不需要与所有明星的距离总和最大的点。您需要距离最近的恒星最远的点。
为了详细说明，我们举个例子，中心有一颗星星，离中心有一段距离的星星有很多：
"largest distance sum" 方法可能会在红色圆圈中的某处给出一个点（太近甚至与中心星星重叠），而您想要的更像是绿色圆圈中的东西：
考虑到这一点：
- 首先我们应该把屏幕分成大小合适的正方形，我们将从这些正方形中构建一个距离图，以找到与任何星星距离最大的那个。
"reasonably-sized" 部分在性能方面非常重要。您使用了 1920x1080 分辨率，在我看来这太精细了。为了获得视觉上足够令人愉悦的结果，48x30 甚至 32x20 的分辨率就足够了。
- 要实际构建距离图，我们可以简单地使用 Breadth-first Search。我们将所有星星的位置转换为网格坐标，并将其用作 BFS 的起始位置。
结果会是这样的：
这里还有一个大问题：最红的方块在底边！
原来边缘和角方块比中心坐标有 "cheating" 优势，因为没有星形朝向一侧（对于角方块甚至是 3 个边）。所以很可能角和边正方形与任何星星的距离最大。
您的艺术作品在视觉上不是很赏心悦目吗？所以我们可以通过过滤掉特定填充内的结果来作弊。幸运的是，BFS 的结果默认是排序的，所以我们可以迭代结果，直到找到一个适合所需区域的结果。
下面是带注释的完整代码。即使距离图可见，整个过程也需要 20 毫秒，这对于一个 webgl 片段来说应该足够了（运行 @ max 30fps ~ 33ms/frame）
此解决方案还将处理极少数情况，即多颗星在同一帧移出边界。在那种情况下，只需从 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>
你可以把canvas想象成一个1080×1920列和行的矩阵，初始化为1代表空白区域，0代表第xth列，y th 行表示该坐标处的点。您现在需要在二进制矩阵中找到最大的空矩形。
此 Dr. Dobb's article 包含解决该问题的最快算法之一。您可以在 Internet 上找到 JavaScript 实现或自己实现。
也可以考虑求最大空方格
var canvas = document.querySelector("#canvas-1");
var rctx = canvas.getContext("2d");
var ncols = canvas.width;
var nrows = canvas.height;
var npoints = +canvas.dataset.points;
var matrix = Array(nrows).fill(0).map(function() {
return Array(ncols).fill(1);
});
var i, x, y, t0, t1, maxrect, maxsquare;
/*
* For consistency with algorithms, the matrix is initialized with 1s
* representing the blank area and the points are represented with 0s
*/
for (i = 0; i < npoints; i++) {
x = Math.floor(Math.random() * ncols);
y = Math.floor(Math.random() * nrows);
matrix[y][x] = 0;
}
t0 = new Date();
maxrect = maximalRectangle(matrix);
t1 = new Date();
console.log("Rectangle found in %dms", t1 - t0);
t0 = new Date();
maxsquare = maximalSquare(matrix);
t1 = new Date();
console.log("Square found in %dms", t1 - t0);
/*
* Render the results
*/
rctx.fillStyle = "rgba(255,0,0,.5)";
rctx.fillRect(maxrect.left, maxrect.top, maxrect.right - maxrect.left + 1, maxrect.bottom - maxrect.top + 1);
rctx.fillStyle = "rgba(0,0,255,.5)";
rctx.fillRect(maxsquare.left, maxsquare.top, maxsquare.right - maxsquare.left + 1, maxsquare.bottom - maxsquare.top + 1);
rctx.fillStyle = "rgb(255,255,255)";
for (y = 0; y < nrows; y++) {
for (x = 0; x < ncols; x++) {
if (matrix[y][x] === 0) {
rctx.fillRect(x, y, 1, 1);
}
}
}
/*
* implementation of this answer:
*
*/
function maximalRectangle(matrix) {
var best_area = 0;
var best_rect = {};
var M = matrix[0].length;
var N = matrix.length;
var c = Array(M + 1).fill(0);
var s = [];
var m, n, open_width, area, prev;
for (n = 0; n < N; n++) {
for (m = 0; m < M; m++) {
if (matrix[n][m] === 0) {
c[m] = 0;
} else {
c[m]++;
}
}
open_width = 0;
for (m = 0; m < M + 1; m++) {
if (c[m] > open_width) {
s.push({
m: m,
w: open_width
});
open_width = c[m];
} else if (c[m] < open_width) {
do {
prev = s.pop();
area = open_width * (m - prev.m);
if (area > best_area) {
best_area = area;
best_rect.left = prev.m;
best_rect.right = m - 1;
best_rect.top = n - open_width + 1;
best_rect.bottom = n;
}
open_width = prev.w;
} while (c[m] < open_width);
open_width = c[m];
if (open_width != 0) {
s.push(prev);
}
}
}
}
return {
area: best_area,
left: best_rect.left,
top: best_rect.top,
right: best_rect.right,
bottom: best_rect.bottom
};
}
/*
* (possibly buggy) implementation of this answer:
*
*/
function maximalSquare(matrix) {
var best_length = 0;
var best_square = {};
var M = matrix[0].length;
var N = matrix.length;
var c = Array(M + 1).fill(0);
var n, m, temp, prev = 0;
for (n = 1; n <= N; n++) {
for (m = 1; m <= M; m++) {
temp = c[m];
if (matrix[n - 1][m - 1] === 1) {
c[m] = Math.min(Math.min(c[m - 1], prev), c[m]) + 1;
if (best_length < c[m]) {
best_length = c[m];
best_square.left = m - best_length;
best_square.right = m - 1;
best_square.top = n - best_length;
best_square.bottom = n - 1;
}
} else {
c[m] = 0;
}
prev = temp;
}
}
return {
area: best_length * best_length,
left: best_square.left,
top: best_square.top,
right: best_square.right,
bottom: best_square.bottom
};
}
<canvas id="canvas-1" width="1920" height="1080" data-points="80" style="background-color: #000;"></canvas>
我有一个基本上代表屏幕的坐标系。
我有任意数量的头寸。例如：
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},
];
我正在寻找一种算法来找到人口最少的点。
白色的小圆圈代表人口，红色的 Xs 标记点在我看来人口稀少：
我的目标是 运行 将所有这些白色迷你圆圈随机移动到随机方向的动画，一旦圆圈离开屏幕，它就会被传送到最无人居住的地方，这样大的空白区域减少了。
我试图通过计算从每个整数坐标到每个圆的距离总和然后选择距离总和最大的坐标来实现这一点。仅此一项似乎就已经 CPU 密集了，但我注意到该算法会导致圆圈传送到我坐标系的边界。所以我还添加了从每个整数坐标到每个边界整数坐标的距离之和。那时，脚本基本上冻结了。所以这绝对不是正确的做法。
我运行没主意了。我想我不需要一个完美的算法，而是一个在精度和性能之间取得健康平衡的算法。 最后，我希望能够在 1920x1080 canvas 上每秒多次 运行 该算法，其中大约有 80 个这样的小圆圈。理想情况下，该算法将有一个参数来调整准确性，从而调整它使用的 CPU 时间。
这就是我上面提到的方法。我注释掉了导致脚本冻结的行：
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>
原始解决方案（经过编辑）
这里有一个例子，不过我觉得如果你有更多的圈子可能会更有趣。
- 我只计算到几个最近的圆圈的距离
- 根据您的要求，我已将 canvas 的边框排斥新的圆圈，因此您不太可能在边框上获得新的圆圈。
这是通过计算到边缘的距离 (
[canvas.width - coord.x, coord.x - 0, canvas.height - coord.y, coord.y -0]) 以及到每个现有圆的距离来完成的。
（我也换成了更实用的风格，因为我发现这样更容易，虽然这不是必需的。）
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>
互动版
这是一个更具交互性的版本，您可以测试它的工作原理。正如您将看到的，大多数时候，当其他圆圈是随机生成时，人口密度最低的区域位于边缘。此外，你在检查距离时计算的圆圈越多，你在选择人口最少的区域时就越倾向于向边缘和角落移动。
寻找人口最少的区域的逻辑与原始解决方案中的逻辑相同。
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>
(因为是黑底白点canvas，为了方便区分，就把白点叫做星星)
首先，您的解决方案似乎不符合您的标准。您不需要与所有明星的距离总和最大的点。您需要距离最近的恒星最远的点。
为了详细说明，我们举个例子，中心有一颗星星，离中心有一段距离的星星有很多：
"largest distance sum" 方法可能会在红色圆圈中的某处给出一个点（太近甚至与中心星星重叠），而您想要的更像是绿色圆圈中的东西：
考虑到这一点：
- 首先我们应该把屏幕分成大小合适的正方形，我们将从这些正方形中构建一个距离图，以找到与任何星星距离最大的那个。
"reasonably-sized" 部分在性能方面非常重要。您使用了 1920x1080 分辨率，在我看来这太精细了。为了获得视觉上足够令人愉悦的结果，48x30 甚至 32x20 的分辨率就足够了。
- 要实际构建距离图，我们可以简单地使用 Breadth-first Search。我们将所有星星的位置转换为网格坐标，并将其用作 BFS 的起始位置。
结果会是这样的：
这里还有一个大问题：最红的方块在底边！
原来边缘和角方块比中心坐标有 "cheating" 优势，因为没有星形朝向一侧（对于角方块甚至是 3 个边）。所以很可能角和边正方形与任何星星的距离最大。
您的艺术作品在视觉上不是很赏心悦目吗？所以我们可以通过过滤掉特定填充内的结果来作弊。幸运的是，BFS 的结果默认是排序的，所以我们可以迭代结果，直到找到一个适合所需区域的结果。
下面是带注释的完整代码。即使距离图可见，整个过程也需要 20 毫秒，这对于一个 webgl 片段来说应该足够了（运行 @ max 30fps ~ 33ms/frame）
此解决方案还将处理极少数情况，即多颗星在同一帧移出边界。在那种情况下，只需从 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>
你可以把canvas想象成一个1080×1920列和行的矩阵，初始化为1代表空白区域，0代表第xth列，y th 行表示该坐标处的点。您现在需要在二进制矩阵中找到最大的空矩形。
此 Dr. Dobb's article 包含解决该问题的最快算法之一。您可以在 Internet 上找到 JavaScript 实现或自己实现。
也可以考虑求最大空方格
var canvas = document.querySelector("#canvas-1");
var rctx = canvas.getContext("2d");
var ncols = canvas.width;
var nrows = canvas.height;
var npoints = +canvas.dataset.points;
var matrix = Array(nrows).fill(0).map(function() {
return Array(ncols).fill(1);
});
var i, x, y, t0, t1, maxrect, maxsquare;
/*
* For consistency with algorithms, the matrix is initialized with 1s
* representing the blank area and the points are represented with 0s
*/
for (i = 0; i < npoints; i++) {
x = Math.floor(Math.random() * ncols);
y = Math.floor(Math.random() * nrows);
matrix[y][x] = 0;
}
t0 = new Date();
maxrect = maximalRectangle(matrix);
t1 = new Date();
console.log("Rectangle found in %dms", t1 - t0);
t0 = new Date();
maxsquare = maximalSquare(matrix);
t1 = new Date();
console.log("Square found in %dms", t1 - t0);
/*
* Render the results
*/
rctx.fillStyle = "rgba(255,0,0,.5)";
rctx.fillRect(maxrect.left, maxrect.top, maxrect.right - maxrect.left + 1, maxrect.bottom - maxrect.top + 1);
rctx.fillStyle = "rgba(0,0,255,.5)";
rctx.fillRect(maxsquare.left, maxsquare.top, maxsquare.right - maxsquare.left + 1, maxsquare.bottom - maxsquare.top + 1);
rctx.fillStyle = "rgb(255,255,255)";
for (y = 0; y < nrows; y++) {
for (x = 0; x < ncols; x++) {
if (matrix[y][x] === 0) {
rctx.fillRect(x, y, 1, 1);
}
}
}
/*
* implementation of this answer:
*
*/
function maximalRectangle(matrix) {
var best_area = 0;
var best_rect = {};
var M = matrix[0].length;
var N = matrix.length;
var c = Array(M + 1).fill(0);
var s = [];
var m, n, open_width, area, prev;
for (n = 0; n < N; n++) {
for (m = 0; m < M; m++) {
if (matrix[n][m] === 0) {
c[m] = 0;
} else {
c[m]++;
}
}
open_width = 0;
for (m = 0; m < M + 1; m++) {
if (c[m] > open_width) {
s.push({
m: m,
w: open_width
});
open_width = c[m];
} else if (c[m] < open_width) {
do {
prev = s.pop();
area = open_width * (m - prev.m);
if (area > best_area) {
best_area = area;
best_rect.left = prev.m;
best_rect.right = m - 1;
best_rect.top = n - open_width + 1;
best_rect.bottom = n;
}
open_width = prev.w;
} while (c[m] < open_width);
open_width = c[m];
if (open_width != 0) {
s.push(prev);
}
}
}
}
return {
area: best_area,
left: best_rect.left,
top: best_rect.top,
right: best_rect.right,
bottom: best_rect.bottom
};
}
/*
* (possibly buggy) implementation of this answer:
*
*/
function maximalSquare(matrix) {
var best_length = 0;
var best_square = {};
var M = matrix[0].length;
var N = matrix.length;
var c = Array(M + 1).fill(0);
var n, m, temp, prev = 0;
for (n = 1; n <= N; n++) {
for (m = 1; m <= M; m++) {
temp = c[m];
if (matrix[n - 1][m - 1] === 1) {
c[m] = Math.min(Math.min(c[m - 1], prev), c[m]) + 1;
if (best_length < c[m]) {
best_length = c[m];
best_square.left = m - best_length;
best_square.right = m - 1;
best_square.top = n - best_length;
best_square.bottom = n - 1;
}
} else {
c[m] = 0;
}
prev = temp;
}
}
return {
area: best_length * best_length,
left: best_square.left,
top: best_square.top,
right: best_square.right,
bottom: best_square.bottom
};
}
<canvas id="canvas-1" width="1920" height="1080" data-points="80" style="background-color: #000;"></canvas>