Hi, Chris.
I have updated the two pnpolyfill functions as you listed below and the
documentation of all of the poly* routines to reflect the difference
between the pnpoly and the polyfill approach to determining set membership.
Before I submitted that patch, I wanted to take a stab at implementing
pnpoly in PP. Below is my first attempt.
pp_def('pnpoly_pp',
HandleBad => 1,
Pars => 'x(m,n); y(m,n); px(k); py(k); int [o] msk(m,n)',
Code => '
int a, b, i, j, c, nvert;
nvert = $SIZE(k);
#define TESTX $x(m=>a,n=>b)
#define TESTY $y(m=>a,n=>b)
#define VERTX(q) $px(k=>q)
#define VERTY(q) $py(k=>q)
for(b=0;b<$SIZE(n);b++) {
for(a=0;a<$SIZE(m);a++) {
c = 0;
for(i=0,j=nvert-1;i<nvert;j=i++) {
if( ((VERTY(i)>TESTY) != (VERTY(j)>TESTY)) &&
(TESTX < (VERTX(j)-VERTX(i)) *
(TESTY-VERTY(i)) / (VERTY(j)-VERTY(i)) + VERTX(i)) )
c = !c;
}
$msk(n=>b,m=>a) = c;
}
}
#undef TESTX
#undef TESTY
#undef VERTX(q)
#undef VERTY(q)
'
);
I also did a quick benchmark:
my $px = pdl(3,15,9);
my $py = pdl(3,3,9);
my $im = zeroes(20, 11);
my $ps = $px->cat($py)->xchg(0,1);
cmpthese(5e4,{
'pnpoly' => sub{pnpoly($im->xvals,$im->yvals,$px,$py)},
'pnpoly_pp' => sub{PDL::pnpoly_pp($im->xvals,$im->yvals,$px,$py)},
'polyfill' => sub{polyfill($im,$ps,1)}
});
Rate pnpoly pnpoly_pp polyfill
pnpoly 5241/s -- -72% -95%
pnpoly_pp 19011/s 263% -- -82%
polyfill 106383/s 1930% 460% --
There is a drastic improvement (~2.5x) over the current pnpoly
implementation, but it still lags well behind the polyfill in both runtime
and memory consumption. I was thinking that it might be possible to get
better runtime by making a function which operates on a single row and
using a threadloop in pnpoly_pp to run it over the image. Do you think
there would be much utility in that? I have a feeling most of the execution
time is in the allocation of x/yvals on the Perl call to pnpoly_pp, but I
was curious about what others' experience has been with something like this.
I haven't ever created test cases before and I didn't see a guide on the
PDL website, what are the sorts of things that are usually tested for?
Many thanks.
- Tim
On Sun, Jun 17, 2012 at 12:55 PM, chm <[email protected]> wrote:
> Hi Tim-
>
> Here are some candidate versions for pnpolyfill
> and pnpolyfillv with some minor cleanup and
> fixes including lvalue subroutine declaration.
>
> sub PDL::pnpolyfill {
>>
>> my ($im, $ps, $col) = @_;
>> barf("ps must contain pairwise points.\n") unless $ps->getdim(0) == 2;
>> barf("color not specified.\n") unless $col;
>> $im->where(pnpoly($im->xvals, $im->yvals, $ps->using(0,1))) .= $col;
>> }
>>
>> sub PDL::pnpolyfillv :lvalue {
>>
>> my ($im, $ps) = @_;
>> barf("ps must contain pairwise points.\n") unless $ps->getdim(0) == 2;
>> return $im->where(pnpoly($im->xvals, $im->yvals, $ps->using(0,1)));
>> }
>>
>
> --Chris
>
>
> On 6/17/2012 9:03 AM, chm wrote:
>
>> Hi Tim-
>>
>> Thanks for the patch.
>>
>> After further consideration, how about we implement
>> a pnpolyfill and pnpolyfillv per your original
>> approach rather than coupling the two versions?
>>
>> Where I'm going with this is that, ideally, we would
>> have a PP implementation of the pnpoly stuff which
>> would have good performance and the better algorithm.
>>
>> All that would be needed are the two new routines
>> and some pnpoly cases for t/image2d.t in the PDL
>> test suite.
>>
>> --Chris
>>
>> On 6/16/2012 3:25 PM, Tim Haines wrote:
>>
>>> Hi, Chris.
>>>
>>> I updated the documentation for polyfill and polyfillv, added the Perl
>>> subroutine PDL::polyfill, and added the pnpoly option to polyfill and
>>> polyfillv. I have attached the git diff file generated against the latest
>>> repository. It builds and tests without issue against Perl 5.14.2 on
>>> Ubuntu
>>> 12.04 x86_64.
>>>
>>> Many thanks.
>>>
>>> - Tim
>>>
>>
_______________________________________________
Perldl mailing list
[email protected]
http://mailman.jach.hawaii.edu/mailman/listinfo/perldl
