Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #2116

Re: designing a data structure in C for PS paths.

Show all headers | View raw

[luser- -droog <mijoryx@yahoo.com>, 2014-12-09 10:49]
> On Tuesday, December 9, 2014 12:40:16 PM UTC-6, luser- -droog wrote:
> > On Tuesday, December 9, 2014 12:08:56 PM UTC-6, luser- -droog wrote:
> > > On Tuesday, December 9, 2014 7:49:05 AM UTC-6, Carlos wrote:
> > > > On 09/12/2014 8:32, luser- -droog wrote:
> > > > >
> > > > > Sure. I think I was using confusing terminology. I was using
> > > > > the same word 'path' to refer to a subpath (a sequence of
> > > > > `lineto` and `curveto` beginning with `moveto`, possibly
> > > > > ending with `closepath`), the currentpath (which can contain
> > > > > many subpaths), and the graphics-state stack.
> > > > >
> > > > > If I were to make the 'path' out of stacks then that would
> > > > > separate it from the rest of the graphics state, and I would
> > > > > need a top-level stack for `gsave/grestore` to operate on.
> > > > > The elements of the top-level path stack would be "normal"
> > > > > path stacks, the elements of which would be "subpath" stacks,
> > > > > the elements of which would be path operations (moveto, line,
> > > > > curveto, closepath).
> > > > >
> > > > 
> > > > OK, but if the elements of the "normal" path were the
> > > > operations themselves (just the concatenated operations of all
> > > > subpaths, without structuring), it would be conceptually the
> > > > same, right?
> > > 
> > > Yes, I suppose so. I think it would make `closepath` O(n),
> > > though, since it now has to search for the most recent
> > > `moveto`, whereas the two-level structuring makes it
> > > easier to find (and O(1)).
> > 
> > Hm. Maybe not `closepath` itself, if you're just accumulating the
> > data, but at some point during processing, all the `closepath`s
> > must be associated with `moveto`s to define the subpaths. If you
> > `stroke` the path, it must be processed several times: dashing,
> > tracing the outline, clipping, filling.

To avoid searching back on closepath, you can keep the subpath starting
point and angle in a variable, and on closepath "lineto" it (the stored
angle is to draw the join). On each path appending operation set the
variable if it's empty, and clear it after each closepath or moveto;
that should be enough for it to always hold the current subpath's
starting point.

> 
> On third thought, goddamit you're right!
> 
> My implementations of all these other processing steps don't make use
> of the structuring at all! They use knowledge of the element
> dictionaries, but they iterate through the current path using
> `pathforall` or xpost's non-standard `devpathforall` which skips the
> `transform/itransform` sandwich.
> 
> They can indeed be flat. Nice catch, dude.

I take no credit for that; it was just you using the old "Rubber Duck"
technique :)  (See http://c2.com/cgi/wiki?RubberDucking)

I guess structuring the path in subpaths could make sense if you
precalculate some values (bounding box, whether it's closed...) and
want to associate them with the subpath, or if your internal
representation requires it. But it's not necessary to do so---that's
what I wanted to make sure and you did.

-- 

Back to comp.lang.postscript | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:27 -0800
  Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:38 -0800
  Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-07 22:09 -0800
    Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-08 15:53 +0100
      Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-08 23:32 -0800
        Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-09 14:49 +0100
          Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:08 -0800
            Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:40 -0800
              Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:49 -0800
                Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-11 00:18 +0100

csiph-web