Generating random samples from a 2D space matching the probability density function estimated from a discrete set of data

I have a set of around 12k points in the {a,e} space that looks as in the figure below (yes, there are 12 thousand points, but most of them are concentrated in the bottom left). I have to extract around 600k random points from this space, and I want the resulting set to match the hypothetical 2D probability density function that has led to the initial set of 12k points. ksdensity can estimate the 2D pdf, and I can extract random samples accordingly just as this thread suggests, using randsample, but the problem is that the set of samples will be limited to the discrete points in which I meshed the domain. I could work with, for instance, a 5000x5000 mesh, but this is quite CPU-consuming and I think it leads to considerable overfitting. I wonder if there is any kind of analytical alternative that makes it easier and allows to work in the continuum. This thread suggests something but tbh I don't think it is well justified. Thanks in advance!