Here is some comment on GB's intersection problem/solution from the polish mp expert Boguslaw Jackowski (those who will be in bremen next week can meet this personality).
Hans
>EHL> I implemented it by finding some intersectiontime and the recursively >EHL> finding the intersectionstimes of the two subpaths (each with some >EHL> neighbourhood of the first intersection point cut off). For the time >EHL> being I cannot find my code, but here it is in pseude code. > >EHL> When done this way, the intersection times will be sorted according to >EHL> the first path.
Frankly speaking, such a procedure should belong to plain from the very beginning... Obviously, we added it in our plain_ex that we use for generating fonts (even more -- we find also common outlines).
Attached you'll find the relevant excerpt plus examples.
Incidentally, recursion seem still banned from the MF/MP realm. I complained about it some time ago, but it seems that nobody but me is hurted by this annoyin situation. Attached you'll find an example: 31-element series (in a reversed order) break down w2c mpost...
And finally, let me quote the post from Larry Siebenmann (from 30 Jun 2000):
> I believe that value (-1,-1) for "intersectiontimes" is a > 100% ironclad guarantee that its two path arguments are > disjoint. > > Is the converse true? That is, if "intersectiontimes" > yields positive times, do the two paths necessarily > intersect? NO! In writing the last post, I confirmed to my > satisfaction that MP and MF report positive intersection > times for paths that only come near. Start by looking > at the following -- in which one of the paths is constant. > > path c; > pair v,w; > c:=fullcircle scaled 2; > v:=(1+19epsilon,0) rotated 33.1234567; > w:=(1-15epsilon,0) rotated 33.1234567; > show (v intersectiontimes c); > show (w intersectiontimes c); > v:=(1+20epsilon,0) rotated 33.1234567; > w:=(1-16epsilon,0) rotated 33.1234567; > show (v intersectiontimes c); > show (w intersectiontimes c); > > end > > The log: > > This is MetaPost, Version 0.641 > **&Plain filetest.mp > (filetest.mp > >> (0.47754,0.73682) > >> (0.96869,0.7373) > >> (-1,-1) > >> (-1,-1) ) > > Thus "intersectionpoint" may return a point when the paths > are disjoint. It is guaranteed only to return a point of > close approach. Close approach algorithms are complicated > when efficient. But they are trivial in principle and enjoy > incredible generality:- indeed, since we have explicit > bounds modulus of continuity, it suffices to measure image > distances on a finite but fine net of points in source. > > Question: Is there an *if-and-only-if* test for b'ezier > curve intersection? > > The answer is yes for linear segments, though in some, but > not all, cases one needs exact rational arithmetic. So > think of working in C.
I think you have now more comments than enough ;-)
Cheers -- Jacko
-- BOP s. c. ul. Bora-Komorowskiego 24, 80-377 Gdansk, Poland tel. (+48 58) 553 46 59, fax (+48 58) 511 03 81 [EMAIL PROTECTED], http://www.bop.com.pl
================================================================
Deze e-mail is door E-mail VirusScanner van Planet Internet gecontroleerd op virussen.
Op http://www.planet.nl/evs staat een verwijzing naar de actuele lijst waar op wordt gecontroleerd.
4hh.zip
Description: Zip archive
-------------------------------------------------------------------------
Hans Hagen | PRAGMA ADE | [EMAIL PROTECTED]
Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------
information: http://www.pragma-ade.com/roadmap.pdf
documentation: http://www.pragma-ade.com/showcase.pdf
-------------------------------------------------------------------------
