35
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ "without some kind of bias" would probably yield curves that could get arbitrarily long, looping across themselves. At any rate, it's an interesting question. $\endgroup$
    – pjs36
    Commented Jan 4, 2018 at 4:49
  • $\begingroup$ That is kind of what I imagine too. But if we add another restriction (shorter than $x$?) $\endgroup$ Commented Jan 4, 2018 at 4:51
  • 7
    $\begingroup$ There is no general notion of 'uniform' measure on an infinite set. Especially on a space of curves, which is really big! You should look into the formalism required to define Brownian motion (BM), which is a random continuous function $[0,\infty) \to \mathbb{R}$. (Then a 2D BM is just a vector of two independent 1D BM's.) I don't know of any well studied stochastic processes that have smooth (or even differentiable) sample paths -- BM has continuous, but everywhere non-differentiable paths (though probably someone has thought about this). I guess some smoothing could be used... $\endgroup$
    – J Richey
    Commented Jan 4, 2018 at 5:13
  • $\begingroup$ There is no notion of this... because it's impossible? (You edited your comment while I was typing :P but my question stands.) $\endgroup$ Commented Jan 4, 2018 at 5:18
  • $\begingroup$ I should also add that from a probability point of view, it's easy to condition on Brownian motion to satisfy some of the requirements you are talking about. For example, one can write down the distribution of a BM conditioned to stay within an interval. $\endgroup$
    – J Richey
    Commented Jan 4, 2018 at 5:20

5 Answers 5

15
$\begingroup$

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


          ScalingLimits
          Fig.1: arXiv version abstract.


$\endgroup$
11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks! And is there a way to also fix the end point? (Because BM as such follows my intuition about motion from a point... but not from one point to another.) $\endgroup$ Commented Jan 4, 2018 at 5:41
  • 1
    $\begingroup$ @HermanTulleken, Brownian bridge (BB) does the job, as explained in my answer. It is sort of BM conditioned to end at a given point at a given time. Here is one way of realizing BB: Let $(W_t)$ be a $d$-dim BM starting at $0$. If $x \in \mathbb{R}^d$ and $T> 0$ is a fixed time, then $B_t = W_t + (t/T)(x-W_T)$ realizes the BB joining $0$ to $x$ over the time interval $[0, T]$. $\endgroup$ Commented Jan 4, 2018 at 5:50
  • $\begingroup$ Sorry I missed that last bit! $\endgroup$ Commented Jan 4, 2018 at 5:52
  • $\begingroup$ (I will reflect a bit on your answer) $\endgroup$ Commented Jan 4, 2018 at 6:10
8
$\begingroup$

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$.

$\endgroup$
1
  • 3
    $\begingroup$ This is the right answer. Of course, the difficulty lies in defining a reasonable measure on the set of all (differentiable/smooth/analytic) curves between two points. $\endgroup$
    – Carmeister
    Commented Jan 4, 2018 at 6:47
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This is precisely the type of thing we DO do (we have LOTS of tricks), but such a curve is not "uniform" (for example, if we arrange points by Y we would get different typical curves.) $\endgroup$ Commented Jan 4, 2018 at 4:39
  • $\begingroup$ (But if I am missing something - please elaborate!) $\endgroup$ Commented Jan 4, 2018 at 4:50
1
$\begingroup$

If You want to draw irregular closed shape (e.g. asteroid or island), then the simplest way is to use polar coordinates - rotate the polar axis using random-size steps from 0..360, change the polar radius also using random steps, both in certain limits min..max -

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .