Hello, I would like to know if it is possible in MetaPost (in particular MetaFun) to get all the possible intersection points of the paths, with some kind of simple command, with a syntax like, say: A[] := path1 intersections path2 (where the resulting list could be either a list of points or a list of time pairs, like for intersectiontimes). Another possible syntax could be path3 := path1 intersections path2 which would give a path for which times 0, 1, 2, 3, ... give the first, second, third, fourth, ... intersection point. Anything like this? -- Giuseppe "Oblomov" Bilotta
At 09:59 PM 3/22/2003 +0100, you wrote:
Hello,
I would like to know if it is possible in MetaPost (in particular MetaFun) to get all the possible intersection points of the paths, with some kind of simple command, with a syntax like, say:
A[] := path1 intersections path2
(where the resulting list could be either a list of points or a list of time pairs, like for intersectiontimes).
Another possible syntax could be
path3 := path1 intersections path2
which would give a path for which times 0, 1, 2, 3, ... give the first, second, third, fourth, ... intersection point.
Anything like this?
not that i know, but assuming that those path have some distance, i can imagine dividing a path in parts and determining the intersectionpoints iof the pieces; delta := .25 ; for i=0 step delta upto length(p)-delta : if intersection_found(1,subpath(i,i+.1) of p) : store point fi ; endfor ; ..... Hans ------------------------------------------------------------------------- Hans Hagen | PRAGMA ADE | pragma@wxs.nl 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 -------------------------------------------------------------------------
Saturday, March 22, 2003 Hans Hagen wrote:
I would like to know if it is possible in MetaPost (in particular MetaFun) to get all the possible intersection points of the paths,
[snip]
Anything like this?
HH> not that i know, but assuming that those path have some distance, i can HH> imagine dividing a path in parts and determining the intersectionpoints iof HH> the pieces; HH> delta := .25 ; HH> for i=0 step delta upto length(p)-delta : HH> if intersection_found(1,subpath(i,i+.1) of p) : HH> store point HH> fi ; HH> endfor ; I'll see if I can make something of this ... (wow, looks like I'm gonna need to learn MetaPost too ...) -- Giuseppe "Oblomov" Bilotta
Giuseppe Bilotta
Saturday, March 22, 2003 Hans Hagen wrote:
I would like to know if it is possible in MetaPost (in particular MetaFun) to get all the possible intersection points of the paths,
[snip]
Anything like this?
HH> not that i know, but assuming that those path have some distance, i can HH> imagine dividing a path in parts and determining the intersectionpoints iof HH> the pieces;
HH> delta := .25 ;
HH> for i=0 step delta upto length(p)-delta : HH> if intersection_found(1,subpath(i,i+.1) of p) : HH> store point HH> fi ; HH> endfor ;
I'll see if I can make something of this ... (wow, looks like I'm gonna need to learn MetaPost too ...)
I implemented it by finding some intersectiontime and the recursively finding the intersectionstimes of the two subpaths (each with some neighbourhood of the first intersection point cut off). For the time being I cannot find my code, but here it is in pseude code. let p and q be paths; let (s,t) be a pair of intersection times of p and q; recursively find the intersection times of the subpath (0, s - small number) of p and q; store (s,t); recursively find the intersection times of the subpath (s + small number, infinity) of p and q; feel happy; When done this way, the intersection times will be sorted according to the first path. -- Emil Hedevang Lohse http://home.imf.au.dk/emil/ Alle spørgsmål er lige dumme. Og spørgsmålet "Kan ænder flyve?" er ikke dumt.
Sunday, March 23, 2003 Emil Hedevang Lohse wrote: 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> let p and q be paths; EHL> let (s,t) be a pair of intersection times of p and q; EHL> recursively find the intersection times of the EHL> subpath (0, s - small number) of p and q; EHL> store (s,t); EHL> recursively find the intersection times of the EHL> subpath (s + small number, infinity) of p and q; EHL> feel happy; EHL> When done this way, the intersection times will be sorted according to EHL> the first path. Ok, I came up with something which might be useful; Hans, you may consider adding it to the MetaFun core: newinternal intersectiontolerance ; intersectiontolerance := 4*eps ; def findallintersections (expr p, q) = pair intersections[], intersectionpoints[] ; intersectionsfound := 0 ; % reset intersections if (path p and path q): begingroup ; save j, tp ; path tp; tp := p ; j:= 0 ; intersections[j] = tp intersectiontimes q ; forever: exitif (xpart intersections[j] = -1) or (ypart intersections[j] = -1) or (xpart intersections[j] + intersectiontolerance > length p) ; intersectionpoints[j] = point ypart intersections[j] of q ; j:=j+1 ; tp := subpath (xpart intersections[j-1] + intersectiontolerance, length p) of p ; % watch the trick to ensure that the times are % relative to the original paths intersections[j] := tp intersectiontimes q ; intersections[j] := (xpart (p intersectiontimes ((point xpart intersections[j] of tp)--cycle)), ypart intersections[j]); endfor ; intersectionsfound := j ; endgroup ; fi ; enddef ; Some notes: * this is my first MetaPost macro, so I expect it to be slow, inefficient, and buggy; feel free to comment * USAGE: findallintersections(path, path) reinitializes the following global expressions: + intersectionsfound, a numeric containing the number of intersections + intersections[0] .. intersections[intersectionsfound-1], pairs containing the time of the intersections on the two paths + intersectionpoints[0] .. intersectionpoints[intersectionsfound-1], points of intersection of the two paths * PARAMETER: there is a global parameter intersectiontolerance: setting it too low will send the macro in a neverending loop in case of tangent curves (example: beginfig(1) path c[] ; c1:= fullcircle scaled 10cm ; c2:= fullsquare scaled 10cm ; draw c1 withcolor blue; draw c2 withcolor blue; loggingall ; findallintersections (c1, c2) ; show intersectionsfound ; for i= 0 upto intersectionsfound-1 : drawpoint intersectionpoints[i] ; endfor ; endfig will fail for intersectiontolerance:=eps ; Comments? Ideas? Suggestions? -- Giuseppe "Oblomov" Bilotta
Monday, March 24, 2003 Guy Worthington wrote: GW> Giuseppe Bilotta wrote
Emil Hedevang Lohse wrote:
[an algorithm for finding the intersection points of two paths]
[a metapost implementation]
GW> Thanks Emil and Giuseppe, a nice example that was well worth the read. You may want to have a look at the stuff in the attached MetaPost macroset, which I'm preparing for a better support of the Eukleides program. -- Giuseppe "Oblomov" Bilotta
participants (4)
-
Emil Hedevang Lohse -
Giuseppe Bilotta -
Guy Worthington -
Hans Hagen