Given a random sample of points from some unknown distribution, we propose a new data-driven method for estimating its probability support $S$. Under the mild assumption that $S$ is $r$-convex, the smallest $r$-convex set which contains the sample points is the natural estimator. The main problem for using this estimator in practice is that $r$ is an unknown geometric characteristic of the set $S$. A stochastic algorithm is proposed for selecting it from the data under the hypothesis that the sample is uniformly generated. The new data-driven reconstruction of $S$ is able to achieve the same convergence rates as the convex hull for estimating convex sets, but under a much more flexible smoothness shape condition. The practical performance of the estimator is illustrated through a real data example and a simulation study.