List<List<Vector2>> rows = BuildPositionRows(hexPositions, tolerance);
for (int row = 0; row < rows.Count; row++)
{
List<Vector2> rowPositions = rows[row];
rowPositions.Sort((left, right) => left.x.CompareTo(right.x));
for (int i = 0; i < rowPositions.Count - 1; i++)
{
Vector2 left = rowPositions[i];
Vector2 right = rowPositions[i + 1];
if (Mathf.Abs((right.x - left.x) - xStep) > tolerance)
{
continue;
}
Vector2 middle = (left + right) * 0.5f;
TryAddPocket(pockets, hexPositions, new Vector2(middle.x, middle.y + rowStep), tolerance);
TryAddPocket(pockets, hexPositions, new Vector2(middle.x, middle.y - rowStep), tolerance);
}
}
return pockets;
}
private List<List<Vector2>> BuildPositionRows(List<Vector2> positions, float tolerance)
{
var rows = new List<List<Vector2>>();
for (int i = 0; i < positions.Count; i++)
{
Vector2 position = positions[i];
List<Vector2> row = FindPositionRow(rows, position.y, tolerance);
if (row == null)
{
row = new List<Vector2>();
rows.Add(row);
}
row.Add(position);
}
return rows;
}
private List<Vector2> FindPositionRow(List<List<Vector2>> rows, float z, float tolerance)
{
for (int i = 0; i < rows.Count; i++)
{
if (rows[i].Count > 0 && Mathf.Abs(rows[i][0].y - z) <= tolerance)
{
return rows[i];
}
}
return null;
}
private void TryAddPocket(List<Vector2> pockets, List<Vector2> hexPositions, Vector2 candidate, float tolerance)
{
if (HasPosition(hexPositions, candidate, tolerance) || HasPosition(pockets, candidate, tolerance))
{
return;
}
pockets.Add(candidate);
}
private List<Vector2> ToCenteredPlanePositions(List<Vector2> positions, Vector2 center, float radius)
{
var centeredPositions = new List<Vector2>(positions.Count);
for (int i = 0; i < positions.Count; i++)
{
centeredPositions.Add((positions[i] - center) * radius);
}
return centeredPositions;
}