javascript - 在坐标系中找到最多未填充的点

标签 javascript coordinates point 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 标记点在我看来非常稀少:

screenshot

我的目标是运行一个动画，将所有这些白色迷你圆圈随机移动到随机方向，一旦圆圈离开屏幕，它就会被传送到最无人居住的地方，从而减少大的空白空间。

我试图通过计算从每个整数坐标到每个圆的距离总和，然后选择距离总和最大的坐标来实现这一点。仅此一项似乎就已经占用大量 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 上的白点，为了方便区分，我就把白点称为星星)

首先，您的解决方案似乎不符合您的标准。您不需要与所有明星的距离总和最大的点。您需要距离最近的恒星最远的点。

为了详细说明，我们举个例子这样的情况，中心有一颗星星，离中心有一段距离的地方有大量星星:

enter image description here

“最大距离和”方法可能会在红色圆圈中的某处给出一个点(太近甚至与中心星重叠)，而您想要的更像是绿色圆圈中的点:

enter image description here

考虑到这一点:

  1. 首先，我们应该将屏幕分成大小合适的正方形，我们将从这些正方形构建一个距离图，以找到与任何星星距离最大的那个。

“合理大小”部分在性能方面非常重要。您使用了 1920x1080 分辨率，在我看来这太精细了。要获得视觉上足够令人愉悦的结果，48x30 甚至 32x20 的分辨率就足够了。

  1. 要实际构建距离图，我们可以简单地使用 Breadth-first Search .我们将所有星星的位置转换为网格坐标，并将其用作 BFS 的起始位置。

结果会是这样的:

enter image description here

这里还有一个大问题:最红的方 block 在底部边缘!

事实证明，边 Angular 正方形比中心坐标具有“作弊”优势，因为没有星形朝向一侧(对于 Angular 正方形，甚至是 3 个边)。所以很可能 Angular 和边正方形与任何星星的距离最大。

您的艺术作品在视觉上不是很赏心悦目吗？所以我们可以通过过滤掉特定填充内的结果来作弊。幸运的是，默认情况下 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>

关于javascript - 在坐标系中找到最多未填充的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54516362/

上一篇：javascript - 事件如何冒泡到 document 而不是 document.body？

下一篇：javascript - 从具有 O(n) 的数组中获取最大的时间顺​​序下降、最小值和最大值

相关文章：

javascript - 简单的 Highchart 作为单独的 .js 文件工作，但不在 View 中

javascript - 按钮单击更改颜色

android - 如何使用屏幕像素绘制

c++ - 无法将 QGraphicsView 坐标映射到 QGraphicsScene

math - 二次贝塞尔曲线 : Calculate Points

javascript - 将 map 转换为数组 - Javascript

javascript - axios.then(res => { console.log(this) }) 打印未定义

python - 列表对子列表的理解？

ios - 如何使用 ScrollView 缩放到中心？

javascript - 小数点后的值未在 Javascript 中计算

©2024 IT工具网  联系我们