Fierce and scary geometry algorithm for ‘ParallelPath’

[jdawiseman...@gmail.com]

Algorithm question, the problem being illustrated by:
http://www.jdawiseman.com/2019/20190400_ParallelPath.ps
http://www.jdawiseman.com/2019/20190400_ParallelPath.pdf
http://www.jdawiseman.com/2019/20190400_ParallelPath.png

I want a decorative effect like that in the linked ps, pdf, and png.

That is currently being achieved by starting with the target path, and clipping to it. Then setlinewidth thick and setgray black, stroke; setlinewidth a bit thinner and setgray white, stroke; setlinewidth a bit thinner and setgray black, stroke; etc.

Done that way the on-screen the PDF looks good, and if converted to a bitmap with GraphicConverter, still looks good. Happiness!

But if printed on some actual printers, the outermost black line seems thicker than the others. Not happy. This is likely to be a printer artefact, the printer being more aggressive about spreading white than about spreading black. That would affect one side of the outermost line, but two sides of the others — making the outermost seem thicker. (Though the cause might be different: I don’t know.)

One way to fix this would be to trace and stroke directly the parallel lines, rather than as the gap between a black stroke and a white stroke. That would require a routine, perhaps called ParallelPath, which would take two parameters: a distance in points; and a boolean = left|right. ParallelPath would walk round the currentpath, replacing it with a new path the parameters’s distance to the left|right, as if holding out a left|right arm that far away from the body.

Seems like a fierce and scary algorithm to write. If you have already written such an algorithm, or something like it, please share.

[edspike...@gmail.com]

With gs and -r600 the outer most and inner most oval in the 9 edges are jagged and appear thicker. The inner ones are not. Perhaps you can write the outside line in white instead of black.

[jdawiseman...@gmail.com]

> Perhaps you can write the outside line in white instead of black.

The problem isn’t the thickest line. The problem is the thinnest black, one edge of which is a clip rather than an overpaint.

[jdawiseman...@gmail.com]

Perhaps the algorithm could make pieces, and somehow sew them together.
• For a straight line, the left-hand-out line is easy to compute.
• For a point, at which the angle of turn is known, it’s a part circle.
• For a curve, one could flattenpath. Or, neater, use the position and derivatives at the endpoints with https://groups.google.com/forum/#!topic/comp.lang.postscript/3RIq0Jnwrbo to make it’s curve. Perhaps recurse into splits of the original curve, until it’s not too curvy.

That gives a list of pieces. That can be cut at intersections, but it’s not yet obvious to me how to decide what to keep and what to bin.

All very fiddly.

[luser droog]

I just had a crazy thought: what if we could abuse 'strokepath' to do the work?
In a way, this is similar to the job 'strokepath' has to do. It takes a single
curve and generates two offset curves on either side (plus caps and joins).

[jdawiseman...@gmail.com]

> I just had a crazy thought: what if we could abuse 'strokepath' to do the work?
> In a way, this is similar to the job 'strokepath' has to do. It takes a single
> curve and generates two offset curves on either side (plus caps and joins).

PLRM3, p700:
> The path produced by strokepath … is not suitable for stroke, as it may contain interior segments or disconnected subpaths produced by strokepath’s conversion from stroke to outline.

Not strokeable, alas.

[luser droog]

Perhaps so, at least not directly. But it may be an easier job to clean up
the path it creates rather than doing the whole job some other way.

[luser droog]

It's definitely not the desired result out of the box, but the information
is in there.

%!

144 setlinewidth
300 400 200 0 360 arc strokepath 1 setlinewidth stroke
showpage quit

[luser droog]

Got something that appears to work for simple paths. Probably easy to make
it go wrong.

I started by drawing a circle, flattening and dumping the path.
Then I stroked the path and dumped and noticed that every other
subpath was either an "extrusion" of the original line or a join.
So I chop up the path into subpaths, take length-2 intervals and
pull out the interesting half and then juggle the points in the
right order.

$ cat stroke.ps
%!

/args { -1 1{-1 roll =only( )print}for } def
/dumppath {
{ 2 args (moveto) = }
{ 2 args (lineto) = }
{ 6 args (curveto) = }
{ (closepath) = }
pathforall
} def

/script {

300 400 200 0 360 arc

dumppath/ =

flattenpath
dumppath/ =

144 setlinewidth
strokepath
dumppath/ =

1 setlinewidth
stroke
} def

/path {
[
{ [ 3 1 roll }
{ }
{ }
{ ] } pathforall
]
} def

/righthand {
[
path
0 2 2 index length 2 sub { % ...p i
2 copy 2 getinterval % ...p i p_i
0 get 0 4 getinterval % ...p i p_ir
3 1 roll pop % ... p_ir p
} for
pop
]
} def

/lefthand {
[
path
0 2 2 index length 2 sub { % ...p i
2 copy 2 getinterval % ...p i p_i
0 get 4 4 getinterval % ...p i p_il
aload pop 4 2 roll 4 array astore
3 1 roll pop
} for
pop
]
} def

/draw {
dup 0 get aload pop 4 2 roll moveto lineto
1 1 index length 1 sub getinterval
{
aload pop 4 2 roll lineto lineto
} forall
} def

/strokeable {
flattenpath
strokepath
righthand
lefthand
newpath
stack
draw draw
} def

499.999 399.999 moveto
499.999 405.112 lineto
498.962 420.452 lineto
495.931 440.309 lineto
491.003 459.473 lineto
484.28 477.848 lineto
475.858 495.331 lineto
465.839 511.822 lineto
454.324 527.219 lineto
441.416 541.42 lineto
427.215 554.329 lineto
411.818 565.843 lineto
395.327 575.862 lineto
377.843 584.284 lineto
359.469 591.007 lineto
340.304 595.935 lineto
320.447 598.966 lineto
305.108 599.998 lineto
299.999 599.998 lineto

50 setlinewidth
strokeable

1 setlinewidth
stroke
showpage quit

571.755 399.999 moveto
571.755 405.112 lineto
%427.757 405.112 lineto
%427.757 399.999 lineto
%closepath
%571.755 405.112 moveto
%571.755 405.112 lineto
%571.834 409.965 lineto
%499.999 405.112 lineto
%closepath
571.834 409.965 lineto
570.797 425.304 lineto
%427.126 415.599 lineto
%428.163 400.259 lineto
%closepath
%570.797 425.304 moveto
%570.599 428.304 lineto
%570.136 431.313 lineto
%498.962 420.452 lineto
%closepath

stroke

showpage quit

[jdawiseman...@gmail.com]

Good approach.

But:
• Circle is a particularly easy case.
• I dislike flattenpath, as it causes slight corners where curve meets a line or curve that ought to be continuous.

Algorithm for latter.
◊ For a Bézier cubic, calculate a straightness, which might the range of angles of tangents.
◊ If that bigger than, say, 22½°, recurse.
◊ Calculate end points of left hand, and partial derivatives wrt to the z of the curve long which walking, and double derivs.
◊ Have ApproximatingCurve make that into a Bézier cubic. https://groups.google.com/forum/#!topic/comp.lang.postscript/3RIq0Jnwrbo

There’s still a lot of awkwardness of sewing these pieces together. E.g., in a serif of a font, there might be many dozens of pieces to discard.

[luser droog]

I had an emotional reaction to your response, but sat on it and studied
it, and with more distance I'm beginning to see what you're getting at.

Your sketch is more complicated but probably more correct.
ISTM for parts of the image, we want something like a *morph* between
the inner curve and the outer curve. So, running along two curves
and producing a new curve place at a specified proportionate
distance between the two, and comprising a shape that is a
specified proportion of the shapes of the two source curves.

If one of the two source curves can be degenerate then that
gives: growing to infinity, shrinking to zero, interpolating
between curves.

I think I should read up on 'upath' which I think handles some of the
gymnastics I've been doing with paths. Writing a function to take
two paths can't really work with the currentpath as naively as I've
grown used to doing.

[Carlos]

On 20.4.2019 11:44, jdawiseman...@gmail.com wrote:
>> Perhaps you can write the outside line in white instead of black.
>
> The problem isn’t the thickest line. The problem is the thinnest black, one edge of which is a clip rather than an overpaint.
>

I think what he means is, if your last stroke is thin white, then *that*
stroke would have a clip edge, but it doesn't matter, because it's
invisible. The outermost black line would have overpaint on both sides.
Depending on the width of the outermost white stroke the glyph's contour
will appear more or less distorted though.
--

[jdaw1]

Sorry about delay in replying — original post was from wrong gmail account, and there‘s no way to stop it being my browser’s default. Sigh.

On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> … we want something like a *morph* between

> the inner curve and the outer curve.

No. The outer curve is merely a version of all the curves. Wha’s wanted is derived from the inner curve only.

On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> I think I should read up on 'upath' which I think handles some of the
> gymnastics I've been doing with paths. Writing a function to take
> two paths can't really work with the currentpath as naively as I've
> grown used to doing.

Please report back.

Sorry about delay in replying — original post was from wrong gmail account, and there‘s no way to stop it being my browser’s default. Sigh.

On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> … we want something like a *morph* between

> the inner curve and the outer curve.

No. The outer curve is merely a version of all the curves. Wha’s wanted is derived from the inner curve only.

On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> I think I should read up on 'upath' which I think handles some of the
> gymnastics I've been doing with paths. Writing a function to take
> two paths can't really work with the currentpath as naively as I've
> grown used to doing.

Please report back.

On Monday, 29 April 2019 01:40:45 UTC+1, Carlos wrote:
> I think what he means is, if your last stroke is thin white, then *that*
> stroke would have a clip edge, but it doesn't matter, because it's
> invisible. The outermost black line would have overpaint on both sides.
> Depending on the width of the outermost white stroke the glyph's contour
> will appear more or less distorted though.

Agreed.

[luser droog]

On Wednesday, June 19, 2019 at 5:04:13 PM UTC-5, jdaw1 wrote:
> Sorry about delay in replying — original post was from wrong gmail account, and there‘s no way to stop it being my browser’s default. Sigh.
>
> On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> > … we want something like a *morph* between
> > the inner curve and the outer curve.
>
> No. The outer curve is merely a version of all the curves. Wha’s wanted is derived from the inner curve only.
>
> On Sunday, 28 April 2019 21:33:08 UTC+1, luser droog wrote:
> > I think I should read up on 'upath' which I think handles some of the
> > gymnastics I've been doing with paths. Writing a function to take
> > two paths can't really work with the currentpath as naively as I've
> > grown used to doing.
>
> Please report back.
>

I didn't do any more after posting that, but I did actually do a little
bit with the program just before I posted that. But rereading the whole
thread, I think my code doesn't address the actual problem you were
having. And my "algorithm" boils down to roughly the same thing you were
already doing. 'stroke' uses 'strokepath'.

I should also point out that this code is very implementation dependant
and may fail to work with any other version of ghostscript which does
'strokepath' differently or any other postscript interpreter which doesn't
produce a path that's exactly of the expected form.

The new features here over the previous code are that multiple parallel
curves can be created. Rather like the fact that the result of 'strokepath'
is not meant to be strokeable, my function 'strokeable' produced a result
which could be 'stroke'd but not 'strokeable'd again.

Another side note: you should not be afraid of 'flattenpath' mostly because
'strokepath' (and hence 'stroke') already does that. Actually computing
a real offset curve is a hard problem AIUI, but offsetting a sequence of
line-segments is really easy. So PostScript has already been taking that
shortcut this whole time.

Did you experiment at all with adjusting 'setflat' on the original? That
might influence the sharpness of the clipped edges.

Anyway, the new function 'strokes' takes two arrays for left widths and
right widths and replaces the current path with corresponding left and
right offsets.

/pathdraw {
{
dup 0 2 getinterval aload pop moveto
2 1 index length 2 sub getinterval
0 2 2 index length 2 sub { % sp i
2 copy 2 getinterval aload pop lineto
pop
} for
pop
closepath
} forall

/strokeleftpath {
flattenpath
strokepath
lefthand
} def

/strokerightpath {
flattenpath
strokepath
righthand
} def

/strokes {
{right left}{exch def}forall
[
right {
gsave
setlinewidth
strokerightpath
grestore
} for
left {
gsave
setlinewidth
strokeleftpath
grestore
} for
]
newpath
{ draw } forall
} def

300 400 200 0 360 arc

{ 2 10 100 }{ 2 20 100 }strokes

1 setlinewidth
stroke
showpage quit

{

300 400 200 0 360 arc

50 setlinewidth
strokeable

strokeable
1 setlinewidth
stroke
showpage

} pop


/section {

499.999 399.999 moveto
499.999 405.112 lineto
498.962 420.452 lineto
495.931 440.309 lineto
491.003 459.473 lineto
484.28 477.848 lineto
475.858 495.331 lineto
465.839 511.822 lineto
454.324 527.219 lineto
441.416 541.42 lineto
427.215 554.329 lineto
411.818 565.843 lineto
395.327 575.862 lineto
377.843 584.284 lineto
359.469 591.007 lineto
340.304 595.935 lineto
320.447 598.966 lineto
305.108 599.998 lineto
299.999 599.998 lineto

} def

[luser droog]

Oops. I remembered wrong. The two arrays are not lists of lengths, but
collected 'for' loop parameters.

One other problem with this code is apparent if you view the resulting
image. The paths aren't closed even though the seed path was closed.

> $ cat stroke.ps
> %!
>
> /args { -1 1{-1 roll =only( )print}for } def
> /dumppath {
> { 2 args (moveto) = }
> { 2 args (lineto) = }
> { 6 args (curveto) = }
> { (closepath) = }
> pathforall
> } def
>

[snip code that wasn't used]

[snip code that was commented out anyway]

[luser droog]

A little progress reveals a big setback ...

I added some stuff to deal with closed paths. It worked with the single
path arc from my first test, but fails spectacularly when I tried with
a '9'. Using the '9' reveals a completely different, deeper problem.
On sharp turns, the *span* of the new line segment with be very short
with much of the slack taken up by the join between segments.

But my code steals the spans and throws away all the joins! So it doesn't
quite work for a 9. It may be salvageable but I have to dig back into
the 'strokepath' data. So here's my crappy '9':

%!

/args { -1 1{-1 roll =only( )print}for } def
/dumppath {
{ 2 args (moveto) = }
{ 2 args (lineto) = }
{ 6 args (curveto) = }
{ (closepath) = }
pathforall
} def

/path {
[
{ [ 3 1 roll }
{ }
{ }
{ ] } pathforall
]
} def

/isclosed {
false
{ pop pop }
{ pop pop }
{ pop pop pop pop pop pop }
{ pop true }

pathforall
} def

/pathdraw {
{
dup 0 2 getinterval aload pop moveto
2 1 index length 2 sub getinterval
0 2 2 index length 2 sub { % sp i
2 copy 2 getinterval aload pop lineto
pop
} for
pop
closepath
} forall
} def

/righthand {
[
path
0 2 2 index length 2 sub { % ...p i
2 copy 2 getinterval % ...p i p_i
0 get 0 4 getinterval % ...p i p_ir
3 1 roll pop % ... p_ir p
} for
pop

%closed { counttomark 1 sub index = } if

]
} def

/lefthand {
[
path
0 2 2 index length 2 sub { % ...p i
2 copy 2 getinterval % ...p i p_i
0 get 4 4 getinterval % ...p i p_il
aload pop 4 2 roll 4 array astore
3 1 roll pop
} for
pop

%closed { counttomark 1 sub index == } if

]
} def

/draw {
dup 0 get aload pop 4 2 roll moveto lineto
1 1 index length 1 sub getinterval
{
aload pop 4 2 roll lineto lineto
} forall
} def

/strokeable {

/closed isclosed def

flattenpath
strokepath
righthand
lefthand
newpath
stack
draw
draw
} def

/strokeleftpath {

/closed isclosed def

flattenpath
strokepath
lefthand
} def

/strokerightpath {

/closed isclosed def

flattenpath
strokepath
righthand
} def

/strokes {
{right left}{exch def}forall
[
right {
gsave
setlinewidth
strokerightpath
grestore
} for
left {
gsave
setlinewidth
strokeleftpath
grestore
} for
]
newpath

{ pathdraw } forall
} def

%300 400 200 0 360 arc closepath
currentflat 8 div setflat
/Palatino-Roman 296 selectfont
100 100 moveto (9) true charpath
{ 2 5 20 }{ 2 6 20 }strokes

[luser droog]

On Saturday, June 22, 2019 at 5:37:31 PM UTC-5, luser droog wrote:
> On Saturday, June 22, 2019 at 4:54:01 PM UTC-5, luser droog wrote:
> > >
> > > Anyway, the new function 'strokes' takes two arrays for left widths and
> > > right widths and replaces the current path with corresponding left and
> > > right offsets.
> >
> > Oops. I remembered wrong. The two arrays are not lists of lengths, but
> > collected 'for' loop parameters.
> >
> > One other problem with this code is apparent if you view the resulting
> > image. The paths aren't closed even though the seed path was closed.
> >
> > > $ cat stroke.ps
>
> A little progress reveals a big setback ...
>
> I added some stuff to deal with closed paths. It worked with the single
> path arc from my first test, but fails spectacularly when I tried with
> a '9'. Using the '9' reveals a completely different, deeper problem.
> On sharp turns, the *span* of the new line segment with be very short
> with much of the slack taken up by the join between segments.
>
> But my code steals the spans and throws away all the joins! So it doesn't
> quite work for a 9. It may be salvageable but I have to dig back into
> the 'strokepath' data. So here's my crappy '9':
>
> %!

[snip]

Using Calibri looks a little better, although apparently the orientation
is the reverse of what Palatino-Bold uses. I discovered that by doing

/Calibri-Bold 596 selectfont

100 100 moveto (9) true charpath

1 setlinejoin
flattenpath
20 setlinewidth strokepath
%dumppath
0 setlinewidth
stroke showpage

Then the dumppath nicely shows where the joins are (they're the curves).
But I haven't come up with a way to exploit that knowledge yet.
The image shows little hemispheres at each join.

[luser droog]

On Sunday, June 23, 2019 at 5:59:51 PM UTC-5, luser droog wrote:
>
> Using Calibri looks a little better, although apparently the orientation
> is the reverse of what Palatino-Bold uses. I discovered that by doing
>
> /Calibri-Bold 596 selectfont
> 100 100 moveto (9) true charpath
> 1 setlinejoin
> flattenpath
> 20 setlinewidth strokepath
> %dumppath
> 0 setlinewidth
> stroke showpage
>
> Then the dumppath nicely shows where the joins are (they're the curves).
> But I haven't come up with a way to exploit that knowledge yet.
> The image shows little hemispheres at each join.

After seeing a nice example of 'arcto', I rewrote my code to try to get
something where I could drop in an 'arcto' to clean up the output.
Sort of a step sideways. This program exhibits the same problems as the
earlier ones, but it no longer uses the result of 'strokepath' so it's
no longer implementation dependant. Instead it's dependent on the font
glyph itself, expecting several closed paths followed by a lone 'moveto'
at the end.

This program draws the original glyph, then the 'strokepath' scaffolding,
then my curve at the same width in red, then another curve farther out in
blue. The blue one makes it easier to see the problems going on in the red
one.

$ cat stroke1.ps
%!

/closedsubpaths {

[
{ [ 3 1 roll }
{ }
{ }
{ ] }
pathforall
] ]
} def

/div {
dup 0 eq { pop }{//div} ifelse
} def

/perp {
{y1 x1 y0 x0}{exch def}forall
x1 x0 sub y1 y0 sub
exch neg % dx,dy => dy,-dx
2 copy dup mul exch dup mul add sqrt
2 copy div % x y mag y/mag
4 1 roll exch pop div exch % x/mag y/mag
} def


/offsetvectorsbyn {
[ exch
{ %forall subpaths
dup length 2 gt {
[ exch
%pstack()=
0 2 2 index length 4 sub { % A i
2 copy 4 getinterval aload pop % A i x0 y0 x1 y1
perp n mul exch n mul exch % A i dx dy
4 copy pop pop 2 getinterval aload pop % A i dx dy xi yi
exch 4 3 roll add % A i dy yi xi'
3 1 roll add % A i xi' yi'
4 2 roll pop
} for % [ ... A
dup dup length 2 sub 2 getinterval aload pop 2 copy
5 4 roll 0 2 getinterval aload pop
%counttomark 1 sub index counttomark 2 sub index
perp n mul exch n mul exch
exch 4 3 roll add
3 1 roll add
]
}{ pop } ifelse
} forall
]
} def

/drawpath {

{
dup 0 2 getinterval aload pop moveto
2 1 index length 2 sub getinterval

0 2 2 index length 1 sub { % A i

2 copy 2 getinterval aload pop lineto
pop
} for pop
closepath
} forall
} def

/offsetpath {
/n exch def
closedsubpaths
%pstack quit
offsetvectorsbyn
newpath
drawpath
} def

/Calibri-Bold 596 selectfont
100 100 moveto (9) true charpath

gsave stroke grestore
20 setlinewidth
strokepath
1 setlinewidth
stroke

1 0 0 setrgbcolor

100 100 moveto (9) true charpath

flattenpath
10 offsetpath
3 setlinewidth
stroke

0 0 1 setrgbcolor

100 100 moveto (9) true charpath

flattenpath
20 offsetpath
stroke

showpage quit

[luser droog]

Much better now. Still something fishy in the lower left corner.
This time I take 3 points at a time, get the 2 normals and average
them to get a normal to offset the point.

Next step will be consulting the angle between these two vectors
to determine whether to attempt a join.

$ cat stroke1.ps
%!

/closedsubpaths {
[
{ [ 3 1 roll }
{ }
{ }
{ ] }
pathforall
] ]
} def

/drawpath {
{
dup 0 2 getinterval aload pop moveto
2 1 index length 2 sub getinterval
0 2 2 index length 1 sub { % A i
2 copy 2 getinterval aload pop lineto
pop
} for pop
closepath
} forall
} def

/div {
dup 0 eq { pop }{//div} ifelse
} def

/normalize {

2 copy dup mul exch dup mul add sqrt
2 copy div % x y mag y/mag
4 1 roll exch pop div exch % x/mag y/mag
} def

/perp {
{y1 x1 y0 x0}{exch def}forall
x1 x0 sub y1 y0 sub
exch neg % dx,dy => dy,-dx

normalize
} def

/v*n {

n mul exch n mul exch % A i dx dy

} def

/v+v {
exch 4 3 roll add % dy yi xi'
3 1 roll add % xi' yi'

} def


/offsetvectorsbyn {
[ exch
{ %forall subpaths
dup length 2 gt {
[ exch
%pstack()=
0 2 2 index length 4 sub { % A i
2 copy 4 getinterval aload pop % A i x0 y0 x1 y1

perp v*n

4 copy pop pop 2 getinterval aload pop % A i dx dy xi yi

v+v

4 2 roll pop
} for % [ ... A
dup dup length 2 sub 2 getinterval aload pop 2 copy
5 4 roll 0 2 getinterval aload pop
%counttomark 1 sub index counttomark 2 sub index

perp v*n
v+v
]
}{ pop } ifelse
} forall
]
} def

/first2 {
0 2 getinterval
} def

/first4 {
0 4 getinterval
} def

/last2 {

dup length 2 sub 2 getinterval

} def

/last4 {
dup length 4 sub 4 getinterval
} def

/spill {
aload pop
} def

/offsetcenterpoint { % x_1 y_1 x0 y0 x1 y1 -> x0' y0'
4 copy perp % xy_1 xy0 xy1 xy01^
8 2 roll pop pop % xy01^ xy_1 xy0
4 copy perp % xy01' xy_1 xy0 xy_10^
8 6 roll v+v normalize % xy_1 xy0 xy^%
v*n v+v 4 2 roll pop pop
} def

/offsetvectorsbynwithjoins {
[ exch
{

dup length 2 gt {
[ exch

dup last2 spill 2 index first4 spill
offsetcenterpoint 3 2 roll
0 2 2 index length 6 sub {
2 copy 6 getinterval spill
offsetcenterpoint 4 2 roll
pop
} for
dup last4 spill 4 index first2 spill
offsetcenterpoint 3 2 roll
pop
]
}{ pop } ifelse

} forall
]
} def

/offsetpath {
/n exch def
closedsubpaths
%pstack quit

%offsetvectorsbyn
offsetvectorsbynwithjoins

[luser droog]

"Low Res Illustration"

Slight change to better illustrate what it's doing and what's going wrong.
I set the flatness tolerance really high so we get choppy curves made out
of fewer line segments. And I draw both sides of the offset curve.

So we can see that taking 3 points and averaging the normals works
tolerably (although it's not ideal) for large angles. But for small
angles with lots of points, it generates these weird inner "ears".

/offsetcenterpoint { % ... ( ? ?? ) x_1 y_1 x0 y0 x1 y1 -> x0' y0'

4 copy perp % xy_1 xy0 xy1 xy01^
8 2 roll pop pop % xy01^ xy_1 xy0
4 copy perp % xy01' xy_1 xy0 xy_10^
8 6 roll v+v normalize % xy_1 xy0 xy^%
v*n v+v 4 2 roll pop pop
} def

/offsetvectorsbynwithjoins {
[ exch
{
dup length 2 gt {
[ exch

dup dup last2 spill 2 index first4 spill
offsetcenterpoint 4 2 roll
pop

0 2 2 index length 6 sub {
2 copy 6 getinterval spill
offsetcenterpoint 4 2 roll
pop
} for

dup dup last4 spill 4 index first2 spill
offsetcenterpoint 4 2 roll
pop pop

]
}{ pop } ifelse
} forall
]
} def

/offsetpath {
/n exch def
closedsubpaths

%dup ==
%pstack quit
%offsetvectorsbyn
offsetvectorsbynwithjoins
%dup ==
newpath
drawpath
} def

currentflat 16 mul setflat
2 setlinejoin

/Calibri-Bold 596 selectfont
100 100 moveto (9) true charpath
gsave stroke grestore
20 setlinewidth
strokepath
1 setlinewidth
stroke

1 0 0 setrgbcolor
100 100 moveto (9) true charpath
flattenpath

gsave

10 offsetpath
3 setlinewidth
stroke

grestore
-10 offsetpath

stroke

0 0 1 setrgbcolor
100 100 moveto (9) true charpath
flattenpath

gsave
20 offsetpath
stroke
grestore
-20 offsetpath
stroke


showpage quit

[luser droog]

I now have code to detect and surgically replace the ears. All that remains
(I think) is fabricating the replacement points. I think the midpoint of
the outer two points of the ear will work, but we'll have to see what it
looks like.

It detects ears by checking the angular change at each point. Any runs of
two or more points at around 180 degrees +-30 are flagged as ears.
It uses a run-length encoding of the flagged ears to guide the snipping
and recomposition of the array of points representing the path.

I tried just running through the points and eliminating single points but
the result was ugly, and even after 12 iterations the ears remained.

I've reduced the output to one red curve and one blue curve. Output from the
ear detection:

[[180.279633 2.00844574 0.224014282 3.93617249 0.410858154 4.97277832 0.176799774 8.12938309 1.70695114 8.78822327 0.701179504 4.62898636 3.62308717 358.79422 4.60778809 3.89904785 1.46203613 3.70935059 2.70690918 8.35592651 179.719986 179.853 163.023392 17.1131592 3.13320923 4.04489136 0.712005615 7.02740479 178.143555 189.396683 169.974152 175.828217 177.600082 182.887177 3.90716553 3.72990417 0.349945068 3.03895569 1.14590454 3.84664917 2.58439636 6.73135376 8.44741821 6.67147827 7.84288025 5.83366394 5.58996582 3.79476929 28.0493774 25.0266438 3.40968704 6.83194065 354.626678 356.853027 5.40203857 4.52456665 10.3373413 10.7698364 11.151123 8.07275391 7.5569458 4.2388916 6.66830444 6.71658325 7.65461731 8.71060181 10.1319275 7.57539368 4.35528564 5.24961853 3.06735229 3.64326477 7.19722 5.72450256 8.46220398 6.24998474 7.22940826 3.24757385 5.05388641 1.93174744 3.18948364 1.1917038 1.92375946 179.914886] [24.9522095 3.4453125 1.15289307 7.15319824 2.39425659 5.74685669 7.67160034 2.6307373 9.53170776 357.162567 9.54965782 3.18024826 10.4573441 3.06572342 8.25476837 0.406646729 6.06898499 1.02275085 5.94130707 0.709129333 9.92462158 0.1537323 7.91809082 5.94891357 0.386489868 8.43563843 0.587463379 7.52613831 0.184005737 7.20550537 23.6573792]]
[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]
[[20 3 5 6] []]
ear: [269.057098 111.948341 266.341736 110.966988 256.754395 108.264374]
ear: [190.533295 104.847809 188.945831 105.091476 187.242645 105.257896 177.905411 106.817024 169.435318 108.778946 168.050308 109.137222]
[[180.218292 2.01687622 0.0436096191 3.96809387 0.000625610352 5.02503967 1.02964401 8.28387833 4.94224167 8.95646858 2.01691246 4.68037891 3.62996459 357.561401 5.73220825 4.60473633 1.73522949 4.36611938 4.63208 224.63446 182.775711 177.832932 171.512054 179.457596 3.63217163 4.9083252 1.19036865 211.948822 181.631485 15.9331589 12.1903801 9.78577709 10.0365582 184.513687 6.11184692 3.96517944 0.330780029 2.85295105 1.11465454 3.59619141 2.53746033 6.36784363 7.94700623 6.40586853 7.37348938 5.58110046 5.29910278 3.65362549 31.8732605 330.994293 3.81921959 8.07155323 354.276306 356.622803 5.46618652 5.45623779 14.0754089 20.9076843 19.5395203 10.9311829 9.1210022 4.45806885 7.52981567 7.90560913 9.35531616 11.4260101 13.7461395 8.98088074 4.84397888 5.29974365 3.1807251 3.8860321 8.62216187 7.07295227 12.054184 8.52066 9.13140106 3.43019104 5.57831573 1.92396545 3.34073639 1.19281 1.97290039 179.966583] [23.7032623 3.42803955 1.44546509 7.04550171 2.96081543 5.74115 7.50161743 3.640625 9.2638855 356.477173 9.26171112 4.25038528 10.0725632 3.95078659 8.00562286 1.3163147 5.93536377 0.400894165 5.81770325 1.5835495 9.53955841 1.62148285 7.65376282 5.90643311 1.53013611 8.18559265 1.32310486 7.3684082 0.99836731 7.04521179 22.927063]]
[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]
[[20 4 3 2] []]
ear: [265.617462 121.338165 263.495483 120.553375 254.480942 118.00251 241.449 115.441101]
ear: [211.08754 113.391441 191.306641 114.817863]

So it's finding ears in the red curve that I can't even see.
There also appears to be an ear "around the corner" from the last point to
the first point of the first subpath of both curves which my detector does
not detect ATM.

/offsetvectorsbynusingavg {

[ exch
{
dup length 2 gt {
[ exch
dup dup last2 spill 2 index first4 spill
offsetcenterpoint 4 2 roll
pop
0 2 2 index length 6 sub {
2 copy 6 getinterval spill
offsetcenterpoint 4 2 roll
pop
} for
dup dup last4 spill 4 index first2 spill
offsetcenterpoint 4 2 roll
pop pop
]
}{ pop } ifelse
} forall
]
} def

/atan {
2 copy 0 eq exch 0 eq and { pop }{ //atan } ifelse
} def

/recenter {
%dup 180 gt { 360 sub } if
%180 sub
cvi %180 mod
} def

/dumpangles false def

/checkangle { % [inner 3 points]
aload pop
{y2 x2 y1 x1 y0 x0}{exch def}forall
/dx1 x1 x0 sub def
/dy1 y1 y0 sub def
/dx2 x2 x1 sub def
/dy2 y2 y1 sub def
dumpangles { x1 =only ( )print y1 =only ( )print } if
dy2 dx2 atan recenter dumpangles { dup =only ( )print } if
dy1 dx1 atan recenter dumpangles { dup =only ( )print } if
%2 copy 0 eq exch 0 eq or {
%pop pop false
%dumpangles { (false)= } if
%}{
%2 copy add dup =only ( )print
%dup 180 lt exch -180 gt and
%abs 300 lt
%3 1 roll
sub dumpangles { dup =only ( )print } if
abs 180 lt %and
dumpangles { dup = } if
%} ifelse
} def

/offsetpointbyavgperp { % x y [ xy0 xy1 .. xyn ]
%dup 8 last 6 first checkangle
true
{
0 0 3 2 roll
0 2 2 index length 4 sub { % 0 0 a i
2 copy 4 getinterval aload pop perp % 0 0 a i xy^0
6 4 roll v+v % a i xy^0+00
4 2 roll % 00' a i
pop
} for pop
normalize v*n v+v 4 2 roll
}{ pop pop pop } ifelse
} def

/cat {
2 array astore [ exch { spill } forall ]
} def

/first { %n
0 exch getinterval
} def

/last { %n
1 index length 1 index sub exch getinterval
} def

/offsetvectorsbynusingavgs {

[ exch
{
dup length 2 gt {
[ exch

dup dup 4 last 1 index 6 first dup 2 first spill 4 2 roll cat
offsetpointbyavgperp
dup 2 last 1 index 8 first dup 6 last 2 first spill 4 2 roll cat
offsetpointbyavgperp
pop
0 2 2 index length 10 sub {
2 copy 10 getinterval dup 6 last 2 first spill 3 2 roll
offsetpointbyavgperp
pop
} for
dup dup 8 last dup 4 last 2 first spill 3 2 roll 3 index 2 first cat
offsetpointbyavgperp
dup 6 last dup 2 last spill 3 2 roll 3 index 4 first cat
offsetpointbyavgperp

pop pop
]
}{ pop } ifelse
} forall
]
} def

/filterbyangle {

[ exch
{
dup length 2 gt {
[ exch

dup 2 last 1 index 4 first dup 2 first spill 4 2 roll cat
checkangle { 3 2 roll }{ pop pop } ifelse
0 2 2 index length 6 sub { % A i
2 copy 6 getinterval dup 4 last 2 first spill 3 2 roll
checkangle { 4 2 roll }{ pop pop } ifelse
pop
} for
dup 4 last dup 2 first spill 3 2 roll 3 index 2 first cat
checkangle { 3 2 roll }{ pop pop } ifelse
%pstack()=
pop
]
}{ pop } ifelse
} forall
]
dumpangles { ()= } if
} def

/p-p { % x1 y1 x0 y0
%pstack()=
exch 3 1 roll sub % x1 x0 y1-y0
3 1 roll sub exch % x1-x0 y1-y0
} def

/getvectors {
[ exch
{
[ exch
dup 2 last spill 2 index 2 first spill p-p 3 2 roll

0 2 2 index length 4 sub {

2 copy 4 getinterval spill p-p 4 2 roll
pop
} for
pop
]
} forall
]
} def

/getangles {
getvectors
[ exch
{
[ exch
0 2 2 index length 2 sub {
2 copy 2 getinterval spill exch atan 3 1 roll
pop
} for
pop
]
} forall
]
} def

/getdiffs {
[ exch
{
[ exch
0 2 2 index length 2 sub {
2 copy 2 getinterval spill sub abs 3 1 roll
pop
} for
dup 1 last spill 1 index 1 first spill sub abs exch
pop
]
} forall
]
} def

/isbig {
[ exch
{
[ exch
{
dup 160 gt exch 220 lt and { 1 }{ 0 } ifelse
} forall
]
} forall
]
} def

/findears {
[ exch
{
dup length string exch % s a
0 1 2 index length 1 sub { % s a i
3 copy % s a i s a i
get 3 2 roll exch % s a s i a_i
put
} for pop
} forall
]
[ exch
{
[ exch
{ (\1\1) search not { pop exit } if
length exch pop exch
2 exch
{
dup 0 get 1 ne { exit } if
exch 1 add exch

1 1 index length 1 sub getinterval

} loop
} loop
]
} forall
]
} def

/tail { % n
1 index length 1 index sub getinterval
} def

/snipthisear {
(ear: )=only
dup ==
} def

/snippoly { % [polygon] [ears]
[ 3 1 roll
0 2 2 index length 2 sub { % p e i
2 copy 2 getinterval % p e i ear==[zeros ones]
spill 2 mul exch 2 mul % p e i ones zeros
5 4 roll exch % e i ones p zeros
2 copy tail 3 1 roll first % e i ones p[zeros:$] p[0:zeros]
5 1 roll % p-first e i ones p-tail
exch % p-first e i p-tail ones
2 copy tail 3 1 roll first % p-zeros e i p-tail p-ones
snipthisear % p-zeros e i p-tail p-ones'
4 1 roll 3 1 roll pop % p-zeros p-ones' p-tail e
} for
pop
]
[ exch {spill} forall ]
} def

/dosnips { % [[path][]] [[ears][]]
[ 3 1 roll
0 1 2 index length 1 sub { % p e i
3 copy get % p e i p e_i
3 1 roll exch get % p e e_i p_i
exch dup length 0 eq { % p e p_i e_i
pop 3 1 roll % p_i p e
}{ % p e p_i e_i
snippoly % p e p_i'
3 1 roll % p_i' p e
} ifelse
} for
pop pop
]
} def

/snipears {
dup getangles %dup ==
getdiffs dup ==
isbig dup ==
findears dup ==
dosnips

} def

/offsetpath {
/n exch def
closedsubpaths
%dup ==
%pstack quit
%offsetvectorsbyn

%offsetvectorsbynusingavg
%1 { filterbyangle } repeat
offsetvectorsbynusingavgs
%1 { filterbyangle } repeat
snipears

%dup ==
newpath
drawpath
} def

%currentflat 4 div setflat
%currentflat 4 mul setflat

2 setlinejoin

/Calibri-Bold 596 selectfont
100 100 moveto (9) true charpath
gsave stroke grestore
20 setlinewidth
strokepath
1 setlinewidth
stroke

1 0 0 setrgbcolor
100 100 moveto (9) true charpath
flattenpath
gsave
10 offsetpath
3 setlinewidth
stroke
grestore

%-10 offsetpath
%stroke

%showpage quit

0 0 1 setrgbcolor
%100 100 moveto (9) true charpath
%flattenpath
%gsave
20 offsetpath
stroke
%grestore
%-20 offsetpath
%stroke


showpage quit

[luser droog]

[snip]

> [[20 4 3 2] []]
> ear: [265.617462 121.338165 263.495483 120.553375 254.480942 118.00251 241.449 115.441101]
> ear: [211.08754 113.391441 191.306641 114.817863]
>
> So it's finding ears in the red curve that I can't even see.
> There also appears to be an ear "around the corner" from the last point to
> the first point of the first subpath of both curves which my detector does
> not detect ATM.
>
>

I rewrote everything from scratch since the other code was long and
complicated and also wrong. This version makes ears on the sharp turns,
but it should be easier for me to figure something out now that it's
all shorter and simpler.


$ cat stroke2.ps
%!

/args-begin { dup length dict begin { exch def } forall } def
/map { [ 3 1 roll forall ] } def
/spill { aload pop } def
/head { 0 exch getinterval } def
/tail { 1 index length 1 index sub getinterval } def
/last { 1 index length 1 index sub exch getinterval } def
/droplast { 1 index length exch sub 0 exch getinterval } def
/fortuplem {
{p m n a} args-begin
0 n /a load length m sub
[ /a load /exch cvx m /getinterval cvx /p load /exec cvx ] cvx
end for
} def

/p-p {

exch 3 1 roll sub % x1 x0 y1-y0
3 1 roll sub exch % x1-x0 y1-y0
} def

/p+v {
exch 3 1 roll add
3 1 roll add exch
} def

/perp {
%exch neg
neg exch
} def

/norm {
2 copy dup mul exch dup mul exch add sqrt
1 exch div v*n
} def

/v*n {
3 2 roll 1 index mul 3 1 roll mul
} def

/closedsubpaths { [ { [ 3 1 roll } { } { } { ] } pathforall ] ] } def

/drawpath {
{

dup length 2 eq { spill moveto }{
dup 2 head spill moveto
2 tail 2 2 { spill lineto } fortuplem
closepath
} ifelse
} forall
} def

/offsetbyvectors {
/n exch def
{
dup length 2 ne {
2 droplast
offsetsubpath
} if
} map
} def

/offsetsubpath {
[ exch
%dup length =
dup 2 4 { offsetvec } fortuplem
counttomark -1 roll
dup 2 last spill 3 2 roll 2 head spill 4 array astore { offsetvec } exec

] %dup length =
} def

/offsetvec {
dup 0 2 getinterval spill 3 2 roll
spill %4 2 roll
p-p norm n v*n
perp p+v
} def

/offsetpath {
closedsubpaths exch
offsetbyvectors
newpath
drawpath
} def

/Calibri-Bold 600 selectfont

100 100 moveto (9) true charpath
gsave stroke grestore

gsave

20 setlinewidth strokepath
1 setlinewidth

%stroke
grestore

1 0 0 setrgbcolor
flattenpath
gsave
10 offsetpath

stroke
grestore
-10 offsetpath
stroke

showpage quit

[luser droog]

On Friday, July 19, 2019 at 4:00:23 PM UTC-5, luser droog wrote:
>
> I rewrote everything from scratch since the other code was long and
> complicated and also wrong. This version makes ears on the sharp turns,
> but it should be easier for me to figure something out now that it's
> all shorter and simpler.
>

I want to point out 2 "hacks" in the code that I'm trying to generalize.
First, the glyph path as expected does not consist entirely of closed paths,
but ends with a single 'moveto' to position the next glyph. When I grab the
path data and try to wrap it in a depth=2 array, I have to add an extra ']'
to close my array. And this leaves a length=2 subpath in my data structure
which should not undergo the offsetting procedure.

> /closedsubpaths { [ { [ 3 1 roll } { } { } { ] } pathforall ] ] } def

I think this behavior can be generalized to be more robust for arbitrary
path data by replacing that final ']' with

{{]}stopped{exit}if}loop

Secondly, the outer curve of the '9' has the last point coincident with
the first. Being closed already takes care of patching up these two points.
But have both identical points present in the list of points makes a zero
vector when I calculate vectors. (Correction: I think both the inner and
outer curves have this coincident point.)

Currently I'm handling this by just explicitly discarding the last point
in the curve. But a more robust solution would find all the zero vectors
and remove corresponding points anywhere in the path.

But this idea is turning out to be damned tricky to implement. I can get
an array of booleans that correspond to the zero vectors easily enough.
But making a loop to run through the booleans and snip corresponding
indices in the path means that every time I do a snip, subsequent indices
have been shifted. So I can't just use a simple 'for' loop. ...

[luser droog]

On Saturday, July 20, 2019 at 11:33:39 AM UTC-5, luser droog wrote:
> On Friday, July 19, 2019 at 4:00:23 PM UTC-5, luser droog wrote:
> >
> > I rewrote everything from scratch since the other code was long and
> > complicated and also wrong. This version makes ears on the sharp turns,
> > but it should be easier for me to figure something out now that it's
> > all shorter and simpler.
> >
>
> I want to point out 2 "hacks" in the code that I'm trying to generalize.
> First, the glyph path as expected does not consist entirely of closed paths,
> but ends with a single 'moveto' to position the next glyph. When I grab the
> path data and try to wrap it in a depth=2 array, I have to add an extra ']'
> to close my array. And this leaves a length=2 subpath in my data structure
> which should not undergo the offsetting procedure.
>

[snip]

The saga of this program continues in the thread, Snipping the ears:
https://groups.google.com/d/msg/comp.lang.postscript/UJKMKfAoqDY/iwkTTSwNEAAJ

[jdaw1]

Cross-link: http://github.com/jdaw1/placemat/issues/18/

Which in turn links to
• http://groups.google.com/g/comp.lang.postscript/c/OTpiW7feg_c/m/7S733-mkey4J
• http://groups.google.com/g/comp.lang.postscript/c/bFWXCkT2R-A
• http://groups.google.com/g/comp.lang.postscript/c/UJKMKfAoqDY/m/Ba9OAtLdCAAJ