path data structure

[luser- -droog]

I've started writing up a graphics package in postscript,
http://code.google.com/p/xpost/source/browse/g.ps
and I'm not sure of the best way to represent a path.

My first thought was to simulate a linked-list with arrays.

move: [ x y /moveto [...] ]
next element ___^
line: [ x y /lineto [...] ]
curve: [ x y x y x y /curveto [...] ]

So the number of args is length-2. The *next* pointer is dup length 1 sub get.
And a tail pointer is relatively easy, dup length 1 sub 1 getinterval.

But something in me doesn't like using arrays like this. It's too fiddly.

So I'm think maybe it should be in a dict with integer keys.

/path <<
0 <<... first subpath ...>>
1 <<... second subpath ...>>
>> def

/subpath <<
0 << /type /moveto /args [ x y ] >>
1 << /type /lineto /args [ x y ] >>
2 << /type /curveto /args [ x y x y x y ] >>
>> def

I suppose one way to determine which is better is to pick one,
start coding, and see what trouble I get into. But, uh,
has anybody else already done that and come to some conclusions?

[luser- -droog]

On Friday, August 9, 2013 10:19:23 PM UTC-5, luser- -droog wrote:
> I've started writing up a graphics package in postscript,
>
> http://code.google.com/p/xpost/source/browse/g.ps
>
> and I'm not sure of the best way to represent a path.
>
> My first thought was to simulate a linked-list with arrays.
>
> move: [ x y /moveto [...] ]
> next element ___^
> line: [ x y /lineto [...] ]
> curve: [ x y x y x y /curveto [...] ]
>
> So the number of args is length-2. The *next* pointer is dup length 1 sub get.
> And a tail pointer is relatively easy, dup length 1 sub 1 getinterval.
>
> But something in me doesn't like using arrays like this. It's too fiddly.
>

> So I'm thinking maybe it should be in a dict with integer keys.

>
> /path <<
> 0 <<... first subpath ...>>
> 1 <<... second subpath ...>>
> >> def
>
> /subpath <<
> 0 << /type /moveto /args [ x y ] >>
> 1 << /type /lineto /args [ x y ] >>
> 2 << /type /curveto /args [ x y x y x y ] >>
> >> def
>
>
> I suppose one way to determine which is better is to pick one,
> start coding, and see what trouble I get into. But, uh,
> has anybody else already done that and come to some conclusions?

Alright, here goes.

% path == <<
% 0 << subpath0 >>
% 1 << %subpath1
% 0 << elem0 /move >> %first elem must be /move
% 1 << elem1 >>
% >>
% >>
% A /move element will always start a new subpath
% Any other element appends to the last subpath
%
/addtopath { % << /data [...] /cmd /... >> <<path>>
dup length 0 eq {
1 index /cmd get /move eq {
<< 0 4 3 roll >> % new subpath % <path> <subpath>
0 exch put
}{
/addtopath cvx /nocurrentpoint signalerror
} ifelse
}{
1 index /cmd get /move eq {
dup length 3 2 roll % <path> n <elem>
<< 0 3 2 roll >> % new subpath % <path> n <<0 <elem>>>
}{
dup length 1 sub get % <elem> <subpath>
dup length 4 3 roll put
} ifelse
} ifelse
} def

% x y moveto -
% set current point to (x,y)
/moveto {
transform
2 copy
/itransform cvx
graphicsdict /currentgstate get /currentpoint get 0 3 getinterval astore
graphicsdict /currentgstate get exch /currentpoint exch put
2 array astore
<< /data 3 2 roll /cmd /move >> graphicsdict /currentpath get addtopath
} def

And, I suppose it's unnecessary to save the currentpoint as a separate
element in the gstate. The /currentpoint procedure can just look at
the last element in the path.

But, all in all, this seems like it's a reasonable way to go.