* Metapost: union test of two paths @ 2010-07-02 17:01 Marco 2010-07-03 8:03 ` Taco Hoekwater 0 siblings, 1 reply; 11+ messages in thread From: Marco @ 2010-07-02 17:01 UTC (permalink / raw) To: ntg-context Hi, two arbitrary paths are given. A small path and a larger path, both cycled. How to find out if the smaller path lies completely »inside« the larger path? If this is too complicated, it might help if I can find out if a given point lies inside a given cycled path. I hope it's understandable what I want to achieve. Marco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-02 17:01 Metapost: union test of two paths Marco @ 2010-07-03 8:03 ` Taco Hoekwater 2010-07-03 10:19 ` Taco Hoekwater 2010-07-03 10:33 ` Alan BRASLAU 0 siblings, 2 replies; 11+ messages in thread From: Taco Hoekwater @ 2010-07-03 8:03 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco On 07/02/2010 07:01 PM, Marco wrote: > Hi, > > two arbitrary paths are given. A small path and a larger path, both cycled. > How to find out if the smaller path lies completely »inside« the larger path? That is hard. The main problem is the word 'arbitrary'. An arbitrary path does not even have to enclose anything: path p; p = origin--(100,100)--cycle; > If this is too complicated, it might help if I can find out if a given point > lies inside a given cycled path. Even this is fairly tricky. Some important questions are: * do your arbitrary paths selfintersect? * are your arbitrary paths convex or concave? * is a point *on* the path in or out? * do you want to use nonzero or even-odd filling rules? Best wishes, Taco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 8:03 ` Taco Hoekwater @ 2010-07-03 10:19 ` Taco Hoekwater 2010-07-03 13:34 ` Taco Hoekwater 2010-07-03 10:33 ` Alan BRASLAU 1 sibling, 1 reply; 11+ messages in thread From: Taco Hoekwater @ 2010-07-03 10:19 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco [-- Attachment #1: Type: text/plain, Size: 678 bytes --] On 07/03/2010 10:03 AM, Taco Hoekwater wrote: > >> If this is too complicated, it might help if I can find out if a given >> point lies inside a given cycled path. > > Even this is fairly tricky. Some important questions are: I thought this was a neat thing to try to write a macro for. Attached is a test file that defines a macro inside() that takes two arguments: a point and a cyclic path. It returns true if the point lies inside that path, in most cases. There are lots of problems with it; what happens to a point actually on the curve is basically undefined, and self-intersects sometimes make it fail in interesting ways. Anyway, perhaps it helps. Best wishes, Taco [-- Attachment #2: inside.mp --] [-- Type: text/plain, Size: 1783 bytes --] def inside(expr j, p) = begingroup save n; hide( save done, L, P, t, bottom, top; boolean done; path L,P; numeric t[]; pair bottom, top; bottom = llcorner p; top = urcorner p; P := p; n := 0; if (xpart j <= xpart bottom) or (xpart j >= xpart top) or (ypart j <= ypart bottom) or (ypart j >= ypart top): else: L := j--(xpart j, ((ypart bottom)-100)); done := false; forever: (t[n],whatever) = L intersectiontimes P; if (t[n]<0) and (n>0) : % find upward match P := reverse P; numeric t[]; L := j--(xpart j, ((ypart bottom)-100)); forever: (t[n],whatever) = L intersectiontimes P; exitif t[n]<0; L := subpath (t[n]+epsilon, length L) of L; n := n + 1; endfor; done := true; fi exitif done; L := subpath (t[n]+epsilon,length L) of L; n := n + 1; endfor; fi ) if (n>1) and (not odd n): true else: false fi endgroup enddef; beginfig(1); path P; % P:= (fullcircle scaled 20) shifted (20,20); % P:= (0,10){down}..(10,10){up} .. (30,10){down} .. (20,10){up}..cycle; % P := unitsquare scaled 10 rotated 30 shifted (20,10); % P := (10,10){down}..(30,10){up} .. (0,10){down} .. (20,10){up}..cycle; P := (0,10){down}..(10,0){right}..(30,5){up}.. (20,10){up}..(30,15){up}..(20,20){left}..cycle; draw P withcolor red; nx := 100; ny := 100; pair endgrid; endgrid := (30,30); pickup pencircle xscaled (xpart endgrid/nx) yscaled (ypart endgrid/ny); pair J; for k = 1 upto nx: for l = 1 upto ny: J := (k/nx*xpart endgrid,l/ny*ypart endgrid); if inside(J,P): drawdot J withcolor green; else: drawdot J withcolor blue; fi endfor; endfor; currentpicture := currentpicture scaled 10; endfig; end. [-- Attachment #3: Type: text/plain, Size: 486 bytes --] ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 10:19 ` Taco Hoekwater @ 2010-07-03 13:34 ` Taco Hoekwater 2010-07-03 14:54 ` Marco 2010-07-03 23:11 ` Marco 0 siblings, 2 replies; 11+ messages in thread From: Taco Hoekwater @ 2010-07-03 13:34 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco [-- Attachment #1: Type: text/plain, Size: 880 bytes --] On 07/03/2010 12:19 PM, Taco Hoekwater wrote: > On 07/03/2010 10:03 AM, Taco Hoekwater wrote: >> >>> If this is too complicated, it might help if I can find out if a given >>> point lies inside a given cycled path. >> >> Even this is fairly tricky. Some important questions are: > > I thought this was a neat thing to try to write a macro for. Attached > is a test file that defines a macro inside() that takes two arguments: > a point and a cyclic path. It returns true if the point lies inside > that path, in most cases. There are lots of problems with it; > what happens to a point actually on the curve is basically undefined, > and self-intersects sometimes make it fail in interesting ways. Here is a somewhat smarter version of the same macro. This one seems ok at first glance (extensive testing will probably show border cases that are not covered). Best wishes, Taco [-- Attachment #2: inside2.mp --] [-- Type: text/plain, Size: 1782 bytes --] def inside(expr j, p) = begingroup save n; hide( save L, P, t, tt,bottom, top; boolean abort; path L,P; pair bottom, top; bottom = llcorner p; top = urcorner p; P := p; n := 0; if (xpart j <= xpart bottom) or (xpart j >= xpart top) or (ypart j <= ypart bottom) or (ypart j >= ypart top): else: P := subpath (epsilon,(length P)) of P; L := j--(xpart j, -infinity); forever: t := xpart (P intersectiontimes L); exitif t<0; tt := t; forever: exitif t<0; exitif not (xpart direction t of P = 0); L := L shifted (-epsilon,0); t := xpart (P intersectiontimes L); exitif t<0; if t<tt: L := L shifted (3epsilon,0); t := xpart (P intersectiontimes L); fi endfor exitif t < 0; n := n + 1; P := subpath (t+epsilon,(length P)) of P; endfor; fi ) if (n>0) and (odd n): true else: false fi endgroup enddef; beginfig(1); path P; P:= (fullcircle scaled 20) shifted (20,20); P:= (0,10){down}..(10,10){up} .. (30,10){down} .. (20,10){up}..cycle; P := ((0,0)--(10,0)--(10,10)--(0,10)--cycle) rotated 130 shifted (20,10); % P := (10,10){down}..(30,10){up} .. (0,10){down} .. (20,10){up}..cycle; % P := ((25,10){down}..(10,0){right}..(30,5){up}.. % (20,10){up}..(30,15){up}..(20,20){left}..cycle) shifted (0,5); nx := 50; ny := 40; pair endgrid; endgrid := (40,30); pickup pencircle xscaled (xpart endgrid/nx) yscaled (ypart endgrid/ny); pair J; for k = 1 upto nx: for l = 1 upto ny: J := (k/nx*xpart endgrid,l/ny*ypart endgrid); if inside(J,P): drawdot J withcolor green; else: drawdot J withcolor blue; fi endfor; endfor; draw P withcolor red; currentpicture := currentpicture scaled 10; endfig; end. [-- Attachment #3: Type: text/plain, Size: 486 bytes --] ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 13:34 ` Taco Hoekwater @ 2010-07-03 14:54 ` Marco 2010-07-03 23:11 ` Marco 1 sibling, 0 replies; 11+ messages in thread From: Marco @ 2010-07-03 14:54 UTC (permalink / raw) To: ntg-context Hi Taco, many thanks for your effort! I'm just having a look at your code. Kind regards Marco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 13:34 ` Taco Hoekwater 2010-07-03 14:54 ` Marco @ 2010-07-03 23:11 ` Marco 2010-07-04 6:47 ` Taco Hoekwater 1 sibling, 1 reply; 11+ messages in thread From: Marco @ 2010-07-03 23:11 UTC (permalink / raw) To: ntg-context Hi Taco! > That is hard. The main problem is the word 'arbitrary'. Sorry, I was too general. The paths are a outline of a relatively simple shape (so border cases should rarely occur) with area >0k, not selfintersecting. > * is a point *on* the path in or out? It doesn't matter in my case. > This one seems ok at first glance (extensive testing will probably > show border cases that are not covered). I did run some tests. It works like a charm, exactly the way I expect. Thank you very much for this piece of code. If I got it right, your basic idea is to count the times the point inside the boundingbox crosses the border of the shape. And the subpath stuff results of the fact that intersectionpoint/times returns only one intersection even if there are more. Very smart. I'm grateful for your support. Kind regards Marco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 23:11 ` Marco @ 2010-07-04 6:47 ` Taco Hoekwater 2010-07-04 8:09 ` Marco 0 siblings, 1 reply; 11+ messages in thread From: Taco Hoekwater @ 2010-07-04 6:47 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco On 07/04/2010 01:11 AM, Marco wrote: > Hi Taco! > >> That is hard. The main problem is the word 'arbitrary'. > Sorry, I was too general. The paths are a outline of a relatively > simple shape (so border cases should rarely occur) with area>0k, not > selfintersecting. That helps. First test whether the paths insersect, that is easy. If they do insersect, they may still be touching each other only. Still, perhaps that is good enough (depends on what you want to do). But if they do not intersect, then you know for sure that either one is inside the other, or they are totally disjunct. In the fully overlapping case, the boundingboxes of the two paths will most likely likewise overlap perfectly, and that could be good enough for you. Alternatively, if you are certain that both the paths are convex hulls, then just testing for the boundingboxes could be good enough in practice. When the two paths P and Q touch at time A, you could test whether the two points that are time(A+epsilon) and time(A-epsilon) are both inside() both paths. But the hardest thing with doing all this in metapost is that you cannot trust metaposts results in the mathematical sense: rounding errors creep in easily in the internal routines, which is one the problems I hope to solve with metapost 2. Best wishes, Taco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-04 6:47 ` Taco Hoekwater @ 2010-07-04 8:09 ` Marco 2010-07-04 8:21 ` Taco Hoekwater 0 siblings, 1 reply; 11+ messages in thread From: Marco @ 2010-07-04 8:09 UTC (permalink / raw) To: ntg-context Thanks for the hints. > But the hardest thing with doing all this in metapost is that you > cannot trust metaposts results in the mathematical sense: rounding > errors creep in easily in the internal routines, which is one the > problems I hope to solve with metapost 2. When is MP2 expected to be released? Is there a timeline or alike? Kind regards Marco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-04 8:09 ` Marco @ 2010-07-04 8:21 ` Taco Hoekwater 0 siblings, 0 replies; 11+ messages in thread From: Taco Hoekwater @ 2010-07-04 8:21 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco On 07/04/2010 10:09 AM, Marco wrote: > Thanks for the hints. > >> But the hardest thing with doing all this in metapost is that you >> cannot trust metaposts results in the mathematical sense: rounding >> errors creep in easily in the internal routines, which is one the >> problems I hope to solve with metapost 2. > When is MP2 expected to be released? Is there a timeline or alike? End of this summer, I hope. But I am constantly juggling between mp|luatex|context and commercial work, so deadlines are far from fixed. Best wishes, Tacfo ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 8:03 ` Taco Hoekwater 2010-07-03 10:19 ` Taco Hoekwater @ 2010-07-03 10:33 ` Alan BRASLAU 2010-07-03 13:36 ` Taco Hoekwater 1 sibling, 1 reply; 11+ messages in thread From: Alan BRASLAU @ 2010-07-03 10:33 UTC (permalink / raw) To: ntg-context; +Cc: Taco Hoekwater, Marco On Saturday 03 July 2010 10:03:32 Taco Hoekwater wrote: > On 07/02/2010 07:01 PM, Marco wrote: > > Hi, > > > > two arbitrary paths are given. A small path and a larger path, both > > cycled. How to find out if the smaller path lies completely »inside« the > > larger path? > > That is hard. The main problem is the word 'arbitrary'. An arbitrary > path does not even have to enclose anything: > > path p; p = origin--(100,100)--cycle; > > > If this is too complicated, it might help if I can find out if a given > > point lies inside a given cycled path. > > Even this is fairly tricky. Some important questions are: > > * do your arbitrary paths selfintersect? > * are your arbitrary paths convex or concave? > * is a point *on* the path in or out? > * do you want to use nonzero or even-odd filling rules? > > Best wishes, > Taco OK, this is off-topic (and not very useful as an answer)... but is something to think about: ``posito tendendum esse a puncto ad punctum, licet nihil ultra iter determinat, via eligetur maxime facilis seu brevissima;'' Leibniz: De rerum originatione radicali, 1697 ``suppose that we are to go from one point to another, without being directed to follow a particular path, the path chosen will be the easiest or the shortest one;'' So, in a Cartesian space, if the energy cost of a kink is low, than > path p; p := origin--(100,100)--cycle; should be a straight line running back on itself. Indeed, this is what metapost produces. Now try p := origin..(100,100)..cycle; Alan ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Metapost: union test of two paths 2010-07-03 10:33 ` Alan BRASLAU @ 2010-07-03 13:36 ` Taco Hoekwater 0 siblings, 0 replies; 11+ messages in thread From: Taco Hoekwater @ 2010-07-03 13:36 UTC (permalink / raw) To: mailing list for ConTeXt users; +Cc: Marco On 07/03/2010 12:33 PM, Alan BRASLAU wrote: > > > So, in a Cartesian space, if the energy cost of a kink is low, than >> path p; p := origin--(100,100)--cycle; > should be a straight line running back on itself. > Indeed, this is what metapost produces. > > Now try p := origin..(100,100)..cycle; The .. operator makes the cost of a kink infinity. Best wishes, Taco ___________________________________________________________________________________ If your question is of interest to others as well, please add an entry to the Wiki! maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context webpage : http://www.pragma-ade.nl / http://tex.aanhet.net archive : http://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___________________________________________________________________________________ ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2010-07-04 8:21 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2010-07-02 17:01 Metapost: union test of two paths Marco 2010-07-03 8:03 ` Taco Hoekwater 2010-07-03 10:19 ` Taco Hoekwater 2010-07-03 13:34 ` Taco Hoekwater 2010-07-03 14:54 ` Marco 2010-07-03 23:11 ` Marco 2010-07-04 6:47 ` Taco Hoekwater 2010-07-04 8:09 ` Marco 2010-07-04 8:21 ` Taco Hoekwater 2010-07-03 10:33 ` Alan BRASLAU 2010-07-03 13:36 ` Taco Hoekwater
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).