How can I generate "random" curves?

In game programming (my profession) it is often necessary to generate all kinds of random things, including random curves (for example, to make a procedural island or for an agent to follow some path).

For one dimensional things, we usually use some random generator that generates say floats (which are really rational numbers) in some range and that is good enough as an approximation for most purposes. (Even though we cannot generate actual real numbers within a range uniformly, we can get a good sense of it with the rationals that we DO generate.)

When it comes to 2D things, though, things are very murky. For example, suppose I want to generate curves uniformly between two points (say, all curves bounded in a box, and say, additional requirements such as that the curves are differentiable).

The way we usually do it is to generate random parameters for some specific type of curve - say a Bezier curve, but this is not (AFAI can see) uniform in the original requirements - i.e. some curves that fit the bill will be more likely than others.

Is this even a sensible question to ask?

And if so, is there a way to generate curves (to a decent approximation) so that they are uniform within the parameters? (bounded and smooth)?

It "feels" like there are too many curves; it is strictly true with real numbers too... but there we have that rationals can be close enough for practical purposes; but with 2D things it seems less clear that any possible real curve is "close enough" to a "rational curve".

So I guess the main question is... if we have a set of "all curves", whether we can find a way to generate another set of approximations so that each "real" curve is close enough to our approximation.

Or: is there a mapping from "approximations to reals" to "approximations of continuous, differentiable, bounded curves between two points".... (that preserves uniformity, at least intuitively)?

Or: is there a notion of distribution of (bounded differential) curves? (And way to pick items from it).

Edit: I am more interested in the theoretical possibilities. I know LOTS of ways to generate curves... I am particular interested in generating curves without some kind of bias, and whether this even makes sense to want.

Edit: @pjs36 pointed out the curve may be arbitrary long. I don't mind additional restrictions to prevent pathological curves. Restrictions like "not longer than $x$", or not self-crossing.

Solution 1:

(1) A version of your question was explored here: "Generating Random Curves with Fixed Length and Endpoint Distance." I'd say not definitively answered.

(2) You might look at this recent paper: Igor Rivin, "Random space and plane curves," arXiv:1607.05239, 2016. It relies on random trigonometric series: "our class is precisely the class of random tame knots."

(3) A recent theoretical paper: Kemppainen, Antti, and Stanislav Smirnov. "Random curves, scaling limits and Loewner evolutions." The Annals of Probability 45.2 (2017): 698-779. "[W]e show that a weak estimate on the probability of an annulus crossing implies that a random curve arising from a statistical mechanics model will have scaling limits and those will be well-described by Loewner evolutions with random driving forces."

Solution 2:

The answer clearly depends on how you define 'uniform-ness'.

One way is to understand them as an appropriate limit of discrete uniform counterpart. For example, consider uniform distributions on $\mathbb{R}$. We know that they appear as limiting object of discrete uniform distributions.

Similar idea applies to paths. Let $\delta > 0$ and discretize the $d$-dimensional Euclidean space $\mathbb{R}^d$ by the lattice $(\delta \mathbb{Z})^d = \{(\delta k_1, \cdots, \delta k_d) : k_1, \cdots, k_d \in \mathbb{Z} \}$ of mesh size $\delta > 0$. Then consider all the path of length $n$ starting at the origin and allowing backtracking. Since we have $2d$ choices for each step, there are $(2d)^n$ such paths. Regard them as polygonal paths in $\mathbb{R}^d$ by linear interpolation and consider a uniform distribution over them. Under a proper scaling limit, such uniform distribution converges to what we call a Brownian motion (BM). Precisely in this sense BM can be thought as a uniformly drawn continuous path starting at $0$. (It can also be proved that discretization scheme does not matter too much, in the sense that this limiting precedure is a path-analogue of the central limit theorem. BM describes random curves where speeds at different time are almost uncorrelated.)

BM is a basic building block for more complicated objects sharing similar scheme. For instance, now fix a $x$ in $\mathbb{R}^d$, discretize them to obtain points $x_\delta \in (\delta \mathbb{Z})^d$ and let us count all paths of length $n$ in $(\delta \mathbb{Z})^d$ from $0$ to $x_\delta$. Following the same idea as before, the uniform distribution over such paths converge (under appropriate scaling) to what is called Brownian bridge. Differently, Brownian bridge can be understood as BM conditioned to visit the point $y$ at time $t$. Bounding such curves within a region can be done in a similar way.

But here is a bad news: Since the 'velocity' at different time is not deterministically related, it is not hard to imagine that Brownian paths would look quite irregular. Indeed, it can be shown that Brownian paths are nowhere differentiable with probability $1$. That being said, you can observe paths possessing better regularity only when you impose bias.

Solution 3:

One way to define 'uniformity' over infinite sets is like we do for finite intervals $($say, $[0,1])$, or the disk in $\mathbb R^2$. The basic idea is as follows: suppose we have some infinite set $S$ that is $\mu$-measurable with finite measure. The random variable $X$ on $S$ is said to be $(\mu)$-uniformly distributed if and only if for all measurable $A\subset S$ we have

$$\mathbb P(X \in A)=\frac{\mu(A)}{\mu(S)}.$$

In other words, the probability that $X$ lands on $A$ is proportional to how large $A$ is, relative to $S$. Then, the problem more or less boils down to choosing an adequate subset $S$ of some suitable space of curves $\mathcal C$, and some sensible measure $\mu$ on $\mathcal C$ for which $\mu(S)<\infty$.

Solution 4:

An idea: You could pick $n$ points uniformly from a rectangle, arrange the points by increasing $x$ coordinates, and fit a spline on those points.