[metapost] Re: all intersections between two paths

[Boguslaw Jackowski]

Hans> knowing the persistent high quality of your work, just send them

Inconvincing...

Hans> mails occasional themselves are >4k -)

Convcincing ;-) I reworked the examples and now the archive has 5.5kB.

Laurence> Would your algorithm be extensible for use with other forms of
Laurence> spline curve, in particular NURBs?

No idea. I'm out of math business since long time. I'd ask Larry
Siebenmann...

The crucial assumptions for the algorithm to work are: (1) B\'ezier segments
have no selfintersections and (2) two B\'ezier segments do not intersect at
more than two points.

Both assumption are, in general, invalid (the assumption (2) is perhaps
valid in the realm of fonts which is my main concern), but:

The assumption (1) can be easily circumvented (even automatically), by
splitting such a segment into a 3-segment path (see the example 4 in the
enclosed archive).

As to the assumption (2), two B\'ezier segments without selfintersections can
cross each other at 7 points (which is a simple consequence of the theorem
stated by Dan, that two segments can have at most 9 intersection points).
Here is a simple example:

 beginfig(100);
  path p,q,r;
  p:=(0,0).. controls (300,100) and (-200,100) .. (100,0);
  t:=xpart(p intersectiontimes reverse p);
  q:=subpath (t+.005,1) of p;
  r:=(subpath (0,1-t-0.005) of p) rotatedaround (center(p), 20) shifted (7,1);
  draw q withcolor blue;
  draw r withcolor red;
 endfig;
 end.

(Incidentally, there was a useless line in my previous METAPOST code:
``size:=100''---sorry; I was too quick.)

This case can also be circumvented (see the example 5 in the enclosed
archive). I can admit that circumventing is not a nice technique, but
better this than nothing.

Another argument in favor of the assuption (2) is that such an algorithm can
be implemented in both MF and MP; otherwise, as rightly pointed out Antonio,
the problem cannot be handled efficiently without arclength and arctime
operations (at least I do not know how to do it efficiently) and these
operations are missing from MF.

Anyway, I enclose the macros as they are. Any comments, suggestions,
modifications, questions, etc., are welcome.

-- Jacko

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
 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.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-


-------------- next part --------------
A non-text attachment was scrubbed...
Name: intersec.zip
Type: application/zip
Size: 5530 bytes
Desc: 
Url : http://tug.org/pipermail/metapost/attachments/20050106/718ce5ac/intersec-0001.zip