METAPOST: How do I get this 'max' cutafter to work?

METAPOST: How do I get this 'max' cutafter to work?

[Gerben Wierda]

[-- Attachment #1.1: Type: text/plain, Size: 2357 bytes --]

I have these two paths, but cutting doesn’t work because the path to be cut takes the wrong intersection regardless of how I direct the path to be cut after (reverse or not).

The path to cut after is a triangle with the base horizontal and the path to cut is a vertical line. The top of the triangle is the endpoint of the line and is selected as intersection by cutafter. This happens also if I reverse the triangle path, strangely enough. I have an alternative cutting algorithm, but that cuts as long as the length of cuttings is not 0, which is the case at the top too, so it won’t cut further.

I need a reliable algorithm to make a ‘maximum cutafter’. What might be a good approach?

G

path arrowHead;
arrowHead :=
  (542,-77.000186920166016)..controls (545.33333333333337,-77.000186920166016) and (548.66666666666663,-77.000186920166016)
  ..(552,-77.000186920166016)..controls (550.33333333333337,-73.666853586832687)
  and (548.66666666666663,-70.333520253499344)
  ..(547,-67.000186920166016)..controls (545.33333333333337,-70.333520253499344)
  and (543.66666666666663,-73.666853586832687)
  ..cycle;

path connection;
connection :=
  (420.00004959106445,-367)..controls (420.66670256708773,-367) and (421.333355543111,-367)
  ..(422.00000851913427,-367)..controls (425.33333917170194,-367) and (428.6666698242696,-367)
  ..(432.00000047683727,-367)..controls (442.00000015894574,-367) and (451.99999984105426,-367)
  ..(461.99999952316273,-367)..controls (464.76142345324098,-367) and (467,-364.76142382108867)
  ..(467,-361.99999997656772)..controls (467,-293.99999999218926) and (467,-226.00000000781074)
  ..(467,-158.00000002343228)..controls (467,-155.23857623850762) and (469.23857634039018,-153)
  ..(472.00000014901161,-153)..controls (495.33333338300389,-153) and (518.66666661699617,-153)
  ..(541.99999985098839,-153)..controls (544.76142368504975,-153) and (547,-150.76142367339932)
  ..(547,-147.99999983662815)..controls (547,-125.99999994554271) and (547,-104.00000005445727)
  ..(547,-82.000000163371837)..controls (547,-78.666668047283764) and (547,-75.333335931195691)
  ..(547,-72.000003815107618)..controls (547,-70.333398183460417) and (547,-68.666792551813217)
  ..(547,-67.000186920166016);

show connection cutafter arrowHead;
show connection cutafter (reverse arrowHead);



[-- Attachment #1.2: Type: text/html, Size: 5677 bytes --]

[-- Attachment #2: Type: text/plain, Size: 493 bytes --]

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[Hans Hagen]

On 4/21/2020 1:29 PM, Gerben Wierda wrote:
> I have these two paths, but cutting doesn’t work because the path to be 
> cut takes the wrong intersection regardless of how I direct the path to 
> be cut after (reverse or not).
> 
> The path to cut after is a triangle with the base horizontal and the 
> path to cut is a vertical line. The top of the triangle is the endpoint 
> of the line and is selected as intersection by cutafter. This happens 
> also if I reverse the triangle path, strangely enough. I have an 
> alternative cutting algorithm, but that cuts as long as the length of 
> cuttings is not 0, which is the case at the top too, so it won’t cut 
> further.
> 
> I need a reliable algorithm to make a ‘maximum cutafter’. What might be 
> a good approach?
> 
> G
> 
> path arrowHead;
> arrowHead :=
>    (542,-77.000186920166016)..controls 
> (545.33333333333337,-77.000186920166016) and 
> (548.66666666666663,-77.000186920166016)
>    ..(552,-77.000186920166016)..controls 
> (550.33333333333337,-73.666853586832687)
>    and (548.66666666666663,-70.333520253499344)
>    ..(547,-67.000186920166016)..controls 
> (545.33333333333337,-70.333520253499344)
>    and (543.66666666666663,-73.666853586832687)
>    ..cycle;
> 
> path connection;
> connection :=
>    (420.00004959106445,-367)..controls (420.66670256708773,-367) and 
> (421.333355543111,-367)
>    ..(422.00000851913427,-367)..controls (425.33333917170194,-367) and 
> (428.6666698242696,-367)
>    ..(432.00000047683727,-367)..controls (442.00000015894574,-367) and 
> (451.99999984105426,-367)
>    ..(461.99999952316273,-367)..controls (464.76142345324098,-367) and 
> (467,-364.76142382108867)
>    ..(467,-361.99999997656772)..controls (467,-293.99999999218926) and 
> (467,-226.00000000781074)
>    ..(467,-158.00000002343228)..controls (467,-155.23857623850762) and 
> (469.23857634039018,-153)
>    ..(472.00000014901161,-153)..controls (495.33333338300389,-153) and 
> (518.66666661699617,-153)
>    ..(541.99999985098839,-153)..controls (544.76142368504975,-153) and 
> (547,-150.76142367339932)
>    ..(547,-147.99999983662815)..controls (547,-125.99999994554271) and 
> (547,-104.00000005445727)
>    ..(547,-82.000000163371837)..controls (547,-78.666668047283764) and 
> (547,-75.333335931195691)
>    ..(547,-72.000003815107618)..controls (547,-70.333398183460417) and 
> (547,-68.666792551813217)
>    ..(547,-67.000186920166016);
> 
> show connection cutafter arrowHead;
> show connection cutafter (reverse arrowHead);

\startMPpage[instance=doublefun]

path arrowHead;
arrowHead :=
     (542,-77.000186920166016)..controls 
(545.33333333333337,-77.000186920166016) and
     (548.66666666666663,-77.000186920166016) 
..(552,-77.000186920166016)..controls
     (550.33333333333337,-73.666853586832687) and
     (548.66666666666663,-70.333520253499344) 
..(547,-67.000186920166016)..controls
     (545.33333333333337,-70.333520253499344) and
     (543.66666666666663,-73.666853586832687) ..cycle;

path connection;
connection :=
   (420.00004959106445,-367)..controls (420.66670256708773,-367) and
   (421.333355543111,-367) ..(422.00000851913427,-367)..controls
   (425.33333917170194,-367) and (428.6666698242696,-367)
   ..(432.00000047683727,-367)..controls (442.00000015894574,-367) and
   (451.99999984105426,-367) ..(461.99999952316273,-367)..controls
   (464.76142345324098,-367) and (467,-364.76142382108867)
   ..(467,-361.99999997656772)..controls (467,-293.99999999218926) and
   (467,-226.00000000781074) ..(467,-158.00000002343228)..controls
   (467,-155.23857623850762) and (469.23857634039018,-153)
   ..(472.00000014901161,-153)..controls (495.33333338300389,-153) and
   (518.66666661699617,-153) ..(541.99999985098839,-153)..controls
   (544.76142368504975,-153) and (547,-150.76142367339932)
   ..(547,-147.99999983662815)..controls (547,-125.99999994554271) and
   (547,-104.00000005445727) ..(547,-82.000000163371837)..controls
   (547,-78.666668047283764) and (547,-75.333335931195691)
   ..(547,-72.000003815107618)..controls (547,-70.333398183460417) and
   (547,-68.666792551813217) ..(547,-67.000186920166016);

pair a ; a := arrowHead intersection_point connection ;

draw connection cutafter arrowHead           withcolor red   withpen 
pencircle scaled 2mm ;
draw connection cutafter (reverse arrowHead) withcolor green withpen 
pencircle scaled 1mm ;

draw arrowHead;

draw a withcolor blue withpen pencircle scaled 3mm ;

currentpicture := currentpicture shifted (-bbwidth(currentpicture), 0) ;

draw connection cutafter a ;

draw arrowHead;


\stopMPpage

-----------------------------------------------------------------
                                           Hans Hagen | PRAGMA ADE
               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
        tel: 038 477 53 69 | www.pragma-ade.nl | www.pragma-pod.nl
-----------------------------------------------------------------
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[Gerben Wierda]

[-- Attachment #1.1: Type: text/plain, Size: 4923 bytes --]



> On 21 Apr 2020, at 14:41, Hans Hagen <j.hagen@xs4all.nl> wrote:
> 
> On 4/21/2020 1:29 PM, Gerben Wierda wrote:
[snip]
> 
> \startMPpage[instance=doublefun]
> 
> path arrowHead;
> arrowHead :=
>    (542,-77.000186920166016)..controls (545.33333333333337,-77.000186920166016) and
>    (548.66666666666663,-77.000186920166016) ..(552,-77.000186920166016)..controls
>    (550.33333333333337,-73.666853586832687) and
>    (548.66666666666663,-70.333520253499344) ..(547,-67.000186920166016)..controls
>    (545.33333333333337,-70.333520253499344) and
>    (543.66666666666663,-73.666853586832687) ..cycle;
> 
> path connection;
> connection :=
>  (420.00004959106445,-367)..controls (420.66670256708773,-367) and
>  (421.333355543111,-367) ..(422.00000851913427,-367)..controls
>  (425.33333917170194,-367) and (428.6666698242696,-367)
>  ..(432.00000047683727,-367)..controls (442.00000015894574,-367) and
>  (451.99999984105426,-367) ..(461.99999952316273,-367)..controls
>  (464.76142345324098,-367) and (467,-364.76142382108867)
>  ..(467,-361.99999997656772)..controls (467,-293.99999999218926) and
>  (467,-226.00000000781074) ..(467,-158.00000002343228)..controls
>  (467,-155.23857623850762) and (469.23857634039018,-153)
>  ..(472.00000014901161,-153)..controls (495.33333338300389,-153) and
>  (518.66666661699617,-153) ..(541.99999985098839,-153)..controls
>  (544.76142368504975,-153) and (547,-150.76142367339932)
>  ..(547,-147.99999983662815)..controls (547,-125.99999994554271) and
>  (547,-104.00000005445727) ..(547,-82.000000163371837)..controls
>  (547,-78.666668047283764) and (547,-75.333335931195691)
>  ..(547,-72.000003815107618)..controls (547,-70.333398183460417) and
>  (547,-68.666792551813217) ..(547,-67.000186920166016);
> 
> pair a ; a := arrowHead intersection_point connection ;
> 
> draw connection cutafter arrowHead           withcolor red   withpen pencircle scaled 2mm ;
> draw connection cutafter (reverse arrowHead) withcolor green withpen pencircle scaled 1mm ;
> 
> draw arrowHead;
> 
> draw a withcolor blue withpen pencircle scaled 3mm ;
> 
> currentpicture := currentpicture shifted (-bbwidth(currentpicture), 0) ;
> 
> draw connection cutafter a ;
> 
> draw arrowHead;
> 
> 
> \stopMPpage

Hi Hans, thanks.

I am completely in the dark why your intersection_point works (and thus if it will keep working in all circumstances).

I’d like to understand what is going on here. Why does intersection_point work where cutafter does not? After all, both are based on the same intersectiontimes primitive to find the intersection and they should thus find the same one: the ’perfect’ intersection which is the end point of the path that is to be cut. 

I’d like to understand this, because otherwise I might run into the same problem again later with slightly different paths involved. The first algo that I was using worked fine in most cases, as well, then I created one that worked with paths with ‘internal spikes’ and now I run into this where two comparable situations behaved differently and my question copied the one that didn’t work. And while this example from you works, I need to have something that is 100% reliable.

What METAPOST comes with is:

path cuttings;  % what got cut off

tertiarydef a cutbefore b =  % tries to cut as little as possible
  begingroup save t;
  (t, whatever) = a intersectiontimes b;
  if t<0:
    cuttings:=point 0 of a;
    a
  else: cuttings:= subpath (0,t) of a;
    subpath (t,length a) of a
  fi
  endgroup
enddef;

tertiarydef a cutafter b =
  reverse (reverse a  cutbefore  b)
  hide(cuttings:=reverse cuttings)
enddef;

secondarydef p intersectionpoint q =
 begingroup save x_,y_; (x_,y_)=p intersectiontimes q;
 if x_<0: errmessage("The paths don't intersect"); origin
 else: .5[point x_ of p, point y_ of q] fi endgroup
enddef;

What is in MetaFun is:

boolean intersection_found ;

secondarydef p intersection_point q =
    begingroup
    save x_, y_ ;
    (x_,y_) = p intersectiontimes q ;
    if x_< 0 :
        intersection_found := false ;
        center p % origin
    else :
        intersection_found := true ;
        .5[point x_ of p, point y_ of q]
    fi
    endgroup
enddef ;

The thing I can think of is cutting a bit, trying if it still intersects and if it does repeat and if it doesn’t take the previous result. I can’t rely on the length of cuttings being 0, because this is true in the case of no intersection (cuttings equals (0,0)) as well as a ‘perfect’ intersection at the end of the path (cuttings is the point at the end of the path). I could rely on cuttings being the path (0,0) but how do I compare paths (and not pairs)?

G 

Pretty deep into MP now. Even looked up the reference in John Hobby’s manual to the METAFONT book, but that reference did not help.



[-- Attachment #1.2: Type: text/html, Size: 15475 bytes --]

[-- Attachment #2: Type: text/plain, Size: 493 bytes --]

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[Hans Hagen]

On 4/21/2020 5:52 PM, Gerben Wierda wrote:

> Pretty deep into MP now. Even looked up the reference in John Hobby’s 
> manual to the METAFONT book, but that reference did not help.
in the end it all has to do with accuracy and rounding ... the 
intersection_point trickery is probably less sensitive for that

but it's so long ago that i mp-tool was written that that part of my 
mind probably has been overwritten, obscured or wiped

Hans

-----------------------------------------------------------------
                                           Hans Hagen | PRAGMA ADE
               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
        tel: 038 477 53 69 | www.pragma-ade.nl | www.pragma-pod.nl
-----------------------------------------------------------------
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[Taco Hoekwater]

Hi,

> On 21 Apr 2020, at 17:52, Gerben Wierda <Gerben.Wierda@rna.nl> wrote:
> 
>> pair a ; a := arrowHead intersection_point connection ;

Hans’ example also works with “intersectionpoint”: the differences between intersectionpoint
and intersection_point are minimal except if there is no intersection at all.

The trick is that Hans does not use cutafter. cutafter is designed to cut off as little as 
possible, it is a cutbefore on both paths reversed. So, uses the last intersection point of 
the paths, and in this case it will therefore use the top of the arrowhead. 

In contrast, intersectionpoint finds the first intersection on the non-reversed paths, which 
is the base of the arrowhead.

Alternatively (in this case), you could move the arrowhead up a tiny amount, so that there is 
only one intersection between the connection and arrowHead.

Best wishes,
Taco
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[luigi scarso]

[-- Attachment #1.1: Type: text/plain, Size: 1003 bytes --]

On Wed, Apr 22, 2020 at 9:30 AM Taco Hoekwater <taco@elvenkind.com> wrote:

>
> In contrast, intersectionpoint finds the first intersection on the
> non-reversed paths, which
> is the base of the arrowhead.
>
>
IIrc ,  it's the first in shuffle order

@ Incidentally, if the given cubics intersect more than once, the process
just sketched will not necessarily find the lexicographically smallest pair
$(t_1,t_2)$. The solution actually obtained will be smallest in ``shuffled
order''; i.e., if $t_1=(.a_1a_2\ldots a_{16})_2$ and
$t_2=(.b_1b_2\ldots b_{16})_2$, then we will minimize
$a_1b_1a_2b_2\ldots a_{16}b_{16}$, not
$a_1a_2\ldots a_{16}b_1b_2\ldots b_{16}$.
Shuffled order agrees with lexicographic order if all pairs of solutions
$(t_1,t_2)$ and $(t_1',t_2')$ have the property that $t_1<t_1'$ iff
$t_2<t_2'$; but in general, lexicographic order can be quite different,
and the bisection algorithm would be substantially less efficient if it were
constrained by lexicographic order.


-- 
luigi

[-- Attachment #1.2: Type: text/html, Size: 1515 bytes --]

[-- Attachment #2: Type: text/plain, Size: 493 bytes --]

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________

Re: METAPOST: How do I get this 'max' cutafter to work?

[Gerben Wierda]

> On 22 Apr 2020, at 09:30, Taco Hoekwater <taco@elvenkind.com> wrote:
> 
> Hi,
> 
>> On 21 Apr 2020, at 17:52, Gerben Wierda <Gerben.Wierda@rna.nl> wrote:
>> 
>>> pair a ; a := arrowHead intersection_point connection ;
> 
> Hans’ example also works with “intersectionpoint”: the differences between intersectionpoint
> and intersection_point are minimal except if there is no intersection at all.
> 
> The trick is that Hans does not use cutafter. cutafter is designed to cut off as little as 
> possible, it is a cutbefore on both paths reversed. So, uses the last intersection point of 
> the paths, and in this case it will therefore use the top of the arrowhead. 
> 
> In contrast, intersectionpoint finds the first intersection on the non-reversed paths, which 
> is the base of the arrowhead.
> 
> Alternatively (in this case), you could move the arrowhead up a tiny amount, so that there is 
> only one intersection between the connection and arrowHead.

In fact I did something like this, except that I first shortened the line path so it ends in the middle of the triangle before doing a cutafter (twice in both directions and taking the one which cuts the most). This works reliably.

I gave up on another approach (which repeatedly cut a little bit from the path until it wasn’t intersecting anymore, then taking the one form thelast successful intersection)  as I also have paths that connect a path-cycle to itself. A ‘cut until it just doesn’t intersect anymore' would eat up the entire path in that case until only a single point is left.

G

> 
> Best wishes,
> Taco
> ___________________________________________________________________________________
> If your question is of interest to others as well, please add an entry to the Wiki!
> 
> maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
> webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
> archive  : https://bitbucket.org/phg/context-mirror/commits/
> wiki     : http://contextgarden.net
> ___________________________________________________________________________________

___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!

maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage  : http://www.pragma-ade.nl / http://context.aanhet.net
archive  : https://bitbucket.org/phg/context-mirror/commits/
wiki     : http://contextgarden.net
___________________________________________________________________________________