Skip to main content
formatting
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Generating Random Curvesrandom curves with Fixed Lengthfixed length and Endpoint Distanceendpoint distance

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

editEdit

**Here are the promised details:**

Here are the promised details:

theThe algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$); 

<br/ > Some remarks:Some remarks:

Generating Random Curves with Fixed Length and Endpoint Distance

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

edit

**Here are the promised details:**

the algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$);

<br/ > Some remarks:

Generating random curves with fixed length and endpoint distance

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

Edit

Here are the promised details:

The algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$); 

Some remarks:

described an algorithm that generates such curves in full generality
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

**Here are the promised details:**

the algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

Otherwise the length-stock is split up and assigned to two newly generated line-segments and the original problem of finding a curve of fixed length with endpoints at fixed has to be solved recursively for both segments separately.

Pseudo code:

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$);

<br/ > Some remarks:

the pseudo code is aimed at full generality and also covers "degenerate" cases; those need to be ruled out by further checks. One such case is the collinearity of $p$, $\ q$ and $r$ with positive $\Delta\ell$.

Selecting $r$ from the mentioned elliptical regions with foci $p$ and $q$ can also be interpreted as chosing one of the intersection points of a circle around $p$ and $q$. That covers the algorithm of Matt F. as a special case.

The followup challenge is now to control further properties of the curve via taylored rules for selecting $r$ and distributing $\Delta\ell$ on each recursion level.
Or, play with the options to discover interesting curves and fractals.


**Here are the promised details:**

the algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

Otherwise the length-stock is split up and assigned to two newly generated line-segments and the original problem of finding a curve of fixed length with endpoints at fixed has to be solved recursively for both segments separately.

Pseudo code:

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$);

<br/ > Some remarks:

the pseudo code is aimed at full generality and also covers "degenerate" cases; those need to be ruled out by further checks. One such case is the collinearity of $p$, $\ q$ and $r$ with positive $\Delta\ell$.

Selecting $r$ from the mentioned elliptical regions with foci $p$ and $q$ can also be interpreted as chosing one of the intersection points of a circle around $p$ and $q$. That covers the algorithm of Matt F. as a special case.

The followup challenge is now to control further properties of the curve via taylored rules for selecting $r$ and distributing $\Delta\ell$ on each recursion level.
Or, play with the options to discover interesting curves and fractals.

clarified questions from the comments
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given?

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

edit

In view of the comments and the answer of Bjørn Kjos-Hanssen, I see the need for some clarification:

  • By random curve of unit length connecting $(0,0)$ and $(\alpha,0)$, I mean a random sample from the space of all such curves; that means, that the algorithm should be capable to approximate every such curve to arbitrary precision with a finite number of steps.
    So "random" is not restricted to the appearance of the curve.

  • Being able to generate Brownian Bridges is not sufficient, because I would like the algorithm to be able to generate curves (ideally in any $\mathbb{R}^n$) and not only functions.

So my apologies for not being precise enough.

I have used the formulation "are algorithms already known", because I have found one, that seems to be able to produce all those curves.

I will provide details in a later edit.

Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given?

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given?

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

edit

In view of the comments and the answer of Bjørn Kjos-Hanssen, I see the need for some clarification:

  • By random curve of unit length connecting $(0,0)$ and $(\alpha,0)$, I mean a random sample from the space of all such curves; that means, that the algorithm should be capable to approximate every such curve to arbitrary precision with a finite number of steps.
    So "random" is not restricted to the appearance of the curve.

  • Being able to generate Brownian Bridges is not sufficient, because I would like the algorithm to be able to generate curves (ideally in any $\mathbb{R}^n$) and not only functions.

So my apologies for not being precise enough.

I have used the formulation "are algorithms already known", because I have found one, that seems to be able to produce all those curves.

I will provide details in a later edit.

Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76
Loading