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

Groups > comp.lang.postscript > #3415

Re: Fierce and scary geometry algorithm for ‘ParallelPath’

Show all headers | View raw

On Thursday, June 27, 2019 at 10:30:50 AM UTC-5, luser droog wrote:
> On Thursday, June 27, 2019 at 9:48:15 AM UTC-5, luser droog wrote:
> > On Thursday, June 27, 2019 at 8:59:25 AM UTC-5, luser droog wrote:
> > > 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.
> > > 
> > 
> > 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.
> > 
> 
> "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".
> 

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.


$ 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

/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

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

Thread

Fierce and scary geometry algorithm for ‘ParallelPath’ jdawiseman.bloomberg@gmail.com - 2019-04-17 13:37 -0700
  Re: Fierce and scary geometry algorithm for ‘ParallelPath’ edspikechapman@gmail.com - 2019-04-19 08:55 -0700
    Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdawiseman.bloomberg@gmail.com - 2019-04-20 02:44 -0700
      Re: Fierce and scary geometry algorithm for ‘ParallelPath’ Carlos <carlos@cvkm.cz> - 2019-04-29 02:41 +0200
        Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdaw1 <jdawiseman@gmail.com> - 2019-06-19 15:04 -0700
          Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-22 13:33 -0700
            Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-22 14:54 -0700
              Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-22 15:37 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-23 15:59 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-27 06:59 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-27 07:48 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-27 08:30 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-06-28 12:10 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-07-19 14:00 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-07-20 09:33 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-07-20 13:20 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdaw1 <jdawiseman@gmail.com> - 2021-03-14 10:25 -0700
  Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdawiseman.bloomberg@gmail.com - 2019-04-20 06:54 -0700
    Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-04-20 10:44 -0700
      Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdawiseman.bloomberg@gmail.com - 2019-04-20 11:01 -0700
        Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-04-20 11:33 -0700
          Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-04-20 11:50 -0700
            Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-04-20 13:01 -0700
              Re: Fierce and scary geometry algorithm for ‘ParallelPath’ jdawiseman.bloomberg@gmail.com - 2019-04-21 03:29 -0700
                Re: Fierce and scary geometry algorithm for ‘ParallelPath’ luser droog <luser.droog@gmail.com> - 2019-04-28 13:33 -0700

csiph-web