1

Topic: Algorithm of generation of one-dimensional patterns

Colleagues, and whether exist methods for the decision of the following task. There is some area of space. It is broken into cells (the nearest analogy the image broken into pixels). There is some curve f (x, y) = (x (t), y (t)) if it transits through a cell the cell is considered painted over. It is necessary to pick up such curve that it painted over the maximum number of cells but satisfied to following conditions 1. Absence of self-intersections. The curve should not transit through the same cell twice 2. Sufficient smoothness (max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T) 3. Uniqueness of a pattern - in any area in the size MxN the pattern should be unique. (I.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat.

2

Re: Algorithm of generation of one-dimensional patterns

Hello, denisko, you wrote: D> Colleagues, and whether exist methods for the decision of the following task. D> there is some area of space. It is broken into cells (the nearest analogy the image broken into pixels). There is some curve f (x, y) = (x (t), y (t)) if it transits through a cell the cell is considered painted over. It is necessary to pick up such curve that it painted over the maximum number of cells but satisfied to the following conditions D> 1. Absence of self-intersections. The curve should not transit through the same cell twice D> 2. Sufficient smoothness (max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T) D> 3. Uniqueness of a pattern - in any area in the size MxN the pattern should be unique. (I.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat. For rectangle N*M Y = M/2*cos (pi*X) * (M/2-1/N*X)

3

Re: Algorithm of generation of one-dimensional patterns

Hello, denisko, you wrote: D> Colleagues, and whether exist methods for the decision of the following task. D> there is some area of space. It is broken into cells (the nearest analogy the image broken into pixels). There is some curve f (x, y) = (x (t), y (t)) if it transits through a cell the cell is considered painted over. It is necessary to pick up such curve that it painted over the maximum number of cells but satisfied to the following conditions D> 0. There is some area of space. Areas happen very different, as well as spaces D> 1. Absence of self-intersections. The curve should not transit through the same cell twice D> 2. Sufficient smoothness (max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T) Strange at you a smoothness condition: restriction on the maximum speed of driving on a curve x (t) =a * | t^3 | y (t) =a*t^3 a <sqrt (T) / (3*sqrt (2)) is simple before a fracture is braked, and we go further. D> 3. Uniqueness of a pattern - in any area in the size MxN the pattern should be unique. A fractal it is necessary? D> (i.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat. It as? There are here such curves Peano Mortona Hilbert Serpinsky Moore's scanning

4

Re: Algorithm of generation of one-dimensional patterns

B> For rectangle N*M B> Y = M/2*cos (pi*X) * (M/2-1/N*X) the Size the day off essentially is more M* N here Y takes off for limits very quickly + as far as I understand is not obvious (and maximality and uniqueness is more likely obvious not).

5

Re: Algorithm of generation of one-dimensional patterns

Hello, kov_serg, you wrote: _> Hello, denisko, you wrote: D>> Colleagues, and whether exist methods for the decision of the following task. D>> there is some area of space. It is broken into cells (the nearest analogy the image broken into pixels). There is some curve f (x, y) = (x (t), y (t)) if it transits through a cell the cell is considered painted over. It is necessary to pick up such curve that it painted over the maximum number of cells but satisfied to the following conditions D>> 0. There is some area of space. _> areas happen very different, as well as spaces Area single-connected square-topped if it helps you. _> it is simple before a fracture it is braked, and we go further. The main thing that ruptures was not, i.e. there was no jump from a point on points D>> 3. Uniqueness of a pattern - in any area in the size MxN the pattern should be unique. _> a fractal it is necessary? Most likely  since uniqueness and maximality of filling is unobvious. D>> (i.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat. _> it as? for ((x, y) in rect (x1, y1, M, N)) B + = I (x, y) <<((y-y1) * M + (x-x1)); B - unique.

6

Re: Algorithm of generation of one-dimensional patterns

Hello, denisko, you wrote: D>>> (i.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat. _>> it as? D> for ((x, y) in rect (x1, y1, M, N)) D> B + = I (x, y) <<((y-y1) * M + (x-x1)); D> B - unique. A normal snake? Let x1=y1=0 for brevity>-------\/-------/\-------\<-------/0 1... (w-2) (w-1) (2w-1) (2w-2)... (w+1) (w) (2w) (2w+1)... (3w-2) (3w-1) (4w-1) (4w-2)... (3w+1) (3w) (4w) (4w+1)... (5w-2) (5w-1)................................ And so h lines void getXY (int &x,int &y,int f, int w, int h) {y = f / w; x = y&1? w-1-f%w: f%w;} int getF (int x, int y, int w, int h) {return y*w + (y&1? w-1-x: x);} a curve x (t) = 0.5 + (w-1) * (1-cos (pi*t))/2 y (t) = t

7

Re: Algorithm of generation of one-dimensional patterns

For satisfaction of a condition 2 max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T it is enough to make so 0 <k <sqrt (T)/sqrt (1 + (w-1) ^2*pi^2/4) y (t) =k*t x (t) =0.5 + (w-1) * (1-cos (pi*k*t))/2

8

Re: Algorithm of generation of one-dimensional patterns

D> the Curve should not transit through the same cell twice Not clearly that it means. It not absolutely self-intersection.

9

Re: Algorithm of generation of one-dimensional patterns

Hello, kov_serg, you wrote: Also what not so 0 <k <sqrt (T)/sqrt (1 + (w-1) ^2*pi^2/4) y (t) =k*t x (t) =0.5 + (w-1) * (1-cos (pi*k*t))/2> to pick up such curve that it painted over the maximum number of cells +> 1. Absence of self-intersections. The curve should not transit through the same cell twice +> 2. Sufficient smoothness (max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T) +> 3. Uniqueness of a pattern - in any area in the size MxN the pattern should be unique. (I.e. if to linearize this area and to transform into binary number) that numbers on all image will not repeat.> for ((x, y) in rect (x1, y1, M, N))> B + = I (x, y) <<((y-y1) * M + (x-x1));> B - unique. + that asked that and received In what discontent?

10

Re: Algorithm of generation of one-dimensional patterns

Hello, kov_serg, you wrote: _> + Is not present, because the image size essentially is more than M*N, uniqueness should be in each window M*N _> That asked that and received In what discontent? That you generate too many messages, without trying to understand statements of the problem.

11

Re: Algorithm of generation of one-dimensional patterns

Hello, denisko, you wrote: D> Hello, kov_serg, you wrote: _>> + D> Is not present, because the image size essentially is more than M*N, uniqueness should be in each window M*N Let image MI, NI that the snake creeps any windows M*N in it MI, NI _>> That asked that and received In what discontent? D> that you generate too many messages, without trying to understand statements of the problem. So formulate a statement of the problem distinctly.

12

Re: Algorithm of generation of one-dimensional patterns

Hello, Kodt, you wrote: Hello, denisko, you wrote: D>> 2. Sufficient smoothness (max_t (dx (t)/dt) ^2 + (dy (t)/dy) ^2 <T) I.e. the curvature radius should not be less R = sqrt (T) At it restriction on the maximum speed of driving on a curve, instead of on curvature radius. That is always it would be possible to replace t on k*t what to satisfy to restriction on speed. The curvature radius looks so: 1/R (t) = | x '*y "- y '*x" | / (x ' ^2 + y ' ^2) ^3/2