泊松盘采样使指数超出范围

Question

这是我使用的泊松盘采样算法实现：

using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;
namespace Assets.Scripts.Algorithms
{
public static class PoissonDiscSampling
{
public static List<Vector2> GeneratePoints(int seed, float radius, Vector2 sampleRegionSize, int sampleAmount)
{
Random.InitState(seed);
float cellSize = radius / Mathf.Sqrt(2);
var grid = new int[Mathf.FloorToInt(sampleRegionSize.x / cellSize), Mathf.FloorToInt(sampleRegionSize.y / cellSize)];
var points = new List<Vector2>();
var spawnPoints = new List<Vector2>
{
sampleRegionSize / 2
};
while (spawnPoints.Count > 0)
{
int spawnIndex = Random.Range(0, spawnPoints.Count);
Vector2 spawnCenter = spawnPoints[spawnIndex];
bool accepted = false;
for (int i = 0; i < sampleAmount; i++)
{
float angle = Random.value * Mathf.PI * 2;
var direction = new Vector2(Mathf.Sin(angle), Mathf.Cos(angle));
Vector2 candidate = spawnCenter + direction * Random.Range(radius, radius * 2);
if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid))
{
points.Add(candidate);
spawnPoints.Add(candidate);
grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;
accepted = true;
break;
}
}
if (!accepted)
{
spawnPoints.RemoveAt(spawnIndex);
}
}
return points;
}
private static bool IsValid(Vector2 candidate, Vector2 sampleRegionSize, float cellSize, float radius,
IList<Vector2> points, int[,] grid)
{
if (candidate.x >= 0 && candidate.x < sampleRegionSize.x && candidate.y >= 0 && candidate.y < sampleRegionSize.y)
{
int cellX = (int)(candidate.x / cellSize);
int cellY = (int)(candidate.y / cellSize);
int searchStartX = Mathf.Max(0, cellX - 2);
int searchStartY = Mathf.Max(0, cellY - 2);
int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1);
int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1);
for (int x = searchStartX; x <= searchEndX; x++)
{
for (int y = searchStartY; y <= searchEndY; y++)
{
int pointIndex = grid[x, y] - 1;
if (pointIndex != -1)
{
float sqrDistance = (candidate - points[pointIndex]).sqrMagnitude;
if (sqrDistance < radius * radius)
{
return false;
}
}
}
}
}
return true;
}
}
}

但是这个算法实现有一个小问题。在线上：

grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;

经过几次迭代后，它抛出

索引超出范围异常

不知何故(我仍然不确定为什么(它超出了grid的大小，有时它可以是负数，有时它可以基本等于grid的大小。

我被困住了，我不知道该怎么办。似乎有些东西我根本看不到。

谢谢！

Answer 1

假设cellSize是 1，sampleRegionSize.X是10.9。这将导致网格大小为10。candidate.X必须小于sampleRegionSize.X才有效，但10.8就可以了。将其转换为 int，您最终会得到10.由于数组是零索引的10因此将超出范围。

故事的寓意;不要相信浮点数学。如果需要将浮点坐标转换为索引，请在尝试使用它之前检查索引是否有效。有很多关于浮点数学危险的文章。