Sampling the inside of a curve Suppose I have a set of points $S$ in the plane, which defines a curve in a discretized fashion. This could be $3\cdot 10^3$ points on the unit circle:

But also could be $3\cdot 10^3$ points describing any closed shape, for example:

My question is as follows: How do I sample points from the inside of these shapes ? I'd like to randomly fill the shape's inside.
 A: If you have a very simple shape, like a disk, or an annulus or a square minus an inscribed disk, you can directly generate samples. For anything more complicated, and indeed the general case, rejection sampling is the way to go: pick $x$ and $y$ uniformly distributed on your canvas and keep $(x,y)$ if it is inside your shape, rejecting it otherwise.
So the key issue is how to efficiently decide whether your sample point is inside or outside a given shape.
As whuber notes, a cloud of points does not make up a shape. Perhaps you are thinking of the convex hull of a cloud of points, but your second example is not convex, so this is probably not what you want to do. So I'll assume you have an ordered list of $n$ points $(p_0, \dots, p_n=p_0)$ that make up a simple closed curve; that is, the connecting segments $p_ip_{i+1}$ and $p_jp_{j+1}$ do not intersect for $i\neq j$, and $p_i\neq p_j$ for all $i,j$, unless $i,j\in\{0,n\}$. This defines an interior and an exterior.
First off, you can do some very simple checks, like calculating the minimum bounding box (just take the minimal and maximal $x$ and $y$ values of your points). If your sampled point is outside that bounding box, you can immediately reject it. (Or simpler: generate new candidates in the bounding box directly.)
Next, perhaps you can inscribe a simple object (or multiple ones), like circles or rectangles, where you can easily test inclusion. If a candidate point is in one of the inscribed objects, it is also in the larger shape.
Finally, you need to test whether your new point $p$ is inside the general shape defined by $(p_0, \dots, p_n=p_0)$, i.e., a polygon. This is the point in polygon problem, which is standard fare in computational geometry. The Wikipedia page offers a number of standard algorithms, and you should be able to find something in computational geometry textbooks, too. Finally, there are definitely implementations in standard libraries. For instance, the sp package for R has an appropriately-named function point.in.polygon(). You can even use such algorithms for points in polygons with holes.
