File Coverage

blib/lib/Math/PlanePath/KnightSpiral.pm
Criterion Covered Total %
statement 128 199 64.3
branch 39 76 51.3
condition 0 6 0.0
subroutine 22 27 81.4
pod 6 6 100.0
total 195 314 62.1


line stmt bran cond sub pod time code
1             # Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
2              
3             # This file is part of Math-PlanePath.
4             #
5             # Math-PlanePath is free software; you can redistribute it and/or modify
6             # it under the terms of the GNU General Public License as published by the
7             # Free Software Foundation; either version 3, or (at your option) any later
8             # version.
9             #
10             # Math-PlanePath is distributed in the hope that it will be useful, but
11             # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12             # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13             # for more details.
14             #
15             # You should have received a copy of the GNU General Public License along
16             # with Math-PlanePath. If not, see .
17              
18              
19             package Math::PlanePath::KnightSpiral;
20 1     1   1074 use 5.004;
  1         4  
21 1     1   5 use strict;
  1         2  
  1         39  
22             #use List::Util 'max';
23             *max = \&Math::PlanePath::_max;
24              
25 1     1   5 use vars '$VERSION', '@ISA';
  1         1  
  1         67  
26             $VERSION = 129;
27 1     1   790 use Math::PlanePath;
  1         3  
  1         64  
28             @ISA = ('Math::PlanePath');
29             *_sqrtint = \&Math::PlanePath::_sqrtint;
30              
31             use Math::PlanePath::Base::Generic
32 1     1   7 'round_nearest';
  1         2  
  1         42  
33              
34             # uncomment this to run the ### lines
35             #use Smart::Comments;
36              
37              
38 1     1   6 use constant xy_is_visited => 1;
  1         2  
  1         119  
39             sub x_negative_at_n {
40 0     0 1 0 my ($self) = @_;
41 0         0 return $self->n_start + 3;
42             }
43             sub y_negative_at_n {
44 0     0 1 0 my ($self) = @_;
45 0         0 return $self->n_start + 1;
46             }
47             sub _UNDOCUMENTED__dxdy_list_at_n {
48 0     0   0 my ($self) = @_;
49 0         0 return $self->n_start + 8;
50             }
51 1     1   6 use constant dx_minimum => -2;
  1         2  
  1         44  
52 1     1   5 use constant dx_maximum => 2;
  1         2  
  1         70  
53 1     1   7 use constant dy_minimum => -2;
  1         2  
  1         40  
54 1     1   6 use constant dy_maximum => 2;
  1         1  
  1         85  
55 1         77 use constant 1.02 _UNDOCUMENTED__dxdy_list => (2,1, # ENE
56             1,2, # NNE
57             -1,2, # NNW
58             -2,1, # WNW
59             -2,-1, # WSW
60             -1,-2, # SSW
61             1,-2, # SSE
62             2,-1, # ESE
63 1     1   7 );
  1         14  
64 1     1   7 use constant absdx_minimum => 1;
  1         2  
  1         56  
65 1     1   7 use constant absdy_minimum => 1;
  1         2  
  1         42  
66 1     1   5 use constant dsumxy_minimum => -3; # -2,-1
  1         2  
  1         52  
67 1     1   6 use constant dsumxy_maximum => 3; # +2,+1
  1         2  
  1         51  
68 1     1   6 use constant ddiffxy_minimum => -3;
  1         2  
  1         41  
69 1     1   5 use constant ddiffxy_maximum => 3;
  1         2  
  1         49  
70 1     1   7 use constant dir_minimum_dxdy => (2,1); # X=2,Y=1 angle
  1         2  
  1         47  
71 1     1   5 use constant dir_maximum_dxdy => (2,-1);
  1         2  
  1         1411  
72              
73             # Maybe ...
74             # use constant parameter_info_array =>
75             # [
76             # Math::PlanePath::Base::Generic::parameter_info_nstart1(),
77             # ];
78              
79             #------------------------------------------------------------------------------
80              
81             sub new {
82 3     3 1 581 my $self = shift->SUPER::new(@_);
83 3 50       13 if (! defined $self->{'n_start'}) {
84 3         17 $self->{'n_start'} = $self->default_n_start;
85             }
86 3         8 return $self;
87             }
88              
89             sub _odd {
90 985     985   1537 my ($n) = @_;
91             ### _odd(): $n
92 985         1652 $n -= 2*int($n/2);
93             ### rem: "$n"
94 985 50       1804 if ($n > 1) {
95 0         0 return 2-$n;
96             } else {
97 985         3197 return $n;
98             }
99             # return (int($n) % 2);
100             }
101              
102             sub n_to_xy {
103 1000     1000 1 66981 my ($self, $n) = @_;
104             #### KnightSpiral n_to_xy: $n
105              
106             # adjust to N=1 at origin X=0,Y=0
107 1000         2025 $n = $n - $self->{'n_start'} + 1;
108              
109 1000 100       2168 if ($n < 2) {
110 1 50       3 if ($n < 1) { return; }
  0         0  
111 1         2 $n--;
112 1         6 return (2*$n, -$n);
113             }
114              
115 999         2497 my $d = int ((7 + _sqrtint($n-1)) / 4);
116 999         1561 my $d1 = $d-1;
117 999         1446 my $outer = 2*$d1;
118 999         1318 my $inner = $outer - 1;
119 999         1417 my $p = 2*$d1;
120 999         1367 my $p1 = $p - 1;
121              
122             # use Smart::Comments;
123              
124             #### s frac: .25 * (7 + sqrt($n - 1))
125             #### $d
126             #### $d1
127             #### $inner
128             #### $outer
129             #### $p
130             #### $p1
131              
132 999         1567 $n -= $d*(16*$d - 56) + 50;
133             #### remainder: $n
134              
135             # one
136             #
137 999 100       1771 if ($n < $p1) {
138             #### right upwards, eg 2 ...
139 64         105 return (- _odd($n) + $outer,
140             2*$n - $inner);
141             }
142 935         1324 $n -= $p1;
143              
144 935 100       1680 if ($n < $p1) {
145             #### top leftwards, eg 3 ...
146 64         121 return (-2*$n + $inner,
147             _odd($n) + $inner);
148             }
149 871         1192 $n -= $p1;
150              
151 871 100       1710 if ($n < $p) {
152             #### left downwards ...
153 72         119 return ( - _odd($n) - $inner,
154             -2*$n + $outer);
155             }
156 799         1037 $n -= $p;
157              
158 799 100       1318 if ($n < $p1) {
159             #### bottom rightwards: $n
160 64         125 return (2*$n - $inner,
161             _odd($n) - $outer);
162             }
163 735         973 $n -= $p1;
164              
165              
166              
167             ### two ...
168             #
169 735 100       1187 if ($n < $p1) {
170             ### right upwards ...
171 64         123 return (_odd($n) + $inner,
172             2*$n - $inner);
173             }
174 671         926 $n -= $p1;
175              
176 671 100       1125 if ($n < $p) {
177             #### top leftwards
178 72         142 return (-2*$n + $outer,
179             _odd($n) + $inner);
180             }
181 599         762 $n -= $p;
182              
183 599 100       1026 if ($n < $p1) {
184             #### left downwards
185 64         112 return (_odd($n) - $outer,
186             -2*$n + $inner);
187             }
188 535         731 $n -= $p1;
189              
190 535 100       912 if ($n < $p1) {
191             #### bottom rightwards: $n
192 64         121 return (2*$n - $inner,
193             - _odd($n) - $inner);
194             }
195 471         602 $n -= $p1;
196              
197              
198              
199             ### three ...
200             #
201 471 100       809 if ($n < $p) {
202             ### right upwards, eg 12 ...
203 72         122 return (_odd($n) + $inner,
204             2*$n - $outer);
205             }
206 399         552 $n -= $p;
207              
208 399 100       662 if ($n < $p1) {
209             ### top leftwards, eg 14 ...
210 64         146 return (-2*$n + $inner,
211             - _odd($n) + $outer);
212             }
213 335         423 $n -= $p1;
214              
215 335 100       571 if ($n < $p1) {
216             ### left downwards, eg 15 ...
217 55         103 return (- _odd($n) - $inner,
218             -2*$n + $inner);
219             }
220 280         379 $n -= $p1;
221              
222 280 100       457 if ($n < $p1) {
223             ### bottom rightwards, eg 16 ...
224 49         99 return (2*$n - $outer,
225             - _odd($n) - $inner);
226             }
227 231         295 $n -= $p1;
228              
229              
230             ### four ...
231             #
232 231 100       394 if ($n <= 1) {
233             ### special 17 upwards ...
234 14         40 return ($n + $outer - 2,
235             2*$n - $outer);
236             }
237 217 100       366 if ($n < $p) {
238             ### right upwards ...
239 42         71 return (- _odd($n) + $outer,
240             2*$n - $outer);
241             }
242 175         242 $n -= $p;
243              
244 175 100       320 if ($n < $p) {
245             ### top leftwards, eg 19 ...
246 56         100 return (-2*$n + $outer,
247             - _odd($n) + $outer);
248             }
249 119         149 $n -= $p;
250              
251 119 100       205 if ($n < $p) {
252             ### left downwards, eg 21 ...
253 56         106 return (_odd($n) - $outer,
254             -2*$n + $outer);
255             }
256 63         80 $n -= $p;
257              
258 63 100       110 if ($n < $p) {
259             ### bottom rightwards, eg 23 ...
260 56         103 return (2*$n - $outer,
261             _odd($n) - $outer);
262             }
263 7         11 $n -= $p;
264              
265             ### step outwards, eg 25 ...
266 7         12 return (2*$n + $outer,
267             - _odd($n) - $outer);
268             }
269              
270              
271             # 157 92 113 134 155 90 111 132 153 88 109 130 151
272             # 114 135 156 91 112 133 154 89 110 131 152 87 108
273             # 93 158 73 32 45 58 71 30 43 56 69 150 129
274             # 136 115 46 59 72 31 44 57 70 29 42 107 86
275             # 159 94 33 74 21 4 9 14 19 68 55 128 149
276             # 116 137 60 47 10 15 20 3 8 41 28 85 106
277             # 95 160| 75 34 | 5 22 1 18 13 | 54 67| 148 127
278             # 138 117 48 61 16 11 24 7 2 27 40 105 84
279             # 161 96 35 76 23 6 17 12 25 66 53 126 147
280             # 118 139 62 49 78 37 64 51 80 39 26 83 104
281             # 97 162 77 36 63 50 79 38 65 52 81 146 125
282             # 140 119 164 99 142 121 166 101 144 123 168 103 82
283             # 163 98 141 120 165 100 143 122 167 102 145 124 169
284              
285             sub xy_to_n {
286 0     0 1   my ($self, $x, $y) = @_;
287 0           $x = round_nearest ($x);
288 0           $y = round_nearest ($y);
289 0 0 0       if ($x == 0 && $y == 0) {
290 0           return $self->{'n_start'};
291             }
292              
293 0           my $r = max(abs($x),abs($y));
294 0           my $d = int (($r+1)/2); # ring number, counting $x=1,2 as $d==1
295 0           $r -= (~$r & 1); # next lower odd number
296             ### $d
297             ### $r
298              
299 0 0         if ($y >= $r) {
300             ### top horizontal
301 0           my $xodd = ($x & 1);
302 0           $x = ($x - $xodd) / 2;
303             ### $xodd
304             ### $x
305              
306             # x odd
307             # [3,30,89,180,303] (16*$d**2 + -21*$d + 8)
308             # [14,57,132,239,378,549] (16*$d**2 + -5*$d + 3)
309             #
310             # [9,44,111,210,341,504] (16*$d**2 + -13*$d + 6)
311             # [20,71,154,269,416] (16*$d**2 + 3*$d + 1)
312              
313 0           my $n = 16*$d*$d - $x;
314 0 0         if (($x ^ $y ^ $d) & 1) {
315 0 0         if ($xodd) {
316 0           return $n -5*$d + 2 + $self->{'n_start'};
317             } else {
318 0           return $n -13*$d + 5 + $self->{'n_start'};
319             }
320             } else {
321 0 0         if ($xodd) {
322 0           return $n -21*$d + 7 + $self->{'n_start'};
323             } else {
324 0           return $n + 3*$d + $self->{'n_start'};
325             }
326             }
327             }
328              
329             # the lower left outer corner 25,81,169,etc belongs on the bottom
330             # horizontal, it's not an extension downwards from the right vertical
331             # (positions N=18,66,146,etc), hence $x!=-$y
332             #
333 0 0 0       if ($x >= $r && $x != -$y) {
334             ### right vertical
335 0           my $yodd = ($y & 1);
336 0           $y = ($y - $yodd) / 2;
337             ### $yodd
338             ### $y
339              
340             # y odd
341             # [3, 28,85, 174,295, 448,633] (16*$d**2 + -23*$d + 10)
342             # [8,41, 106,203, 332,493] (16*$d**2 + -15*$d + 7)
343             #
344             # y even
345             # [13,54,127,232,369,538] (16*$d**2 + -7*$d + 4)
346             # [18,67,148,261,406,583,792] (16*$d**2 + $d + 1)
347             #
348 0           my $n = 16*$d*$d + $y;
349 0 0         if (($x ^ $y ^ $d) & 1) {
350 0 0         if ($yodd) {
351 0           return $n -15*$d + 6 + $self->{'n_start'};
352             } else {
353 0           return $n -7*$d + 3 + $self->{'n_start'};
354             }
355             } else {
356 0 0         if ($yodd) {
357 0           return $n -23*$d + 9 + $self->{'n_start'};
358             } else {
359 0           return $n + $d + $self->{'n_start'};
360             }
361             }
362             }
363              
364 0 0         if ($y <= -$r) {
365             ### bottom horizontal
366 0           my $xodd = ($x & 1);
367 0           $x = ($x - $xodd) / 2;
368             ### $xodd
369             ### $x
370              
371             # x odd
372             # [7,38,101,196,323] (16*$d**2 + -17*$d + 8)
373             # [12,51,122,225,360,527] (16*$d**2 + -9*$d + 5)
374             #
375             # x even
376             # [17,64,143,254,397,572] (16*$d**2 + -1*$d + 2)
377             # [24,79,166,285,436] (16*$d**2 + 7*$d + 1)
378              
379 0           my $n = 16*$d*$d + $x;
380 0 0         if (($x ^ $y ^ $d) & 1) {
381 0 0         if ($xodd) {
382 0           return $n -9*$d + 4 + $self->{'n_start'};
383             } else {
384 0           return $n -1*$d + 1 + $self->{'n_start'};
385             }
386             } else {
387 0 0         if ($xodd) {
388 0           return $n -17*$d + 7 + $self->{'n_start'};
389             } else {
390 0           return $n + 7*$d + $self->{'n_start'};
391             }
392             }
393             }
394              
395 0 0         if ($x <= -$r) {
396             ### left vertical
397 0           my $yodd = ($y & 1);
398 0           $y = ($y - $yodd) / 2;
399             ### $yodd
400             ### $y
401              
402             # y odd
403             # [10,47,116,217,350,515] (16*$d**2 + -11*$d + 5)
404             # [15,60,137,246,387] (16*$d**2 + -3*$d + 2)
405             #
406             # y even
407             # [5,34,95,188,313] (16*$d**2 + -19*$d + 8)
408             # [22,75,160,277,426] (16*$d**2 + 5*$d + 1)
409             #
410 0           my $n = 16*$d*$d - $y;
411 0 0         if (($x ^ $y ^ $d) & 1) {
412 0 0         if ($yodd) {
413 0           return $n -11*$d + 4 + $self->{'n_start'};
414             } else {
415 0           return $n -19*$d + 7 + $self->{'n_start'};
416             }
417             } else {
418 0 0         if ($yodd) {
419 0           return $n -3*$d + 1 + $self->{'n_start'};
420             } else {
421 0           return $n + 5*$d + $self->{'n_start'};
422             }
423             }
424             }
425             }
426              
427             # not exact
428             sub rect_to_n_range {
429 0     0 1   my ($self, $x1,$y1, $x2,$y2) = @_;
430              
431 0           $x1 = round_nearest ($x1);
432 0           $y1 = round_nearest ($y1);
433 0           $x2 = round_nearest ($x2);
434 0           $y2 = round_nearest ($y2);
435              
436 0           my $x = max(abs($x1),abs($x2));
437 0           my $y = max(abs($y1),abs($y2));
438              
439 0           my $d = max(abs($x),abs($y));
440 0           $d += ($d & 1); # next even number if not already even
441             ### $x
442             ### $y
443             ### $d
444             ### is: $d*$d
445              
446 0           $d = 2*$d+1; # width of whole square
447             # ENHANCE-ME: find actual minimum if rect doesn't cover 0,0
448             return ($self->{'n_start'},
449 0           $self->{'n_start'} + $d*$d);
450             }
451              
452             1;
453             __END__