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.


(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.”



Fig.1: arXiv version abstract.

Source : Link , Question Author : Herman Tulleken , Answer Author : Joseph O’Rourke

Leave a Comment