Encontrar persona pasar por punto

Question

Una persona empezar a moverse desde $(0,0)$ en un extraño patrón como sigue :

En un solo paso se moverá por una unidad en la actual dirección se está moviendo. Inicialmente la persona está en la posición $(0, 0)$.

1. En el principio, él va $1$ paso hacia el Este (es decir, En un solo paso, su $x$ coordinar aumentará por $1$ unidad).

2. A continuación, $2$ pasos hacia el Norte, (es decir, En un solo paso, su $y$ coordinar aumentará por $1$ unidad).

3. A continuación, $3$ pasos hacia el Oeste, (es decir, En un solo paso, su $x$ coordinar disminuirá por $1$ unidad).

4. A continuación, $4$ pasos hacia el Sur, (es decir, En un solo paso, su $y$ coordinar disminuirá por $1$ unidad).

   a continuación, $5$ pasos hacia el Este, y así sucesivamente.

Por lo tanto cada vez se vuelve $90$ grados en sentido anti horario, y se va a ir un paso más que antes.

La línea roja en el ejemplo se muestra la ruta trazada por el hombre.

Ahora la pregunta es que, dado un $(x,y)$ coordinar necesito saber si la persona va a ir a través de ese punto o no.

Ejemplo : Si coordenadas es$(3,3)$, entonces la respuesta es SÍ si su $(3,5)$ respuesta es NO.

Answer 1

Si $x\le0$, estamos en la línea % iff $\max{|x|,|y|}$es. Si $x\ge0$, estamos en la roja línea iff $\max{|x|,|y-1|}$ es impar.

Answer 2

Dado el primer punto de la secuencia es $(0,0)$, podemos describir la secuencia de la siguiente manera - $(x,y)_n = (0 + 1 + 0 - 3 + 0 + 5 + 0 - ...,0 + 0 + 2 + 0 - 4 + 0 + 6) $ (n términos en ambas series)

Mediante la agrupación de los términos de forma adecuada, se puede ver que

si $ n=4m$, $(x,y)_{4m} = (-2m, 2m)$

si $ n=4m + 1$, $(x,y)_{4m+1} = (-2m, -2m)$

si $ n=4m +2$, $(x,y)_{4m+2} = (2m + 1, -2m)$

si $ n=4m +3$, $(x,y)_{4m+3} = (2m + 1, 2m + 2)$

También se puede ver que la distancia desde el origen es no decreciente. Por lo tanto, un algoritmo para comprobar si el punto (h, k) pertenece a esta secuencia es para calcular estas cuatro secuencias de hasta $x^2 + y^2 > h^2 + k^2$, comparando el punto de cada iteración.

Answer 3

Creo que puedes probar lo siguiente por inducción.

Para$n\in\mathbb N$, la persona gira en$$(2n-1,-2n+2)\ \underrightarrow{y:4n-2}\ (2n-1,2n)\ \underrightarrow{x:-4n+1}\ (-2n,2n)$$$$ \ \ underrightarrow {y: -4n} \ (-2n, -2n) \ \ underrightarrow {x: 4n +1} \ (2 (n +1) -1, -2 (n +1) +2). $$

A partir de esto, encontrará la condición de que la persona atravesará un punto determinado.

Answer 4

Me puse a buscar en varios segmentos de recorrido y vio algunos patrones interesantes (sin pruebas):

$$\begin{array} {c|c|c} \text{Segment when}&\text{Other variable start}& \text{Other variable end}\\ y=0& x: 0&1\\ x=1&y:0&2\\ y=2&x:1&-2\\ x=-2&y:2&-2\\ y=-2& x: -2&3\\ x=3&y:-2&4\\ y=4&x:3&-4\\ x=-4&y:4&-4\\ y=-4&x:-4&5\\ x=5&y:-4&6 \end{array}$$ Basándose en estas observaciones, parece (y creo que debe ser comprobable) que los puntos de $(x,y)$ afectados por este proceso de satisfacer (al menos) una de las siguientes cuatro condiciones:

(i) $x$ impar y positivo; $y\in[-x+1,x+1]$

(ii) $x$ incluso negativo; $y\in [-x,x]$

(iii) $y$, y el valor no positivo; $x\in [y,-y+1]$

(iv) $y$ aun y positivo; $x\in [-y,y-1]$

Por ejemplo, $(17,-11)$ cae en caso de que (i). Desde $-11\in[-16,18]$, este punto sería en el camino.

Answer 5

Observe que todos los puntos donde la persona cambia de dirección de oriente a norte a lo largo de la línea dada por $x + y = 1$:

Del mismo modo cada turno de norte a oeste, a lo largo de la línea donde se $y - x = 1$, cada vez, de oeste a sur a lo largo de la línea donde se $x + y = 0$, y cada vez desde el sur hacia el este a lo largo de la línea donde se $y - x = 0$.

Por otra parte, si un giro hacia una dirección dada (por ejemplo, para el norte) se produce en las coordenadas $(x,y)$, entonces la próxima vez en que dirección va a ocurrir en las coordenadas $(x \pm 2,y \pm 2)$, donde el signo de $\pm$ en cada caso se determina por la dirección de la vuelta.

Podemos asignar a cada punto con coordenadas enteras $(x,y)$ a uno (o dos) de las cuatro regiones del plano de la etiqueta a, B, C o D en el diagrama de arriba, que están delimitadas por las cuatro medias líneas que se muestran en la luz azul.

• R: Si $|y - 1| \le x$, el punto es tocado si y sólo si $x$ es impar.
• B: Si $|x + \frac12| \le y - \frac12$, el punto es tocado si y sólo si $y$ es incluso.
• C: Si $|y| \le -x$, el punto es tocado si y sólo si $x$ es incluso.
• D: Si $|x - \frac12| \le \frac12 - y$, entonces el punto es tocado si y sólo si $y$ es incluso.

Uno puede demostrar que todas estas declaraciones matemáticamente, pero se los dejo como ejercicio, al menos por ahora.