[metapost] all intersections between two paths

[Boguslaw Jackowski]

Laurence, i.e., Antonio:
> The question is about finding all of the intersections of two arbitrary
> `paths'.

Dear colleagues,

I have solved, a least partially, the problem. Actually, such an algorithm is
implemented in a set of macros (plain_ex.mp) that is used in the METATYPE1
engine for the generating of Type 1 fonts out of METATPOST sources. 

But since it is some 60kB of code, it may be too much for an occasional
MP user. Therefore I prepared an tiny excerpt that does even more,
than finding intersections -- it has also implemented a macro for
so called ``removing overlaps''. Of course, the precision of MP is low,
so the macros are not extremely robust, but in normal situations you
may expect them to work.

*** MARGINAL NOTE:

But the abnormal situations happen... Consider, e.g., the following
trivial example:

  path p,q,r;
  p=fullcircle rotated 33;
  q=fullcircle shifted (1+9epsilon,0) rotated 33;
  show p intersectiontimes q;
  end.

The paths should not touch (both are rotated by the same angle,
so the ``non-circularity'' of the MF/MP circle doesn't play
a role here). Yet the MP's log file says

  >> (0.00194,3.99805)

MF produces ``complementary'' values:

  >> (7.99306,4.00696)

*** END OF NOTE

The package is pretty small (some of 4kB zipped macros plus examples), yet
I'd rather not send them to the list without the agreement of the members
and, moreover, I don't know whether the list server accepts attachments.
Anyway, I can send them privately to anybody. But feel warned that the only
documentation are the four simple examples ;-)
 
Cheers -- Jacko

Ps.
Dan Luecking:
> Mathematically, paths of length 1 can intersect as many as 9 times.

Could you provide an example? I can invent only an 8 intersections case.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
 Bogus\l{}aw Jackowski: B_Jackowski at GUST.ORG.PL
----------------------------------------------------------------
 Hofstadter's Law: It always takes longer than you expect, even
                   when you take into account Hofstadter's Law.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-