在坐标系中查找大多数未填充的点
For*_*vin 7 javascript point coordinates coordinate-systems
我有一个基本代表一个屏幕的坐标系.
我有任意数量的职位.例如:
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画布上每秒多次运行该算法,其中大约有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>(因为它是黑色画布上的白点,我会称之为白点星,以便于区分)
首先,您的解决方案似乎不符合您的标准.你不需要与所有恒星的距离最大的点.你需要距离它最近的恒星最远的点.
详细说来,比如说这样的情况,中心有一颗恒星,距离中心有一定距离的大量恒星:
"最大距离和"方法可能会在红色圆圈的某个位置给出一个点(它太靠近甚至与中心星重叠),而你想要的更像是绿色圆圈中的某些东西:
考虑到这一点:
- 首先,我们应该将屏幕划分为合理大小的正方形,我们将从这些正方形构建距离图,以找到与任何恒星距离最远的那个.
"合理大小"的部分在性能方面非常重要.您使用的是1920x1080分辨率,这在我看来太精细了.为了获得足够令人愉悦的结果,48x30甚至32x20的分辨率就足够了.
- 要实际构建距离图,我们可以简单地使用广度优先搜索.我们将所有星星的位置转换为网格坐标,并将其用作BFS的起始位置.
结果将是这样的:
这里还有一个很大的问题:最红的广场位于最底层!
边缘和角落方形比中心坐标具有"欺骗"优势,因为一侧没有星形(甚至是三角形,角形方块).因此角落和边缘正方形很可能与任何恒星的距离最大.
你的艺术作品在视觉上是不是很令人愉悦？所以我们可以通过过滤掉某个填充内的结果来作弊.幸运的是,BFS的结果默认排序,因此我们可以迭代结果,直到找到适合所需区域的结果.
以下是带注释的完整代码.即使可以看到距离图,整个过程也需要20ms,对于webgl片来说应该足够了(运行@ max 30fps~33ms /帧)
这个解决方案还将处理几个星星在同一帧移出界限的罕见情况.在这种情况下,只需从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>