lib/PDL/ImageND.pd

filter: Statementstmt 85.4% 94 / 110 Branchbran 54.1% 26 / 48 Conditioncond 33.3% 1 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 90.9% 10 / 11 Podpod 33.3% 2 / 6 totaltotal 73.8% 133 / 180 CC 31 SCAR 27.6
CC
31
Cov
75%
rebin
31.9
kernctr
10.2
ninterpol
4.9
CRAP 15.9
« blib/lib/PDL/Core.pm ↑ Summary blib/lib/PDL/Reduce.pm »
1 use strict;
2 use warnings;
3  
4 pp_addpm({At=>'Top'},<<'EOD');
5  
6 =head1 NAME
7  
8 PDL::ImageND - useful image processing in N dimensions
9  
10 =head1 DESCRIPTION
11  
12 These routines act on PDLs as N-dimensional objects, not as broadcasted
13 sets of 0-D or 1-D objects. The file is sort of a catch-all for
14 broadly functional routines, most of which could legitimately
15 be filed elsewhere (and probably will, one day).
16  
17 ImageND is not a part of the PDL core (v2.4) and hence must be explicitly
18 loaded.
19  
20 =head1 SYNOPSIS
21  
22 use PDL::ImageND;
23  
24 $y = $x->convolveND($kernel,{bound=>'periodic'});
25 $y = $x->rebin(50,30,10);
26  
27 =cut
28 5 ▶ 
Subroutine BEGIN: called CC=1 SCAR=0.0
29 5 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 use warnings;
31  
32 EOD
33  
34 pp_addpm({At=>'Bot'},<<'EOD');
35  
36 =head1 AUTHORS
37  
38 Copyright (C) Karl Glazebrook and Craig DeForest, 1997, 2003
39 All rights reserved. There is no warranty. You are allowed
40 to redistribute this software / documentation under certain
41 conditions. For details, see the file COPYING in the PDL
42 distribution. If this file is separated from the PDL distribution,
43 the copyright notice should be included in the file.
44  
45 =cut
46 EOD
47  
48 # N-dim utilities
49  
50 pp_addpm(<<'EOD');
51 5 ▶ 
Subroutine BEGIN: called CC=1 SCAR=0.0
52 use Carp;
53  
54 EOD
55  
56 pp_add_exported('','kernctr');
57  
58  
59 pp_def('convolve',Doc=><<'EOD',
60 =for ref
61  
62 N-dimensional convolution (Deprecated; use convolveND)
63  
64 =for usage
65  
66 $new = convolve $x, $kernel
67  
68 Convolve an array with a kernel, both of which are N-dimensional. This
69 routine does direct convolution (by copying) but uses quasi-periodic
70 boundary conditions: each dim "wraps around" to the next higher row in
71 the next dim.
72  
73 This routine is kept for backwards compatibility with earlier scripts;
74 for most purposes you want L<convolveND|PDL::ImageND/convolveND> instead:
75 it runs faster and handles a variety of boundary conditions.
76  
77 =cut
78  
79  
80 EOD
81 Pars => 'a(m); b(n); indx adims(p); indx bdims(q); [o]c(m);',
82 PMCode => '
83 sub PDL::convolve {
84 my($x,$y,$c) = @_;
85 barf("Usage: convolve(a(*), b(*), [o]c(*)") if $#_<1 || $#_>2;
86 $c = PDL->null if $#_<2;
87 PDL::_convolve_int( $x->flat, $y->flat,
88 $x->shape, $y->shape,
89 $c->isnull ? $c : $c->flat,
90 );
91 $c->setdims([$x->dims]);
92  
93 if($x->is_inplace) {
94 $x .= $c;
95 $x->set_inplace(0);
96 return $x;
97 }
98 return $c;
99 }
100 ',
101 RedoDimsCode => '
102 if ($SIZE(p) != $SIZE(q))
103 $CROAK("Arguments do not have the same dimensionality");
104 PDL_Indx i, *dimsa = $P(adims), *dimsb = $P(bdims);
105 for(i=0; i<$SIZE(p); i++)
106 if (dimsb[i]>=dimsa[i])
107 $CROAK("Second argument must be smaller in all dimensions that first");
108 ',
109 CHeader => <<'EOF',
110 /* Compute offset of (x,y,z,...) position in row-major list */
111 static inline PDL_Indx ndim_get_offset(PDL_Indx* pos, PDL_Indx* dims, PDL_Long ndims) {
112 PDL_Long i;
113 PDL_Indx result,size;
114 size = 1;
115 result = 0;
116 for (i=0; i<ndims; i++) {
117 if (i>0)
118 size = size*dims[i-1];
119 result = result + pos[i]*size;
120 }
121 return result;
122 }
123 /* Increment a position pointer array by one row */
124 static inline void ndim_row_plusplus ( PDL_Indx* pos, PDL_Indx* dims, PDL_Long ndims ) {
125 PDL_Long noescape;
126 PDL_Indx i;
127 i=1; noescape=1;
128 while(noescape) {
129 (pos[i])++;
130 if (pos[i]==dims[i]) { /* Carry */
131 if (i>=(ndims)-1) {
132 noescape = 0; /* Exit */
133 }else{
134 pos[i]=0;
135 i++;
136 }
137 }else{
138 noescape = 0; /* Exit */
139 }
140 }
141 }
142 EOF
143 Code => '
144 PDL_Indx *dimsa = $P(adims);
145 PDL_Indx *dimsb = $P(bdims);
146 PDL_Indx andims = $SIZE(p);
147 PDL_Indx bndims = $SIZE(q);
148 PDL_Indx anvals = $SIZE(m);
149 PDL_Indx bnvals = $SIZE(n);
150 double cc;
151  
152 PDL_Indx i,i2,j,k,n,offcen=0,ncen=0,nrow;
153  
154 PDL_Indx pos[andims];
155 for (i=0; i<andims; i++) /* Zero */
156 pos[i]=0;
157  
158 /* Find middle pixel in b */
159 i=0; nrow = dimsb[0];
160 while (i<bnvals) {
161 for (j=0; j<nrow; j++) { /* For each row */
162 pos[0]=j;
163 for (k=0; k < bndims; k++) { /* Is centre? */
164 if (pos[k] != dimsb[k]/2) goto getout_$GENERIC();
165 }
166 ncen = i;
167 getout_$GENERIC(): i++;
168 }
169 pos[0]=0;
170 ndim_row_plusplus( pos, dimsb, bndims );
171 }
172  
173 for (i=0; i<andims; i++) /* Zero */
174 pos[i]=0;
175  
176 /* Initialise offset array to handle the relative coords efficiently */
177 PDL_Indx off[bnvals]; /* Offset array */
178  
179 i=0;
180 while(i<bnvals) {
181 n = ndim_get_offset(pos, dimsa, andims); /* Start of row in A */
182 for (j=0; j<nrow; j++) { /* Fill row */
183 off[i] = n+j;
184 if (i==ncen)
185 offcen = off[i]; /* Offset to middle */
186 i++;
187 }
188 ndim_row_plusplus( pos, dimsa, andims );
189 }
190  
191 for(i=0;i<bnvals;i++) /* Subtract center offset */
192 off[i]=offcen-off[i];
193  
194 /* Now convolve the data */
195  
196 for(i=0; i<anvals; i++) {
197 cc = 0;
198 for(j=0; j<bnvals; j++) {
199 i2 = (i+off[j]+anvals) % anvals ;
200 cc += $a( m=> i2 ) * $b(n=>j) ;
201 }
202 $c(m=>i) = cc;
203 }
204 ');
205  
206  
207 pp_add_exported('',"ninterpol");
208  
209 pp_addpm(<<'EOD');
210  
211 =head2 ninterpol()
212  
213 =for ref
214  
215 N-dimensional interpolation routine
216  
217 =for sig
218  
219 Signature: ninterpol(point(),data(n),[o]value())
220  
221 =for usage
222  
223 $value = ninterpol($point, $data);
224  
225 C<ninterpol> uses C<interpol> to find a linearly interpolated value in
226 N dimensions, assuming the data is spread on a uniform grid. To use
227 an arbitrary grid distribution, need to find the grid-space point from
228 the indexing scheme, then call C<ninterpol> -- this is far from
229 trivial (and ill-defined in general).
230  
231 See also L<interpND|PDL::Primitive/interpND>, which includes boundary
232 conditions and allows you to switch the method of interpolation, but
233 which runs somewhat slower.
234  
235 =cut
236  
237  
238 0 ▶*ninterpol = \&PDL::ninterpol;
Subroutine ninterpol: not called CC=3 SCAR=16.0
Pod undocumented
239 5 ▶ 
Subroutine BEGIN: called CC=1 SCAR=0.0
240 5 ▶sub PDL::ninterpol {
Subroutine BEGIN: called CC=1 SCAR=0.0
241 0 ▶ use PDL::Math 'floor';
Branch: 1 branch
BranchTrueFalseTotal
if $#_ != 1 0 0 0
242 0 use PDL::Primitive 'interpol';
243 0 print 'Usage: $x = ninterpolate($point(s), $data);' if $#_ != 1;
244 my ($p, $y) = @_;
245 0 my ($ip) = floor($p);
246 0 # isolate relevant N-cube
247 0 $y = $y->slice(join (',',map($_.':'.($_+1),list $ip)));
248 for (list ($p-$ip)) { $y = interpol($_,$y->xvals,$y); }
249 $y;
250 }
251  
252 EOD
253  
254 pp_def('rebin',Doc=><<'EOD',
255 =for ref
256  
257 N-dimensional rebinning algorithm
258  
259 =for usage
260  
261 $new = rebin $x, $dim1, $dim2,..;.
262 $new = rebin $x, $template;
263 $new = rebin $x, $template, {Norm => 1};
264  
265 Rebin an N-dimensional array to newly specified dimensions.
266 Specifying `Norm' keeps the sum constant, otherwise the intensities
267 are kept constant. If more template dimensions are given than for the
268 input pdl, these dimensions are created; if less, the final dimensions
269 are maintained as they were.
270  
271 So if C<$x> is a 10 x 10 pdl, then C<rebin($x,15)> is a 15 x 10 pdl,
272 while C<rebin($x,15,16,17)> is a 15 x 16 x 17 pdl (where the values
273 along the final dimension are all identical).
274  
275 Expansion is performed by sampling; reduction is performed by averaging.
276 If you want different behavior, use L<PDL::Transform::map|PDL::Transform/map>
277 instead. PDL::Transform::map runs slower but is more flexible.
278  
279 =cut
280  
281  
282 EOD
283 Pars => 'a(m); [o]b(n);',
284 OtherPars => 'int ns => n',
285 PMCode => pp_line_numbers(__LINE__, <<'EOF'),
286 1 ▶sub PDL::rebin {
Subroutine rebin: called CC=16 SCAR=34.6
Pod undocumented
287 1 my($x) = shift;
288 1 ▶ my($opts) = ref $_[-1] eq "HASH" ? pop : {};
Branch: 1 branch
BranchTrueFalseTotal
ref $_[-1] eq 'HASH' ? : 1 0 1
289 1 my(@idims) = $x->dims;
290 1 ▶ my(@odims) = ref $_[0] ? $_[0]->dims : @_;
Branch: 1 branch
BranchTrueFalseTotal
ref $_[0] ? : 0 1 1
291 1 my($i,$y);
292 1 foreach $i (0..$#odims) {
293 2 ▶ if ($i > $#idims) { # Just dummy extra dimensions
Branch: 2 branches
BranchTrueFalseTotal
if ($i > $#idims) { } 0 2 2
elsif ($odims[$i] != $idims[$i]) { } 2 0 2
294 0 $x = $x->dummy($i,$odims[$i]);
295 0 next;
296 # rebin_int can cope with all cases, but code
297 # 1->n and n->1 separately for speed
298 } elsif ($odims[$i] != $idims[$i]) { # If something changes
299 2 ▶ if (!($odims[$i] % $idims[$i])) { # Cells map 1 -> n
Branch: 2 branches
BranchTrueFalseTotal
if (not $odims[$i] % $idims[$i]) { } 0 2 2
elsif (not $idims[$i] % $odims[$i]) { } 2 0 2
300 0 my ($r) = $odims[$i]/$idims[$i];
301 0 ▶ $y = ($i==0 ? $x : $x->mv($i,0))->dupN($r);
Branch: 1 branch
BranchTrueFalseTotal
$i == 0 ? : 0 0 0
302 } elsif (!($idims[$i] % $odims[$i])) { # Cells map n -> 1
303 2 my ($r) = $idims[$i]/$odims[$i];
304 2 ▶ $x = $x->mv($i,0) if $i != 0;
Branch: 1 branch
BranchTrueFalseTotal
if $i != 0 1 1 2
305 # -> copy so won\'t corrupt input PDL
306 2 $y = $x->slice("0:-1:$r")->copy;
307 2 foreach (1..$r-1) {
308 2 $y += $x->slice("$_:-1:$r");
309 }
310 2 $y /= $r;
311 } else { # Cells map n -> m
312 0 ▶ &PDL::_rebin_int(($i==0 ? $x : $x->mv($i,0)), $y = null, $odims[$i]);
Branch: 1 branch
BranchTrueFalseTotal
$i == 0 ? : 0 0 0
313 }
314 2 $x = $y->mv(0,$i);
315 }
316 }
317 1 ▶ if (exists $opts->{Norm} and $opts->{Norm}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $opts->{'Norm'} and $opts->{'Norm'}) { } 1 0 1
Condition33%1/3
exists $opts->{"Norm"} and $opts->{"Norm"}
!ll&&!rl&&r
001
MC/DC0%0/2
exists $opts->{"Norm"} and $opts->{"Norm"}
exists $opts->{"Norm"} $opts->{"Norm"}
Truth table33%1/3
A and B
A= exists $opts->{"Norm"}B= $opts->{"Norm"}
ABresult
0X0
100
111
318 1 my ($norm) = 1;
319 1 for $i (0..$#odims) {
320 2 ▶ if ($i > $#idims) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > $#idims) { } 0 2 2
321 0 $norm /= $odims[$i];
322 } else {
323 2 $norm *= $idims[$i]/$odims[$i];
324 }
325 }
326 1 return $x * $norm;
327 } else {
328 # Explicit copy so i) can\'t corrupt input PDL through this link
329 # ii) don\'t waste space on invisible elements
330 0 return $x -> copy;
331 }
332 }
333 EOF
334 Code => '
335 int ms = $SIZE(m);
336 int nv = $COMP(ns);
337 int i;
338 double u, d;
339 $GENERIC(a) av;
340 broadcastloop %{
341 i = 0;
342 d = -1;
343 loop (n) %{ $b() = 0; %}
344 loop (m) %{
345 av = $a();
346 u = nv*((m+1.)/ms)-1;
347 while (i <= u) {
348 $b(n => i) += (i-d)*av;
349 d = i;
350 i++;
351 }
352 if (i < nv) $b(n => i) += (u-d)*av;
353 d = u;
354 %}
355 %}
356 ');
357  
358  
359 pp_addpm(<<'EOD');
360  
361 =head2 circ_mean_p
362  
363 =for ref
364  
365 Calculates the circular mean of an n-dim image and returns
366 the projection. Optionally takes the center to be used.
367  
368 =for usage
369  
370 $cmean=circ_mean_p($im);
371 $cmean=circ_mean_p($im,{Center => [10,10]});
372  
373 =cut
374 1 ▶ 
Subroutine circ_mean_p: called CC=2 SCAR=7.0
Pod documented
375 1  
376 1 sub circ_mean_p {
377 my ($x,$opt) = @_;
378 1 ▶ my ($rad,$sum,$norm);
Branch: 1 branch
BranchTrueFalseTotal
if (defined $opt) { } 0 1 1
379 0  
380 if (defined $opt) {
381 $rad = indx PDL::rvals($x,$opt);
382 1 }
383 else {
384 1 $rad = indx rvals $x;
385 1 }
386 1 my $max1 = $rad->max->sclr+1;
387 1 $sum = zeroes($max1);
388 1 PDL::indadd $x->flat, $rad->flat, $sum; # this does the real work
389 1 $norm = zeroes($max1);
390 1 PDL::indadd pdl(1), $rad->flat, $norm; # equivalent to get norm
391 $sum /= $norm;
392 return $sum;
393 }
394  
395 =head2 circ_mean
396  
397 =for ref
398  
399 Smooths an image by applying circular mean.
400 Optionally takes the center to be used.
401  
402 =for usage
403  
404 circ_mean($im);
405 circ_mean($im,{Center => [10,10]});
406  
407 1 ▶=cut
Subroutine circ_mean: called CC=2 SCAR=7.0
Pod documented
408 1  
409 1  
410 sub circ_mean {
411 1 ▶ my ($x,$opt) = @_;
Branch: 1 branch
BranchTrueFalseTotal
if (defined $opt) { } 0 1 1
412 0 my ($rad,$sum,$norm,$a1);
413  
414 if (defined $opt) {
415 1 $rad = indx PDL::rvals($x,$opt);
416 }
417 1 else {
418 6 $rad = indx rvals $x;
419 1 }
420 6 my $max1 = $rad->max->sclr+1;
421 1 $sum = zeroes($max1);
422 1 PDL::indadd $x->flat, $rad->flat, $sum; # this does the real work
423 1 $norm = zeroes($max1);
424 1 PDL::indadd pdl(1), $rad->flat, $norm; # equivalent to get norm
425 $sum /= $norm;
426 6 $a1 = $x->flat;
427 $a1 .= $sum->index($rad->flat);
428  
429 return $x;
430 }
431  
432 EOD
433  
434 pp_add_exported('','circ_mean circ_mean_p');
435  
436  
437 pp_addpm(<<'EOPM');
438 =head2 kernctr
439  
440 =for ref
441  
442 `centre' a kernel (auxiliary routine to fftconvolve)
443  
444 =for usage
445  
446 $kernel = kernctr($image,$smallk);
447 fftconvolve($image,$kernel);
448  
449 kernctr centres a small kernel to emulate the behaviour of the direct
450 convolution routines.
451  
452 =cut
453  
454  
455 *kernctr = \&PDL::kernctr;
456 2 ▶ 
Subroutine kernctr: called CC=10 SCAR=23.3
Pod undocumented
457 sub PDL::kernctr {
458 # `centre' the kernel, to match kernel & image sizes and
459 # emulate convolve/conv2d. FIX: implement with phase shifts
460 2 ▶ # in fftconvolve, with option tag
Branch: 1 branch
BranchTrueFalseTotal
if $#_ != 1 0 2 2
461 2 barf "Must have image & kernel for kernctr" if $#_ != 1;
462 2 my ($imag, $kern) = @_;
463 2 my (@ni) = $imag->dims;
464 2 ▶ my (@nk) = $kern->dims;
Branch: 1 branch
BranchTrueFalseTotal
if $#ni != $#nk 0 2 2
465 2 barf "Kernel and image must have same number of dims" if $#ni != $#nk;
466 2 my ($newk) = zeroes(double,@ni);
467 2 ▶ my ($k,$n,$y,$d,$i,@stri,@strk,@b);
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= $#ni) 4 2 6
468 4 for ($i=0; $i <= $#ni; $i++) {
469 4 $k = $nk[$i];
470 4 ▶ $n = $ni[$i];
Branch: 1 branch
BranchTrueFalseTotal
if $n < $k 0 4 4
471 4 barf "Kernel must be smaller than image in all dims" if ($n < $k);
472 4 $d = int(($k-1)/2);
473 4 $stri[$i][0] = "0:$d,";
474 4 ▶ $strk[$i][0] = (-$d-1).":-1,";
Branch: 1 branch
BranchTrueFalseTotal
$d == 0 ? : 0 4 4
475 4 ▶ $stri[$i][1] = $d == 0 ? '' : ($d-$k+1).':-1,';
Branch: 1 branch
BranchTrueFalseTotal
$d == 0 ? : 0 4 4
476 $strk[$i][1] = $d == 0 ? '' : '0:'.($k-$d-2).',';
477 }
478 2 # kernel is split between the 2^n corners of the cube
479 my ($nchunk) = 2 << $#ni;
480 2 ▶ CHUNK:
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $nchunk) 8 2 10
481 8 for ($i=0; $i < $nchunk; $i++) {
482 8 ▶ my ($stri,$strk);
Branch: 1 branch
BranchTrueFalseTotal
if ($n <= $#ni) 16 8 24
483 16 ▶ for ($n=0, $y=$i; $n <= $#ni; $n++, $y >>= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if $stri[$n][$y & 1] eq "" 0 16 16
484 16 next CHUNK if $stri[$n][$y & 1] eq '';
485 16 $stri .= $stri[$n][$y & 1];
486 $strk .= $strk[$n][$y & 1];
487 8 }
488 8 chop ($stri); chop ($strk);
489 (my $t = $newk->slice($stri)) .= $kern->slice($strk);
490 2 }
491 $newk;
492 }
493  
494 EOPM
495  
496 pp_def(
497 'convolveND',
498 Doc=><<'EOD',
499  
500 =for ref
501  
502 Speed-optimized convolution with selectable boundary conditions
503  
504 =for usage
505  
506 $new = convolveND($x, $kernel, [ {options} ]);
507  
508 Convolve an array with a kernel, both of which are N-dimensional.
509  
510 If the kernel has fewer dimensions than the array, then the extra array
511 dimensions are broadcasted over. There are options that control the boundary
512 conditions and method used.
513  
514 The kernel's origin is taken to be at the kernel's center. If your
515 kernel has a dimension of even order then the origin's coordinates get
516 rounded up to the next higher pixel (e.g. (1,2) for a 3x4 kernel).
517 This mimics the behavior of the earlier L</convolve> and
518 L<fftconvolve|PDL::FFT/fftconvolve()> routines, so convolveND is a drop-in
519 replacement for them.
520  
521  
522 The kernel may be any size compared to the image, in any dimension.
523  
524 The kernel and the array are not quite interchangeable (as in mathematical
525 convolution): the code is inplace-aware only for the array itself, and
526 the only allowed boundary condition on the kernel is truncation.
527  
528 convolveND is inplace-aware: say C<convolveND(inplace $x ,$k)> to modify
529 a variable in-place. You don't reduce the working memory that way -- only
530 the final memory.
531  
532 OPTIONS
533  
534 Options are parsed by PDL::Options, so unique abbreviations are accepted.
535  
536 =over 3
537  
538 =item boundary (default: 'truncate')
539  
540 The boundary condition on the array, which affects any pixel closer
541 to the edge than the half-width of the kernel.
542  
543 The boundary conditions are the same as those accepted by
544 L<range|PDL::Slices/range>, because this option is passed directly
545 into L<range|PDL::Slices/range>. Useful options are 'truncate' (the
546 default), 'extend', and 'periodic'. You can select different boundary
547 conditions for different axes -- see L<range|PDL::Slices/range> for more
548 detail.
549  
550 The (default) truncate option marks all the near-boundary pixels as BAD if
551 you have bad values compiled into your PDL and the array's badflag is set.
552  
553 =item method (default: 'auto')
554  
555 The method to use for the convolution. Acceptable alternatives are
556 'direct', 'fft', or 'auto'. The direct method is an explicit
557 copy-and-multiply operation; the fft method takes the Fourier
558 transform of the input and output kernels. The two methods give the
559 same answer to within double-precision numerical roundoff. The fft
560 method is much faster for large kernels; the direct method is faster
561 for tiny kernels. The tradeoff occurs when the array has about 400x
562 more pixels than the kernel.
563  
564 The default method is 'auto', which chooses direct or fft convolution
565 based on the size of the input arrays.
566  
567 =back
568  
569 NOTES
570  
571 At the moment there's no way to broadcast over kernels. That could/should
572 be fixed.
573  
574 The broadcasting over input is cheesy and should probably be fixed:
575 currently the kernel just gets dummy dimensions added to it to match
576 the input dims. That does the right thing tersely but probably runs slower
577 than a dedicated broadcastloop.
578  
579 The direct copying code uses PP primarily for the generic typing: it includes
580 its own broadcastloops.
581  
582 =cut
583  
584  
585 EOD
586 PMCode => <<'EOD',
587  
588 use PDL::Options;
589  
590 # Perl wrapper conditions the data to make life easier for the PP sub.
591  
592 sub PDL::convolveND {
593 my($a0,$k,$opt0) = @_;
594 my $inplace = $a0->is_inplace;
595 my $x = $a0->new_or_inplace;
596  
597 barf("convolveND: kernel (".join("x",$k->dims).") has more dims than source (".join("x",$x->dims).")\n")
598 if($x->ndims < $k->ndims);
599  
600 # Coerce stuff all into the same type. Try to make sense.
601 # The trivial conversion leaves dataflow intact (nontrivial conversions
602 # don't), so the inplace code is OK. Non-inplace code: let the existing
603 # PDL code choose what type is best.
604 my $type;
605 if($inplace) {
606 $type = $a0->get_datatype;
607 } else {
608 my $z = $x->flat->index(0) + $k->flat->index(0);
609 $type = $z->get_datatype;
610 }
611 $x = $x->convert($type);
612 $k = $k->convert($type);
613  
614 ## Handle options -- $def is a static variable so it only gets set up once.
615 our $def;
616 unless(defined($def)) {
617 $def = PDL::Options->new( {
618 Method=>'a',
619 Boundary=>'t'
620 }
621 );
622 $def->minmatch(1);
623 $def->casesens(0);
624 }
625  
626 my $opt = $def->options(PDL::Options::ifhref($opt0));
627  
628 ###
629 # If the kernel has too few dimensions, we broadcast over the other
630 # dims -- this is the same as supplying the kernel with dummy dims of
631 # order 1, so, er, we do that.
632 $k = $k->dummy($x->dims - 1, 1)
633 if($x->ndims > $k->ndims);
634 my $kdims = pdl($k->dims);
635  
636 ###
637 # Decide whether to FFT or directly convolve: if we're in auto mode,
638 # choose based on the relative size of the image and kernel arrays.
639 my $fft = ( ($opt->{Method} =~ m/^a/i) ?
640 ( $x->nelem > 2500 and ($x->nelem) <= ($k->nelem * 500) ) :
641 ( $opt->{Method} !~ m/^[ds]/i )
642 );
643  
644 ###
645 # Pad the array to include boundary conditions
646 my $adims = $x->shape;
647 my $koff = ($kdims/2)->ceil - 1;
648  
649 my $aa = $x->range( -$koff, $adims + $kdims, $opt->{Boundary} )
650 ->sever;
651  
652 if ($fft) {
653 require PDL::FFT;
654  
655 print "convolveND: using FFT method\n" if($PDL::debug);
656  
657 # FFT works best on doubles; do our work there then cast back
658 # at the end.
659 $aa = double($aa);
660 $_ = $aa->zeroes for my ($aai, $kk, $kki);
661 $kk->range( - ($kdims/2)->floor, $kdims, 'p') .= $k;
662 PDL::fftnd($kk, $kki);
663 PDL::fftnd($aa, $aai);
664  
665 {
666 my($ii) = $kk * $aai + $aa * $kki;
667 $aa = $aa * $kk - $kki * $aai;
668 $aai .= $ii;
669 }
670  
671 PDL::ifftnd($aa,$aai);
672 $x .= $aa->range( $koff, $adims);
673  
674 } else {
675 print "convolveND: using direct method\n" if($PDL::debug);
676  
677 ### The first argument is a dummy to set $GENERIC.
678 &PDL::_convolveND_int( $k->flat->index(0), $k, $aa, $x );
679  
680 }
681  
682  
683 $x;
684 }
685  
686 EOD
687 Pars=>'k0()',
688 OtherPars=>'pdl *k; pdl *aa; pdl *a;',
689  
690 Code => <<'EOD'
691 /*
692 * Direct convolution
693 *
694 * Because the kernel is usually the smaller of the two arrays to be convolved,
695 * we broadcast kernel-first to keep it in the processor's cache. The strategy:
696 * work on a padded copy of the original image, so that (even with boundary
697 * conditions) the geometry of the kernel is linearly related to the input
698 * array. Otherwise, follow the path blazed by Karl in convolve(): keep track
699 * of the offsets for each kernel element in a flattened original PDL.
700 *
701 * The first (PP) argument is a dummy that's only used to set the GENERIC()
702 * macro. The other three arguments should all have the same type as the
703 * first arguments, and are all passed in as SVs. They are: the kernel,
704 * the padded copy of the input PDL, and a pre-allocated output PDL. The
705 * input PDL should be padded by the dimensionality of the kernel.
706 *
707 */
708  
709 PDL_Indx i;
710 pdl *k = $COMP(k), *a = $COMP(a), *aa = $COMP(aa);
711 PDL_RETERROR(PDL_err, PDL->make_physical(aa));
712 PDL_RETERROR(PDL_err, PDL->make_physical(a));
713 PDL_RETERROR(PDL_err, PDL->make_physical(k));
714  
715 PDL_Indx ndims = aa->ndims;
716 if(ndims != k->ndims || ndims != aa->ndims)
717 $CROAK("convolveND: dims don't agree - should never happen\n");
718  
719 PDL_Indx koffs[k->nvals];
720 $GENERIC() kvals[k->nvals];
721 PDL_Indx ivec[ndims];
722  
723 /************************************/
724 /* Fill up the koffs & kvals arrays */
725 /* koffs gets relative offsets into aa for each kernel value; */
726 /* kvals gets the kernel values in the same order (flattened) */
727 PDL_Indx *koff = koffs;
728 $GENERIC() *kval = kvals;
729 $GENERIC() *aptr = ($GENERIC() *)k->data + k->nvals - 1;
730  
731 for (i=0; i < ndims; i++) ivec[i] = 0;
732 PDL_Indx npdls = 2, incs[npdls*ndims], offs[npdls];
733 for (i=0; i < npdls; i++) offs[i] = 0;
734 for (i=0; i < ndims; i++) {
735 incs[i*npdls + 0] = k->dimincs[i];
736 incs[i*npdls + 1] = aa->dimincs[i];
737 }
738 do {
739 *kval++ = aptr[-offs[0]]; /* Copy kernel value into kernel list */
740 *koff++ = offs[1]; /* Copy current aa offset into koffs list */
741 if (!pdl_broadcast_nd_step(npdls, offs, 0, ndims, incs, k->dims, ivec)) break;
742 } while (1);
743  
744 /******************************/
745 /* Now do the actual convolution: for each vector in a, */
746 /* accumulate the appropriate aa-sum and stick it into a. */
747 for (i=0; i < ndims; i++) ivec[i] = 0;
748 aptr = a->data;
749 $GENERIC() *aaptr = aa->data;
750 for (i=0; i < npdls; i++) offs[i] = 0;
751 for (i=0; i < ndims; i++) incs[i*npdls + 0] = a->dimincs[i]; /* got aa already */
752 do {
753 $GENERIC() acc = 0;
754 koff = koffs;
755 kval = kvals;
756 for (i=0;i<k->nvals;i++)
757 acc += aaptr[offs[1] + *koff++] * (*kval++);
758 aptr[offs[0]] = acc;
759 if (!pdl_broadcast_nd_step(npdls, offs, 0, ndims, incs, a->dims, ivec)) break;
760 } while (1);
761 PDL->changed(a, PDL_PARENTDATACHANGED, 0);
762 EOD
763 );
764  
765 pp_def('contour_segments',
766 Pars => 'c(); data(m,n); points(d,m,n);
767 [o] segs(d,q=CALC(($SIZE(m)-1)*($SIZE(n)-1)*4)); indx [o] cnt();',
768 GenericTypes => ['F'],
769 Code => <<'EOF',
770 PDL_Indx p=0;
771 #define PDL_DCALC(vname,c,x1,y1,x2,y2) \
772 $GENERIC(points) vname = (c-$data(m=>x1,n=>y1))/($data(m=>x2,n=>y2)-$data(m=>x1,n=>y1))
773 #define PDL_PCALC(dname,d,x1,y1,x2,y2) \
774 ($points(d=>d,m=>x1,n=>y1)+dname*($points(d=>d,m=>x2,n=>y2)-$points(d=>d,m=>x1,n=>y1)))
775 #define PDL_LINESEG(x01,y01,x02,y02,x11,y11,x12,y12,c,p) do { \
776 PDL_DCALC(dist1,c,x01,y01,x02,y02); \
777 PDL_DCALC(dist2,c,x11,y11,x12,y12); \
778 loop (d) %{ \
779 $segs(q=>p) = PDL_PCALC(dist1,d,x01,y01,x02,y02); \
780 $segs(q=>p+1) = PDL_PCALC(dist2,d,x11,y11,x12,y12); \
781 %} \
782 p+=2; \
783 } while (0)
784 #define PDL_CONTOUR_BREAK(x1,y1,x2,y2,c) \
785 (($data(m=>x1,n=>y1) < c) != ($data(m=>x2,n=>y2) < c))
786 loop (n=:-1,m=:-1) %{
787 PDL_Indx m1=m+1, n1=n+1;
788 char brk_0010 = PDL_CONTOUR_BREAK(m,n,m1,n,$c()),
789 brk_0001 = PDL_CONTOUR_BREAK(m,n,m,n1,$c()),
790 brk_1011 = PDL_CONTOUR_BREAK(m1,n,m1,n1,$c()),
791 brk_0111 = PDL_CONTOUR_BREAK(m,n1,m1,n1,$c());
792 if (brk_0010 && brk_1011)
793 PDL_LINESEG(m,n,m1,n,m1,n,m1,n1,$c(),p); /* from m,n right, stretched right/down */
794 if (brk_0001 && brk_0010 && !brk_1011)
795 PDL_LINESEG(m,n,m1,n,m,n,m,n1,$c(),p); /* loop m,n, stretched right/down */
796 if (brk_0010 && brk_0111 && !brk_0001 && !brk_1011)
797 PDL_LINESEG(m,n,m1,n,m,n1,m1,n1,$c(),p); /* from m,n down, both stretched right */
798 if (brk_0001 && brk_0111 && !(brk_0010 && !brk_1011))
799 PDL_LINESEG(m,n,m,n1,m,n1,m1,n1,$c(),p); /* from m,n downward, stretched down/right */
800 if (brk_0001 && brk_1011 && !brk_0010 && !brk_0111)
801 PDL_LINESEG(m,n,m,n1,m1,n,m1,n1,$c(),p); /* from m,n rightward, both stretched downward */
802 if (brk_0111 && brk_1011 && !brk_0010)
803 PDL_LINESEG(m1,n,m1,n1,m,n1,m1,n1,$c(),p); /* from m1,n down/left, stretched down/left */
804 %}
805 #undef PDL_DCALC
806 #undef PDL_PCALC
807 #undef PDL_LINESEG
808 #undef PDL_CONTOUR_BREAK
809 $cnt()=p-1;
810 EOF
811 Doc => <<'EOF',
812 =for ref
813  
814 Finds a contour in given data. Takes 3 ndarrays as input:
815  
816 C<$c> is the contour value (broadcast with this)
817  
818 C<$data> is an [m,n] array of values at each point
819  
820 C<$points> is a list of [d,m,n] points. It should be a grid monotonically
821 increasing with m and n.
822  
823 Returns C<$segs>, and C<$cnt> which is the highest 2nd-dim index in
824 C<$segs> that's defined. The contours are a collection of disconnected
825 line segments rather than a set of closed polygons.
826  
827 The data array represents samples of some field observed on the surface
828 described by points. This uses a variant of the Marching Squares
829 algorithm, though without being data-driven.
830 EOF
831 );
832  
833 pp_def('contour_polylines',
834 Pars => 'c(); data(m,n); points(d,m,n);
835 indx [o] pathendindex(q=CALC(($SIZE(m)-1)*($SIZE(n)-1)*5)); [o] paths(d,q);
836 byte [t] seenmap(m,n)',
837 GenericTypes => ['F'],
838 Code => <<'EOF',
839 int dir2xy[4][2] = { /* 0 = east, 1 = south, 2 = west, 3 = north */
840 {1,0}, {0,1}, {-1,0}, {0,-1}
841 };
842 broadcastloop %{
843 PDL_Indx polyind = 0, p = 0;
844 loop (n,m) %{ $seenmap() = 0; %} /* & 1 = east, & 2 = south */
845 loop (q) %{ $pathendindex() = -1; %}
846 #define PDL_DCALC(vname,c,x1,y1,x2,y2) \
847 $GENERIC(points) vname = (c-$data(m=>x1,n=>y1))/($data(m=>x2,n=>y2)-$data(m=>x1,n=>y1))
848 #define PDL_PCALC(dname,d,x1,y1,x2,y2) \
849 ($points(d=>d,m=>x1,n=>y1)+dname*($points(d=>d,m=>x2,n=>y2)-$points(d=>d,m=>x1,n=>y1)))
850 #define PDL_LINEPOINT(x,y,dir,c,p) do { \
851 PDL_Indx x2 = x+dir2xy[dir][0], y2 = y+dir2xy[dir][1]; \
852 PDL_DCALC(dist,c,x,y,x2,y2); \
853 loop (d) %{ $paths(q=>p) = PDL_PCALC(dist,d,x,y,x2,y2); %} \
854 p++; \
855 } while (0)
856 #define PDL_CONTOUR_BREAK(x,y,dir,c) \
857 (x >= 0 && x < $SIZE(m) && y >= 0 && y < $SIZE(n) && \
858 (x+dir2xy[dir][0]) >= 0 && (x+dir2xy[dir][0]) < $SIZE(m) && \
859 (y+dir2xy[dir][1]) >= 0 && (y+dir2xy[dir][1]) < $SIZE(n) && \
860 !((dir == 0 && ($seenmap(m=>x,n=>y) & (1<<dir))) || \
861 (dir == 1 && ($seenmap(m=>x,n=>y) & (1<<dir))) || \
862 (dir == 2 && ($seenmap(m=>x-1,n=>y) & (1<<(dir % 2)))) || \
863 (dir == 3 && ($seenmap(m=>x,n=>y-1) & (1<<(dir % 2)))) \
864 ) && \
865 (($data(m=>x,n=>y) < c) != ($data(m=>x+dir2xy[dir][0],n=>y+dir2xy[dir][1]) < c)))
866 loop (n,m) %{
867 PDL_Indx m1=m+1, n1=n+1, linex=-1, liney=-1, linedir=-1;
868 /* linedir is same as dir, but outside linex/y and facing clockwise */
869 char brk_ab = PDL_CONTOUR_BREAK(m,n,0,$c()),
870 brk_ad = PDL_CONTOUR_BREAK(m,n,1,$c()),
871 brk_be = PDL_CONTOUR_BREAK(m1,n,1,$c()),
872 brk_cd = PDL_CONTOUR_BREAK(m,n1,2,$c()), /* actually dc */
873 brk_de = PDL_CONTOUR_BREAK(m,n1,0,$c());
874 if (brk_ab && (brk_ad || brk_de || brk_be))
875 linex = m, liney = n, linedir = 1;
876 else
877 $seenmap() |= 1;
878 if (linedir < 0 && brk_ad && brk_cd)
879 linex = m, liney = n, linedir = 2;
880 if (linedir < 0 && brk_ad && (brk_de || brk_be))
881 linex = m, liney = n1, linedir = 0;
882 if (linedir < 0) { $seenmap() |= 2; continue; }
883 PDL_Indx startlinex=linex, startliney=liney, startlinedir=linedir;
884 PDL_Float startmidx=linex+0.5*dir2xy[(linedir+3)%4][0], startmidy=liney+0.5*dir2xy[(linedir+3)%4][1]; /* of the line-segment */
885 PDL_Float startbackx=startmidx+0.5*dir2xy[(linedir+2)%4][0], startbacky=startmidy+0.5*dir2xy[(linedir+2)%4][1];
886 /* walk the line */
887 while (1) {
888 PDL_LINEPOINT(linex,liney,(linedir+3)%4,$c(),p);
889 switch (linedir) {
890 case 0: $seenmap(m=>linex,n=>liney-1) |= (1<<((linedir+1)%2)); break;
891 case 1: $seenmap(m=>linex,n=>liney) |= (1<<((linedir+1)%2)); break;
892 case 2: $seenmap(m=>linex,n=>liney) |= (1<<((linedir+1)%2)); break;
893 case 3: $seenmap(m=>linex-1,n=>liney) |= (1<<((linedir+1)%2)); break;
894 default: $CROAK("linedir had invalid value %"IND_FLAG, linedir);
895 }
896 char brk_right = PDL_CONTOUR_BREAK(linex,liney,linedir,$c()),
897 brk_straight = PDL_CONTOUR_BREAK(linex+dir2xy[linedir][0],liney+dir2xy[linedir][1],(linedir+3)%4,$c()),
898 brk_left = PDL_CONTOUR_BREAK(linex+dir2xy[(linedir+3)%4][0],liney+dir2xy[(linedir+3)%4][1],linedir,$c());
899 if (brk_right) {
900 linedir = (linedir+1)%4;
901 continue;
902 }
903 if (brk_straight) {
904 linex += dir2xy[linedir][0], liney += dir2xy[linedir][1];
905 continue;
906 }
907 if (brk_left) {
908 linex += dir2xy[linedir][0], liney += dir2xy[linedir][1]; /* step with */
909 linedir = (linedir+3)%4;
910 linex += dir2xy[linedir][0], liney += dir2xy[linedir][1]; /* and left */
911 continue;
912 }
913 break;
914 }
915 PDL_Float endmidx=linex+0.5*dir2xy[(linedir+3)%4][0], endmidy=liney+0.5*dir2xy[(linedir+3)%4][1];
916 PDL_Float endfrontx=endmidx+0.5*dir2xy[linedir][0], endfronty=endmidy+0.5*dir2xy[linedir][1];
917 if (endfrontx == startbackx && endfronty == startbacky) /* close polygon */
918 PDL_LINEPOINT(startlinex,startliney,(startlinedir+3)%4,$c(),p);
919 $pathendindex(q=>polyind++) = p - 1;
920 %}
921 %}
922 #undef PDL_DCALC
923 #undef PDL_PCALC
924 #undef PDL_LINEPOINT
925 #undef PDL_CONTOUR_BREAK
926 EOF
927 Doc => <<'EOF',
928 =for ref
929  
930 Finds polylines describing contours in given data. Takes 3 ndarrays as input:
931  
932 C<$c> is the contour value (broadcast with this)
933  
934 C<$data> is an [m,n] array of values at each point
935  
936 C<$points> is a list of [d,m,n] points. It should be a grid monotonically
937 increasing with m and n.
938  
939 Returns C<$pathendindex>, and C<$paths>. Any C<$pathendindex> entries
940 after the pointers to the ends of polylines are negative.
941  
942 =head3 Algorithm
943  
944 Has two modes: scanning, and line-walking. Scanning is done from the
945 top left, along each row. Each point can be considered as, at C<a>:
946  
947 a|b
948 +-+-
949 c|d|e
950  
951 Every potential boundary above, or to the left of (including the bottom
952 boundaries), C<a> has been cleared (marked with a space above).
953  
954 =head4 Boundary detection
955  
956 This is done by first checking both points' coordinates are within
957 bounds, then checking if the boundary is marked seen, then detecting
958 whether the two cells' values cross the contour threshold.
959  
960 =head4 Scanning
961  
962 If detect boundary between C<a>-C<b>, and also C<a>-C<d>, C<d>-C<e>,
963 or C<b>-C<e>, line-walking starts C<a>-C<b> facing south.
964  
965 If not, mark C<a>-C<b> seen.
966  
967 If detect boundary C<a>-C<d> and C<c>-C<d>, line-walking starts C<a>-C<d>
968 facing west.
969  
970 If detect boundary C<a>-C<d> and also C<d>-C<e> or C<b>-C<e>, line-walking
971 starts C<a>-C<d> facing east.
972  
973 If not, mark C<a>-C<d> seen, and continue scanning.
974  
975 =head4 Line-walking
976  
977 The conditions above guarantee that any line started will have at least
978 two points, since two connected "points" (boundaries between two cells)
979 have been detected. The coordinates of the back end of the starting
980 "point" (boundary with direction) are recorded.
981  
982 At each, a line-point is emitted and that "point" is marked seen. The
983 coordinates emitted are linearly interpolated between the coordinates
984 of the two cells similarly to the Marching Squares algorithm.
985  
986 The next "point" is sought, looking in order right, straight ahead, then
987 left. Each one not detected is marked seen. That order means the walked
988 boundary will always turn as much right (go clockwise) as available,
989 thereby guaranteeing enclosing the area, which deals with saddle points.
990  
991 If a next "point" is found, move to that and repeat.
992  
993 If not, then if the front of the ending "point" (boundary plus direction)
994 is identical to the back of the starting point, a final point is emitted
995 to close the shape. Then the polyline is closed by emitting the current
996 point-counter into C<polyendindex>.
997  
998 =for usage
999  
1000 use PDL;
1001 use PDL::ImageND;
1002 use PDL::Graphics::Simple;
1003 $SIZE = 500;
1004 $vals = rvals($SIZE,$SIZE)->divide($SIZE/12.5)->sin;
1005 @cntr_threshes = zeroes(9)->xlinvals($vals->minmax)->list;
1006 $win = pgswin();
1007 $xrange = [0,$vals->dim(0)-1]; $yrange = [0,$vals->dim(1)-1];
1008 $win->plot(with=>'image', $vals, {xrange=>$xrange,yrange=>$yrange,j=>1},);
1009 for $thresh (@cntr_threshes) {
1010 ($pi, $p) = contour_polylines($thresh, $vals, $vals->ndcoords);
1011 $pi_max = $pi->max;
1012 next if $pi_max < 0;
1013 $pi = $pi->where($pi > -1);
1014 $p = $p->slice(',0:'.$pi_max);
1015 @paths = path_segs($pi, $p->mv(0,-1));
1016 $win->oplot(
1017 (map +(with=>'lines', $_->dog), @paths),
1018 {xrange=>$xrange,yrange=>$yrange,j=>1},
1019 );
1020 }
1021 print "ret> "; <>;
1022 EOF
1023 );
1024  
1025 pp_def('path_join',
1026 Pars => 'e(v=2,n);
1027 indx [o] pathendindex(n); indx [o] paths(nout=CALC($SIZE(n)*2));
1028 indx [t] highestoutedge(d); indx [t] outedges(d,d); byte [t] hasinward(d);
1029 indx [t] sourceids(d);
1030 ',
1031 OtherPars => 'PDL_Indx d => d; int directed;',
1032 OtherParsDefaults => { directed => 1 },
1033 Code => <<'EOF',
1034 loop (d) %{ $highestoutedge() = -1; $hasinward() = 0; %}
1035 loop (n) %{ $pathendindex() = -1; %}
1036 loop (nout) %{ $paths() = -1; %}
1037 #define PDL_ADJ_ADD(idfrom,idto) \
1038 do { \
1039 if (idfrom >= $SIZE(d) || idfrom < 0) \
1040 $CROAK("from index %"IND_FLAG"=%"IND_FLAG" out of bounds", n, idfrom); \
1041 if (idto >= $SIZE(d) || idto < 0) \
1042 $CROAK("to index %"IND_FLAG"=%"IND_FLAG" out of bounds", n, idto); \
1043 PDL_Indx setind = ++$highestoutedge(d=>idfrom); \
1044 if (setind >= $SIZE(d)) \
1045 $CROAK("setind=%"IND_FLAG" exceeded d=%"IND_FLAG, setind, $SIZE(d)); \
1046 $outedges(d0=>setind,d1=>idfrom) = idto; \
1047 $hasinward(d=>idto) = 1; \
1048 } while (0)
1049 loop (n) %{
1050 PDL_Indx from = $e(v=>0), to = $e(v=>1);
1051 PDL_ADJ_ADD(from,to);
1052 if (!$COMP(directed)) PDL_ADJ_ADD(to,from);
1053 %}
1054 #undef PDL_ADJ_ADD
1055 PDL_Indx highest_no_inward = -1;
1056 loop (d) %{
1057 if ($hasinward() || $highestoutedge() == -1) continue;
1058 $sourceids(d=>++highest_no_inward) = d;
1059 %}
1060 PDL_Indx pind = 0, pcount = 0;
1061 while (1) {
1062 PDL_Indx idthis = -1, idnext = -1;
1063 if (highest_no_inward >= 0) {
1064 idthis = $sourceids(d=>highest_no_inward);
1065 if ($highestoutedge(d=>idthis) == 0) highest_no_inward--;
1066 }
1067 if (idthis == -1)
1068 loop (d) %{
1069 if ($highestoutedge() == -1) continue;
1070 idthis = d; break;
1071 %}
1072 if (idthis == -1) break;
1073 while (1) {
1074 if (idthis == -1) break;
1075 if (pind >= $SIZE(nout)) $CROAK("pind exceeded nout");
1076 $paths(nout=>pind++) = idthis;
1077 PDL_Indx edgehighest = $highestoutedge(d=>idthis), edgeidnext = -1;
1078 if (edgehighest < 0) break;
1079 idnext = -1;
1080 loop (d0=edgehighest:0:-1) %{ /* look for non-sink */
1081 PDL_Indx maybe_next = $outedges(d1=>idthis);
1082 if ($highestoutedge(d=>maybe_next) <= 0) continue;
1083 edgeidnext = d0;
1084 %}
1085 if (edgeidnext == -1) edgeidnext = edgehighest;
1086 idnext = $outedges(d0=>edgeidnext,d1=>idthis);
1087 if (edgeidnext != edgehighest)
1088 loop (d0=edgeidnext:edgehighest) %{
1089 $outedges(d1=>idthis) = $outedges(d0=>d0+1,d1=>idthis);
1090 %}
1091 $highestoutedge(d=>idthis) = edgehighest - 1;
1092 if (!$COMP(directed)) { /* remove the edge in the other direction */
1093 edgehighest = $highestoutedge(d=>idnext);
1094 edgeidnext = -1;
1095 loop (d0=edgehighest:0:-1) %{
1096 PDL_Indx maybe_other = $outedges(d1=>idnext);
1097 if (maybe_other != idthis) continue;
1098 edgeidnext = d0;
1099 break;
1100 %}
1101 if (edgeidnext == -1)
1102 $CROAK("no other edge %"IND_FLAG"-%"IND_FLAG, idthis, idnext);
1103 if (edgeidnext != edgehighest)
1104 loop (d0=edgeidnext:edgehighest) %{
1105 $outedges(d1=>idnext) = $outedges(d0=>d0+1,d1=>idnext);
1106 %}
1107 $highestoutedge(d=>idnext) = edgehighest - 1;
1108 }
1109 idthis = idnext;
1110 }
1111 if (pcount >= $SIZE(n)) $CROAK("pcount exceeded n");
1112 $pathendindex(n=>pcount++) = pind - 1;
1113 if (idthis == -1) break;
1114 }
1115 EOF
1116 Doc => <<'EOF',
1117 =for ref
1118  
1119 Links a (by default directed) graph's edges into paths.
1120  
1121 The outputs are the indices into C<paths> ending each path. Past the last
1122 path, the indices are set to -1.
1123 EOF
1124 );
1125  
1126 pp_addpm(<<'EOPM');
1127 =head2 path_segs
1128  
1129 =for ref
1130  
1131 Divide a path into segments.
1132  
1133 =for usage
1134  
1135 @segments = path_segs($pathindices, $paths);
1136  
1137 Returns a series of slices of the C<paths>, such as those created by
1138 L</path_join>, stopping at the first negative index. Currently does not
1139 broadcast.
1140  
1141 =for example
1142  
1143 use PDL;
1144 use PDL::ImageND;
1145 use PDL::Graphics::Simple;
1146 $SIZE = 500;
1147 $vals = rvals($SIZE,$SIZE)->divide($SIZE/12.5)->sin;
1148 @cntr_threshes = zeroes(9)->xlinvals($vals->minmax)->list;
1149 $win = pgswin();
1150 $xrange = [0,$vals->dim(0)-1]; $yrange = [0,$vals->dim(1)-1];
1151 $win->plot(with=>'image', $vals, {xrange=>$xrange,yrange=>$yrange,j=>1},);
1152 for $thresh (@cntr_threshes) {
1153 my ($segs, $cnt) = contour_segments($thresh, $vals, $vals->ndcoords);
1154 my $segscoords = $segs->slice(',0:'.$cnt->max)->clump(-1)->splitdim(0,4);
1155 $linesegs = $segscoords->splitdim(0,2);
1156 $uniqcoords = $linesegs->uniqvec;
1157 next if $uniqcoords->dim(1) < 2;
1158 $indexed = vsearchvec($linesegs, $uniqcoords)->uniqvec;
1159 @paths = path_segs(path_join($indexed, $uniqcoords->dim(1), 0));
1160 @paths = map $uniqcoords->dice_axis(1, $_)->mv(0,-1), @paths;
1161 $win->oplot(
1162 (map +(with=>'lines', $_->dog), @paths),
1163 {xrange=>$xrange,yrange=>$yrange,j=>1},
1164 );
1165 }
1166 print "ret> "; <>;
1167  
1168 =cut
1169  
1170 *path_segs = \&PDL::path_segs;
1171 1 ▶sub PDL::path_segs {
Subroutine path_segs: called CC=3 SCAR=11.0
Pod undocumented
1172 1 my ($pi, $p) = @_;
1173 1 my ($startind, @out) = 0;
1174 1 for ($pi->list) {
1175 4 ▶ last if $_ < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $_ < 0 1 3 4
1176 3 push @out, $p->slice("$startind:$_");
1177 3 $startind = $_ + 1;
1178 }
1179 1 @out;
1180 }
1181 EOPM
1182 pp_add_exported('','path_segs');
1183  
1184 pp_def('combcoords',
1185 GenericTypes => ['F','D'],
1186 Pars => 'x(); y(); z();
1187 float [o]coords(tri=3);',
1188 Code => '
1189 $coords(tri => 0) = $x();
1190 $coords(tri => 1) = $y();
1191 $coords(tri => 2) = $z();
1192 ',
1193 DefaultFlow => 1,
1194 Doc => <<'EOT',
1195 =for ref
1196  
1197 Combine three coordinates into a single ndarray.
1198  
1199 Combine x, y and z into a single ndarray the first dimension
1200 of which is 3.
1201 EOT
1202 );
1203  
1204 pp_def('repulse',
1205 GenericTypes => ['F','D'],
1206 Pars => 'coords(nc,np); [o]vecs(nc,np); int [t]links(np);',
1207 OtherPars => '
1208 double boxsize;
1209 int dmult;
1210 double a;
1211 double b;
1212 double c;
1213 double d;
1214 ',
1215 Code => <<'EOF',
1216 double a = $COMP(a);
1217 double b = $COMP(b);
1218 double c = $COMP(c);
1219 double d = $COMP(d);
1220 int ind; int x,y,z;
1221 HV *hv = newHV();
1222 double boxsize = $COMP(boxsize);
1223 int dmult = $COMP(dmult);
1224 loop(np) %{
1225 int index = 0;
1226 $links() = -1;
1227 loop(nc) %{
1228 $vecs() = 0;
1229 index *= dmult;
1230 index += (int)($coords()/boxsize);
1231 %}
1232 /* Repulse old (shame to use x,y,z...) */
1233 for (x=-1; x<=1; x++) {
1234 for (y=-1; y<=1; y++) {
1235 for (z=-1; z<=1; z++) {
1236 int ni = index + x + dmult * y + dmult * dmult * z;
1237 SV **svp = hv_fetch(hv, (char *)&ni, sizeof(int), 0);
1238 if (svp && *svp) {
1239 ind = SvIV(*svp) - 1;
1240 while (ind>=0) {
1241 double dist = 0;
1242 double dist2;
1243 double tmp;
1244 double func;
1245 loop(nc) %{
1246 tmp = ($coords() - $coords(np => ind));
1247 dist += tmp * tmp;
1248 %}
1249 dist = sqrt(1/(sqrt(dist)+d));
1250 func = c * dist;
1251 dist2 = dist * dist;
1252 func += b * dist2;
1253 dist2 *= dist2;
1254 func += a * dist2;
1255 loop(nc) %{
1256 tmp = ($coords() - $coords(np => ind));
1257 $vecs() -= func * tmp;
1258 $vecs(np => ind) += func * tmp;
1259 %}
1260 ind = $links(np => ind);
1261 }
1262 }
1263 }
1264 }
1265 }
1266 /* Store new */
1267 SV **svp = hv_fetch(hv, (char *)&index, sizeof(index), 1);
1268 if(!svp || !*svp)
1269 $CROAK("Invalid sv from hvfetch");
1270 SV *sv = *svp;
1271 int npv;
1272 if(SvOK(sv) && (npv = SvIV(sv))) {
1273 npv --;
1274 $links() = $links(np => npv);
1275 $links(np => npv) = np;
1276 } else {
1277 sv_setiv(sv,np+1);
1278 $links() = -1;
1279 }
1280 %}
1281 hv_undef(hv);
1282 EOF
1283 Doc => <<'EOF',
1284 =for ref
1285  
1286 Repulsive potential for molecule-like constructs.
1287  
1288 C<repulse> uses a hash table of cubes to quickly calculate
1289 a repulsive force that vanishes at infinity for many
1290 objects. For use by the module L<PDL::Graphics::TriD::MathGraph>.
1291 Checks all neighbouring boxes. The formula is:
1292  
1293 (r = |dist|+d) a*r^-2 + b*r^-1 + c*r^-0.5
1294 EOF
1295 );
1296  
1297 pp_def('attract',
1298 GenericTypes => ['F','D'],
1299 Pars => 'coords(nc,np);
1300 int from(nl);
1301 int to(nl);
1302 strength(nl);
1303 [o]vecs(nc,np);',
1304 OtherPars => '
1305 double m;
1306 double ms;
1307 ',
1308 Code => <<'EOF',
1309 double m = $COMP(m);
1310 double ms = $COMP(ms);
1311 loop(nc,np) %{ $vecs() = 0; %}
1312 loop(nl) %{
1313 int f = $from();
1314 int t = $to();
1315 double s = $strength();
1316 double dist = 0;
1317 double tmp;
1318 loop(nc) %{
1319 tmp = $coords(np => f) - $coords(np => t);
1320 dist += tmp * tmp;
1321 %}
1322 s *= ms * dist + m * sqrt(dist);
1323 loop(nc) %{
1324 tmp = $coords(np => f) - $coords(np => t);
1325 $vecs(np => f) -= tmp * s;
1326 $vecs(np => t) += tmp * s;
1327 %}
1328 %}
1329 EOF
1330 Doc => '
1331 =for ref
1332  
1333 Attractive potential for molecule-like constructs.
1334  
1335 C<attract> is used to calculate
1336 an attractive force for many
1337 objects, of which some attract each other (in a way
1338 like molecular bonds).
1339 For use by the module L<PDL::Graphics::TriD::MathGraph>.
1340 For definition of the potential, see the actual function.
1341 '
1342 );
1343  
1344 pp_done();
« blib/lib/PDL/Core.pm ↑ Summary blib/lib/PDL/Reduce.pm »