R: How is it possible to sample random points from the non-NA region of a raster layer?

I've been attempting to randomly sample a user-defined number of points from a raster layer using spsample, within a region whose extent is defined by a polygon, but cannot figure out how to only sample those portions of the raster within that region which are defined. The image below shows the raster layer and polygon I am working with:

I understand that it is possible to sample within the region and then use the raster layer as a mask to remove from the sampled points those which fall within the NA region of the layer, but, in doing this, the number of background points left over is less than that which was user-specified within the spsample function.

I've tried also converting the raster into a polygon using the rasterToPolygon function, finding the intersection of this polygon and the original, and sampling within only this intersection, but with the raster layers that I am working with being so large, the time required to complete this process is not feasible.

Are there other ways of completing this operation, which are reasonably fast in terms of computational time? Thanks in advance!