Re: Limit of arclength when calculating intersectiontimes ?
luigi scarso <[email protected]> Sat, 26 Apr 2025 11:18:07 +0200
| Newsgroups | gmane.comp.tex.metapost |
|---|---|
| Message-ID | <CAG5iGsC-z9+KdVjcv4rR43W-MPtoJ=KwmbwcNp6Y3SueZeyvgA@mail.gmail.com> |
--===============1881039611690310208== Content-Type: multipart/alternative; boundary="0000000000007e4dec0633aaee45" --0000000000007e4dec0633aaee45 Content-Type: text/plain; charset="UTF-8" On Wed, 23 Apr 2025 at 13:37, luigi scarso <[email protected]> wrote: > > > On Wed, 23 Apr 2025 at 12:43, Toby Thurston <[email protected]> wrote: > >> Can I draw your attention to this question on TeX.SE? >> >> https://tex.stackexchange.com/q/741317/15036 >> >> Apparently MP fails to calculate `intersectiontimes` if either path has a >> `arclength` > 32767.99997 regardless of the number system being used. >> >> Is this limit of `2**15-epsilon` baked in somewhere? >> >> Toby >> >> > $>mpost -numbersystem=binary test.mp > > %% test.mp > numberprecision:=72; > show numbersystem; % should be binary > > d=0.999999999999; > path p,q; pair r; > > p=origin--(800,0); > q=(400,-16383-d)--(400,16383+d); > > r=p intersectiontimes q; show r; % shows (-1,-1) ??????? > > end > > it's still ok, but d=0.9999999999999; fails. > > It's worth checking out. > > Short answer, maybe I'll look into it further, but not now. In mp_path_intersection at some point we call mp_cubic_intersection static void mp_path_intersection (MP mp, mp_knot h, mp_knot hh) { : : if (mp_right_type (pp) != mp_endpoint) { mp_cubic_intersection (mp, p, pp); static void mp_cubic_intersection (MP mp, mp_knot p, mp_knot pp) { : if (number_to_scaled (mp->delx) - mp->tol <= number_to_scaled (stack_max (x_packet (mp->xy))) - number_to_scaled (stack_min (u_packet (mp->uv)))) if (number_to_scaled (mp->delx) + mp->tol >= number_to_scaled (stack_min (x_packet (mp->xy))) - number_to_scaled (stack_max (u_packet (mp->uv)))) if (number_to_scaled (mp->dely) - mp->tol <= number_to_scaled (stack_max (y_packet (mp->xy))) - number_to_scaled (stack_min (v_packet (mp->uv)))) if (number_to_scaled (mp->dely) + mp->tol >= number_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scaled (stack_max (v_packet (mp->uv)))) { if (number_to_scaled (mp->cur_t) >= number_to_scaled (mp->max_t)) { if ( number_equal(mp->max_t, x_two_t) || number_greater(mp->max_t,x_two_t_low_precision)) { /* we've done 17+2 bisections */ number_divide_int(mp->cur_t,1<<2);number_divide_int(mp->cur_tt,1<<2); /* restore values due bit precision */ set_number_from_scaled (mp->cur_t, ((number_to_scaled (mp->cur_t) + 1)/2)); set_number_from_scaled (mp->cur_tt, ((number_to_scaled (mp->cur_tt) + 1)/2)); return; } number_double(mp->max_t); number_clone (mp->appr_t, mp->cur_t); number_clone (mp->appr_tt, mp->cur_tt); } @<Subdivide for a new level of intersection@>; goto CONTINUE; } number_to_scaled convert to signed int, whatever is the numbersystem. This mean that when pp change a little bit -pp=(400,-16383.999900000001) l=(400,-16383.999900000001) r=(400,-5461.3333000000002) q=(400,16383.999900000001) +pp=(400,-16384) l=(400,-16384) r=(400,-5461.3333333333339) q=(400,16384) we have -number_to_scaled (mp->dely) - mp->tol <= number_to_scaled (stack_max (y_packet (mp->xy))) - number_to_scaled (stack_min (v_packet (mp->uv))): 1073741817 <= 2147483635 ? 1 -CHECK stack_max(y_packet (mp->xy)): $1 = {data = {num = 0x40dffffffcb923a3, dval = 32767.999800000001, val = -54975581}, type = mp_scaled_type} -CHECK: number_to_scaled (stack_max (y_packet (mp->xy)))=2147483635, number_to_scaled (stack_min (v_packet (mp->uv)))=0 -number_to_scaled (mp->dely) + mp->tol >= number_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scaled (stack_max (v_packet (mp->uv))): 1073741817 >= 0 ? 1 +number_to_scaled (mp->dely) - mp->tol <= number_to_scaled (stack_max (y_packet (mp->xy))) - number_to_scaled (stack_min (v_packet (mp->uv))): 1073741824 <= -2147483648 ? 0 +CHECK stack_max(y_packet (mp->xy)): $1 = {data = {num = 0x40e0000000000000, dval = 32768, val = 0}, type = mp_scaled_type} +CHECK: number_to_scaled (stack_max (y_packet (mp->xy)))=-2147483648, number_to_scaled (stack_min (v_packet (mp->uv)))=0 +number_to_scaled (mp->dely) + mp->tol >= number_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scaled (stack_max (v_packet (mp->uv))): 1073741824 >= 0 ? 1 As we can see we pass from 2147483635 to -2147483648 instead of 2147483648 and this is a radical change. -- luigi --0000000000007e4dec0633aaee45 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote g= mail_quote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, 23 Apr = 2025 at 13:37, luigi scarso <<a href=3D"mailto:[email protected]">l= [email protected]</a>> wrote:<br></div><blockquote class=3D"gmail_qu= ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20= 4);padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div c= lass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, 23 Apr 2= 025 at 12:43, Toby Thurston <<a href=3D"mailto:[email protected]" target= =3D"_blank">[email protected]</a>> wrote:<br></div><blockquote class=3D"gm= ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,= 204,204);padding-left:1ex">Can I draw your attention to this question on Te= X.SE?<br> <br> <a href=3D"https://tex.stackexchange.com/q/741317/15036" rel=3D"noreferrer"= target=3D"_blank">https://tex.stackexchange.com/q/741317/15036</a><br> <br> Apparently MP fails to calculate `intersectiontimes` if either path has a `= arclength` > 32767.99997 regardless of the number system being used.<br> <br> Is this limit of `2**15-epsilon` baked in somewhere?<br> <br> Toby<br> <br></blockquote><div><br></div><div>$>mpost -numbersystem=3Dbinary <a h= ref=3D"http://test.mp" target=3D"_blank">test.mp</a></div><div><br></div><d= iv>%%=C2=A0 <a href=3D"http://test.mp" target=3D"_blank">test.mp</a></div><= div>numberprecision:=3D72;<br>show numbersystem; % should be binary<br><br>= d=3D0.999999999999;<br>path p,q; pair r;<br><br>p=3Dorigin--(800,0);<br>q= =3D(400,-16383-d)--(400,16383+d);<br><br>r=3Dp intersectiontimes q; show r;= % shows (-1,-1) ???????<br><br>end</div><div><br></div><div>=C2=A0it's= still ok, but=C2=A0=C2=A0d=3D0.9999999999999; fails.</div><div><br></div><= div>It's worth checking out.</div><div><br></div></div></div></blockquo= te><div><br></div><div>Short answer, maybe I'll look into it further, b= ut not now.</div><div><br></div><div>In=C2=A0mp_path_intersection at some p= oint we call=C2=A0</div><div>mp_cubic_intersection</div><div><br></div><div= >static void mp_path_intersection (MP mp, mp_knot h, mp_knot hh) {<br>:<br>= :<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (mp_right_type (pp) !=3D mp_endpo= int) {<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 mp_cubic_intersection (= mp, p, pp);<br></div><div><br></div><div><br></div><div>static void mp_cubi= c_intersection (MP mp, mp_knot p, mp_knot pp) {</div><div>:</div><div>=C2= =A0 =C2=A0 if (number_to_scaled (mp->delx) - mp->tol <=3D<br>=C2= =A0 =C2=A0 =C2=A0 =C2=A0 number_to_scaled (stack_max (x_packet (mp->xy))= ) - number_to_scaled (stack_min (u_packet (mp->uv))))<br>=C2=A0 =C2=A0 = =C2=A0 if (number_to_scaled (mp->delx) + mp->tol >=3D<br>=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 number_to_scaled (stack_min (x_packet (mp->x= y))) - number_to_scaled (stack_max (u_packet (mp->uv))))<br>=C2=A0 =C2= =A0 =C2=A0 =C2=A0 if (number_to_scaled (mp->dely) - mp->tol <=3D<b= r>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 number_to_scaled (stack_max (y_= packet (mp->xy))) - number_to_scaled (stack_min (v_packet (mp->uv))))= <br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (number_to_scaled (mp->dely) += mp->tol >=3D<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 num= ber_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scaled (stack_= max (v_packet (mp->uv)))) {<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= if (number_to_scaled (mp->cur_t) >=3D number_to_scaled (mp->max_t= )) {<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if ( number_equal(= mp->max_t, x_two_t) || number_greater(mp->max_t,x_two_t_low_precision= )) { =C2=A0 /* we've done 17+2 bisections */<br>=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 number_divide_int(mp->cur_t,1<<= 2);number_divide_int(mp->cur_tt,1<<2); /* restore values due bit p= recision */<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 set_= number_from_scaled (mp->cur_t, ((number_to_scaled (mp->cur_t) + 1)/2)= );<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 set_number_fr= om_scaled (mp->cur_tt, ((number_to_scaled (mp->cur_tt) + 1)/2));<br>= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return;<br>=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 number_double(mp->max_t);<br>=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 number_clone (mp->appr_t, mp->cur_t);<br>= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 number_clone (mp->appr_= tt, mp->cur_tt);<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }<br>=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 @<Subdivide for a new level of in= tersection@>;<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 goto CONTINUE= ;<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }<br></div><div><br></div><div>numb= er_to_scaled convert to signed int, whatever is the numbersystem.</div><div= ><br></div><div>This=C2=A0mean that when pp change a little bit</div><div>-= pp=3D(400,-16383.999900000001) l=3D(400,-16383.999900000001) r=3D(400,-5461= .3333000000002) q=3D(400,16383.999900000001)<br>+pp=3D(400,-16384) l=3D(400= ,-16384) r=3D(400,-5461.3333333333339) q=3D(400,16384)<br></div><div><br></= div><div>we have=C2=A0</div><div><br></div><div>-number_to_scaled (mp->d= ely) - mp->tol <=3D =C2=A0number_to_scaled (stack_max (y_packet (mp-&= gt;xy))) - number_to_scaled (stack_min (v_packet (mp->uv))): 1073741817 = <=3D 2147483635 ? 1<br>-CHECK stack_max(y_packet (mp->xy)): $1 =3D {d= ata =3D {num =3D 0x40dffffffcb923a3, dval =3D 32767.999800000001, val =3D -= 54975581}, type =3D mp_scaled_type}<br>-CHECK: number_to_scaled (stack_max = (y_packet (mp->xy)))=3D2147483635, number_to_scaled (stack_min (v_packet= (mp->uv)))=3D0<br>-number_to_scaled (mp->dely) + mp->tol >=3D = =C2=A0number_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scale= d (stack_max (v_packet (mp->uv))): 1073741817 >=3D 0 ? 1<br>+number_t= o_scaled (mp->dely) - mp->tol <=3D =C2=A0number_to_scaled (stack_m= ax (y_packet (mp->xy))) - number_to_scaled (stack_min (v_packet (mp->= uv))): 1073741824 <=3D -2147483648 ? 0<br>+CHECK stack_max(y_packet (mp-= >xy)): $1 =3D {data =3D {num =3D 0x40e0000000000000, dval =3D 32768, val= =3D 0}, type =3D mp_scaled_type}<br>+CHECK: number_to_scaled (stack_max (y= _packet (mp->xy)))=3D-2147483648, number_to_scaled (stack_min (v_packet = (mp->uv)))=3D0<br>+number_to_scaled (mp->dely) + mp->tol >=3D = =C2=A0number_to_scaled (stack_min (y_packet (mp->xy))) - number_to_scale= d (stack_max (v_packet (mp->uv))): 1073741824 >=3D 0 ? 1<br></div><di= v><br></div><div>As we can see we pass from 2147483635=C2=A0 to=C2=A0=C2=A0= -2147483648=C2=A0 instead of=C2=A0 2147483648 and this is a radical change.= </div><div><br></div><div>--</div><div>luigi</div><div><br></div><blockquot= e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s= olid rgb(204,204,204);padding-left:1ex"> </blockquote></div></div> --0000000000007e4dec0633aaee45-- --===============1881039611690310208== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline -- http://tug.org/metapost/ --===============1881039611690310208==--