¿Cómo puedo generar las curvas "al azar"?

Question

En la programación del juego (mi profesión) a menudo es necesario para generar todo tipo de cosas al azar, incluyendo curvas aleatorias (por ejemplo, para hacer un procedimiento de la isla o de un agente de seguir algún camino).

Para unidimensional de las cosas, por lo general, utilizar algunos generador de números aleatorios que genera dicen flota (que en realidad son números racionales) en un rango y que es lo suficientemente bueno como una aproximación para la mayoría de propósitos. (Aunque no podemos generar reales los números reales dentro de un rango de manera uniforme, se puede obtener un buen sentido de la misma con los racionales que generamos.)

Cuando se trata de 2D cosas, sin embargo, las cosas son muy turbias. Por ejemplo, supongamos que deseamos generar curvas de manera uniforme entre dos puntos (es decir, todas las curvas delimitada en una caja, y decir, requisitos adicionales, tales como que las curvas son diferenciables).

La manera en que solemos hacer es generar los parámetros aleatorios para algunos tipos específicos de la curva (por ejemplo, una curva de Bézier, pero esto no es (AFAI puede ver) uniforme en los requisitos originales - es decir, algunas de las curvas que se ajustan a la ley, será más probable que otros.

Esto es incluso una sensata pregunta?

Y si es así, ¿hay una manera de generar curvas (para una aproximación decente), de modo que ellos son uniformes dentro de los parámetros? (delimitada y suave)?

"Se siente" como hay demasiadas curvas; es estrictamente cierto con los números reales también... pero no tenemos que racionales pueden ser lo suficientemente cerca para fines prácticos; pero con 2D cosas parece menos claro que cualquier posible real de la curva es "lo suficientemente cerca" a un "racionales de la curva".

Así que supongo que la principal pregunta es... si tenemos un conjunto de "todas las curvas", si podemos encontrar una manera de generar otra serie de aproximaciones, de manera que cada "real" de la curva está lo suficientemente cerca de nuestra aproximación.

O: es que hay una asignación de "aproximaciones reales" a "aproximaciones de continua, diferenciable, delimitada curvas entre dos puntos".... (que conserva la homogeneidad, al menos intuitivamente)?

O: hay una noción de la distribución de la (limitada diferencial), las curvas? (Y la manera de escoger los elementos de la misma).

Edit: estoy más interesado en las posibilidades teóricas. Sé que un MONTÓN de maneras de generar en las curvas... soy particular interesado en la generación de curvas sin algún tipo de sesgo, y si esto tiene algún sentido para querer.

Edit: @pjs36 señaló la curva puede ser arbitraria de largo. No me importa restricciones adicionales para evitar curvas patológicas. Restricciones como "no más de $x$", o no se auto-cruce.

Answer 1

(1) Una versión de su pregunta fue explorado aquí: "la Generación de Curvas Aleatorias con Longitud Fija y el Extremo de la Distancia." Yo diría que no ha respondido de manera definitiva.

---

         

---

(2) Usted puede mirar en este artículo reciente: Igor Rivin, "al Azar del espacio y de las curvas planas," arXiv:1607.05239de 2016. Se basa en el azar trigonométrica de la serie: "nuestra clase es precisamente la clase de azar domar nudos."

(3) en Un reciente trabajo teórico: Kemppainen, Antti, y Stanislav Smirnov. "Curvas aleatorias, límites de escala y de Loewner evoluciones." Los Anales de la Probabilidad 45.2 (2017): 698-779. "[W]e muestran que un débil estimación sobre la probabilidad de un anillo de cruzar implica que una curva aleatoria derivadas a partir de una mecánica estadística modelo de escala de los límites y de los que serán bien descrito por Loewner evoluciones con el azar de la conducción de las fuerzas."

---

         
          ^{(La imagen de aquí.)}

---

Answer 2

La respuesta depende de cómo se defina 'uniforme-ness'.

Es una manera de entender como un límite adecuado del uniforme discreta contraparte. Por ejemplo, considere la posibilidad de distribuciones uniformes en $\mathbb{R}$. Sabemos que aparecen como limitar el objeto de uniforme discreta distribuciones.

Idea Similar se aplica a las rutas. Deje $\delta > 0$ y discretizar el $d$-dimensional espacio Euclidiano $\mathbb{R}^d$ por el entramado $(\delta \mathbb{Z})^d = \{(\delta k_1, \cdots, \delta k_d) : k_1, \cdots, k_d \in \mathbb{Z} \}$ del tamaño de la malla $\delta > 0$. Luego de considerar todos el camino de la longitud de la $n$, empezando en el origen y que permite volver atrás. Ya tenemos $2d$ opciones para cada paso, hay $(2d)^n$ rutas de acceso. Respecto de ellos como poligonal rutas en $\mathbb{R}^d$ por interpolación lineal y considerar la posibilidad de una distribución uniforme sobre ellos. Bajo la escala adecuada límite, la distribución uniforme converge a lo que nosotros llamamos un movimiento Browniano (BM). Precisamente en este sentido BM puede ser pensado como una manera uniforme dibujado camino continuo de partida en $0$. (También puede ser demostrado que el esquema de discretización no importa mucho, en el sentido de que esta limitación de precedure es un camino análogo del teorema del límite central. BM describe curvas aleatorias cuando las velocidades en diferentes son casi correlacionadas.)

El BM es un bloque de construcción básico para la más complicada de los objetos de intercambio esquema similar. Por ejemplo, ahora fijar un $x$$\mathbb{R}^d$, discretizar ellos para obtener los puntos de $x_\delta \in (\delta \mathbb{Z})^d$ y que nos permiten contar todos los caminos de longitud $n$$(\delta \mathbb{Z})^d$$0$$x_\delta$. Siguiendo la misma idea, como antes, la distribución uniforme sobre dichos caminos convergen (en escala) a lo que se llama puente Browniano. De manera diferente, puente Browniano puede ser entendido como el BM acondicionado para visitar el punto de $y$ tiempo $t$. Delimitación de tales curvas dentro de una región puede ser hecho de una manera similar.

Pero aquí hay una mala noticia: Desde la 'velocidad' de tiempo diferentes no es determinista, no es difícil imaginar que Browniano caminos sería bastante irregular. De hecho, se puede demostrar que Browniano caminos son diferenciable, con una probabilidad de $1$. Dicho esto, se puede observar las rutas de poseer una mejor regularidad sólo cuando se imponen los prejuicios.

Answer 3

Una manera de definir la "uniformidad" de más de conjuntos infinitos es como hacemos para finito de intervalos de $($decir, $[0,1])$, o el disco en $\mathbb R^2$. La idea básica es la siguiente: supongamos que tenemos algunas conjunto infinito $S$ $\mu$medible con un límite de medida. La variable aleatoria $X$ $S$ se dice $(\mu)$- , uniformemente distribuida, si y sólo si para todo medible $A\subset S$ hemos

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

En otras palabras, la probabilidad de que $X$ tierras en $A$ es proporcional al tamaño de $A$ en relación con el $S$. Entonces, el problema más o menos se reduce a la elección de una adecuada subconjunto $S$ de algún espacio adecuado de las curvas de $\mathcal C$, y una razonable medida de $\mu$ $\mathcal C$ que $\mu(S)<\infty$.

Answer 4

Una idea: podría %#% puntos de #% uniformemente de un rectángulo, arreglar los puntos mediante el aumento de $n$ coordenadas y montar una spline en los puntos.