### Re: [NTG-context] How can I compare picture variables in metapost?

Aditya Mahajan schrieb: On Tue, 5 May 2009, Peter Rolf wrote: Taco Hoekwater schrieb: Taco Hoekwater wrote: Zhichu Chen wrote: Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. For circles, probably lua calculations will be faster because the data manipulation will be a bit easier. But for non-circle paths, you are better off with a metapost solution because of lua not knowing about the actual paths. linear search does seem to do that badly, here is a stub: Mhh... isn't it easier to just test, if the distance (centerpoint to centerpoint) from the new circle to all already found circles is greater (or equal) than the sum of the radii? Depends on what you mean by does not intersect. Taco's solution only checks if the curves intersect or not. So, it is possible to have two concentric circles. If you check for distance you get circles which do not overlap. aye Of course, in case of circles, non-overlap can also be tested mathmeaticically. if |c_1 - c_2| max(r_1, r_2) then |c_1 - c_2| |r_1 - r_2| else |c_1 - c_2| r_1 + r_2 end Anyhow an interesting and hard problem (I guess O(n!) ? ). I think it is O(n^3).You only have to check all combinations (which is O(n^2)) and do that for each point that you add add. You are the mathematician, so you are *probably* right here :) Best wishes, Peter Aditya ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___ ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Zhichu Chen wrote: Hi all, I want to draw some paths that won't intersect with each other in metapost. Those paths are generated randomly, e.g., draw 100 circles without any intersections. I use a very stupid way like: I am probably missing something, because the fastest way to draw 100 non-intersecting paths is just by having them in a grid. You don't seem to want that, so: what do you want, exactly? (be warned that marble fill is pretty hard). 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Hi Taco, On Tue, May 5, 2009 at 8:51 PM, Taco Hoekwater t...@elvenkind.com wrote: Zhichu Chen wrote: Hi all, I want to draw some paths that won't intersect with each other in metapost. Those paths are generated randomly, e.g., draw 100 circles without any intersections. I use a very stupid way like: I am probably missing something, because the fastest way to draw 100 non-intersecting paths is just by having them in a grid. You don't seem to want that, so: what do you want, exactly? (be warned that marble fill is pretty hard). Nice to have your attention. Those paths are not meant to be somewhere and they appear randomly. Like one path can have a neighbor very close to it and another path may be not so close to any of the other ones. Basically, they are not organized, they can't form a lattice. What I want exactly is how to determine if there's anything on some region of the picture. I need this to test if the random point I picked is useful. I don't think putting them in a grid is what I want. That'll just make those objects look like they are sorted and kind of like it's a fake picture which is generated intentionally. I hope I haven't make you even more confused. 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___ -- Best Regards Chen Zhi-chu Chen | Shanghai Synchrotron Radiation Facility No. 2019 | Jialuo Rd. | Jiading | Shanghai | P.R. China tel: 086 21 5955 3405 | zhichu.chen.googlepages.com | www.sinap.ac.cn ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Zhichu Chen wrote: What I want exactly is how to determine if there's anything on some region of the picture. I need this to test if the random point I picked is useful. That is easy to answer: you can't (well, not unless you invest a *lot* of effort into creating a bitmap edge structure). However what you can do is ask metapost to calculate intersectionpoints with (the most likely ones of) the already existing objects. This may be the easiest solution (even though it will be so slow that for large numbers of items you may be forced to start a division tree). The core trick is that you randomly place a circle with random radius inside an x-y field, and you keep those paths/pictures in an array. For each newlyt generated circle, you look for an intersection with all the already existing ones (and the rectangle borders) and keep trying to re-place it until there are no more collisions. I can't come up with a solution that is both elegant and fast at the moment, sorry. 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

On Tue, May 5, 2009 at 11:04 PM, Taco Hoekwater t...@elvenkind.com wrote: Zhichu Chen wrote: What I want exactly is how to determine if there's anything on some region of the picture. I need this to test if the random point I picked is useful. That is easy to answer: you can't (well, not unless you invest a *lot* of effort into creating a bitmap edge structure). Well, quick and pain. However what you can do is ask metapost to calculate intersectionpoints with (the most likely ones of) the already existing objects. This may be the easiest solution (even though it will be so slow that for large numbers of items you may be forced to start a division tree). The core trick is that you randomly place a circle with random radius inside an x-y field, and you keep those paths/pictures in an array. For each newlyt generated circle, you look for an intersection with all the already existing ones (and the rectangle borders) and keep trying to re-place it until there are no more collisions. Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. I can't come up with a solution that is both elegant and fast at the moment, sorry. 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___ -- Best Regards Chen Zhi-chu Chen | Shanghai Synchrotron Radiation Facility No. 2019 | Jialuo Rd. | Jiading | Shanghai | P.R. China tel: 086 21 5955 3405 | zhichu.chen.googlepages.com | www.sinap.ac.cn ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Zhichu Chen wrote: Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. For circles, probably lua calculations will be faster because the data manipulation will be a bit easier. But for non-circle paths, you are better off with a metapost solution because of lua not knowing about the actual paths. Good luck, 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Taco Hoekwater wrote: Zhichu Chen wrote: Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. For circles, probably lua calculations will be faster because the data manipulation will be a bit easier. But for non-circle paths, you are better off with a metapost solution because of lua not knowing about the actual paths. linear search does seem to do that badly, here is a stub: path p[]; path m; pair n; i := 0; forever: exitif i 99; m := fullcircle scaled (uniformdeviate 20) shifted (uniformdeviate 100, uniformdeviate 100); n := (-1,-1); if i0: for j = 0 upto (i-1): n := m intersectiontimes p[j]; exitif (xpart n)=0; endfor; fi if (xpart n)0: p[i] := m ; i := i + 1; message(decimal(i)); fi endfor; beginfig(1); for i:=0 upto 99: fill p[i]; endfor; currentpicture := currentpicture scaled 5; endfig; end. ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Taco Hoekwater schrieb: Taco Hoekwater wrote: Zhichu Chen wrote: Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. For circles, probably lua calculations will be faster because the data manipulation will be a bit easier. But for non-circle paths, you are better off with a metapost solution because of lua not knowing about the actual paths. linear search does seem to do that badly, here is a stub: Mhh... isn't it easier to just test, if the distance (centerpoint to centerpoint) from the new circle to all already found circles is greater (or equal) than the sum of the radii? Anyhow an interesting and hard problem (I guess O(n!) ? ). Best wishes, Peter ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

On Tue, 5 May 2009, Zhichu Chen wrote: On Tue, May 5, 2009 at 11:04 PM, Taco Hoekwater t...@elvenkind.com wrote: Zhichu Chen wrote: What I want exactly is how to determine if there's anything on some region of the picture. I need this to test if the random point I picked is useful. That is easy to answer: you can't (well, not unless you invest a *lot* of effort into creating a bitmap edge structure). Well, quick and pain. However what you can do is ask metapost to calculate intersectionpoints with (the most likely ones of) the already existing objects. This may be the easiest solution (even though it will be so slow that for large numbers of items you may be forced to start a division tree). The core trick is that you randomly place a circle with random radius inside an x-y field, and you keep those paths/pictures in an array. For each newlyt generated circle, you look for an intersection with all the already existing ones (and the rectangle borders) and keep trying to re-place it until there are no more collisions. Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. Here is an attempt with lua. Aditya \startluacode third = third or {} function third.generate (x,y,r) return { [center] = {math.random() * x, math.random()*y} , [radius] = math.random() * r } end function third.distance (p1, p2) return math.sqrt( (p1[1] - p2[1])^2 + (p1[2] - p2[2])^2 ) end function third.feasible (c, list) if list then for i,v in pairs(list) do if third.distance (c[center], v[center]) c[radius] + v[radius] then return false end end end return true end function third.add_circle (x,y,r,list) local c = {} repeat c = third.generate(x,y,r) until third.feasible(c,list) return c end function third.fill_circles(n,x,y,r) local list = {} for i=1,n do table.insert(list, third.add_circle(x,y,r, list)) end return list end function third.toMP(c, scale) local tprint = function(s) tex.sprint(tex.ctxcatcodes,s) end local scaled = function(p) return (( .. p .. * .. scale .. )) end tprint(draw fullcircle scaled .. scaled(2*c[radius]) .. shifted ( .. scaled(c[center][1]) .. , .. scaled(c[center][2]) .. ); \n) end function third.show_circles(n,x,y,r) local tprint = function(s) tex.sprint(tex.ctxcatcodes,s) end local list = third.fill_circles(n,x,y,r) tprint(\\startMPcode) for i,v in pairs(list) do third.toMP(v, 1cm) end tprint(\\stopMPcode) end \stopluacode \def\drawCircles{\ctxlua{third.show_circles(100,10,10,2)}} \starttext \drawCircles \stoptext ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

On Tue, 5 May 2009, Peter Rolf wrote: Taco Hoekwater schrieb: Taco Hoekwater wrote: Zhichu Chen wrote: Seems that I don't have too many choices. Maybe using lua to do the math and throwing the result to metapost is faster? I think I can do this, but I don't know how. The documents are a little limited. For circles, probably lua calculations will be faster because the data manipulation will be a bit easier. But for non-circle paths, you are better off with a metapost solution because of lua not knowing about the actual paths. linear search does seem to do that badly, here is a stub: Mhh... isn't it easier to just test, if the distance (centerpoint to centerpoint) from the new circle to all already found circles is greater (or equal) than the sum of the radii? Depends on what you mean by does not intersect. Taco's solution only checks if the curves intersect or not. So, it is possible to have two concentric circles. If you check for distance you get circles which do not overlap. Of course, in case of circles, non-overlap can also be tested mathmeaticically. if |c_1 - c_2| max(r_1, r_2) then |c_1 - c_2| |r_1 - r_2| else |c_1 - c_2| r_1 + r_2 end Anyhow an interesting and hard problem (I guess O(n!) ? ). I think it is O(n^3).You only have to check all combinations (which is O(n^2)) and do that for each point that you add add. Aditya ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

Thank you all guys, To Aditya: Clearly I over-emphasized the randomness. Actually, what I meant is a little more complex: identical objects on random coordinates and they don't intersect with each other. We can rotate them but we can't re-size them and scale them. Your code is very interesting. I'll see what I can do now. Thank you again. -- Best Regards Chen Zhi-chu Chen | Shanghai Synchrotron Radiation Facility No. 2019 | Jialuo Rd. | Jiading | Shanghai | P.R. China tel: 086 21 5955 3405 | zhichu.chen.googlepages.com | www.sinap.ac.cn ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

On Wed, 6 May 2009, Zhichu Chen wrote: To Aditya: Clearly I over-emphasized the randomness. Actually, what I meant is a little more complex: identical objects on random coordinates and they don't intersect with each other. We can rotate them but we can't re-size them and scale them. The difficult part in this case is recognizing that either the input is infeasible (you cannnot put 100 circles of radius 1 in a 10x10 square), or that a particular random sample is stuck and you need to restart. Your code is very interesting. I'll see what I can do now. Both Taco's and my solutions can be adapted so that you do not randomize the radius. (Taco's solution will also work for arbitrary object that can then be rotated by a random amount). Another option that you can consider (if you only want the result to look random), is to start with a uniform placement on a grid and then move objects around by a small amount randomly. This will give an appearance that they are placed at random. Aditya ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___

### Re: [NTG-context] How can I compare picture variables in metapost?

On Tue, 5 May 2009, Aditya Mahajan wrote: Both Taco's and my solutions can be adapted so that you do not randomize the radius. (Taco's solution will also work for arbitrary object that can then be rotated by a random amount). Here is another idea. Ask metapost to test for intersection, but code the rest of the logic in lua. Below is a proof of concept code for communicating with metapost. \startluacode circle = circle or {} function circle.path(x,y,r, name) local path = path .. name .. ; \n .. name .. = fullcircle scaled .. 2*r .. shifted ( .. x .. , .. y ..) ; \n return path end function circle.intersect(x1,y1,r1,x2,y2,r2) local mpx = metapost.format(metafun) local c = circle.path(x1,y1,r1, c) local d = circle.path(x2,y2,r2, d) local intersect = pair n; n := c intersectiontimes d ; \n local message = if (xpart n) 0 : \n .. message(\**false**\) ; \n .. else : \n .. message(\**true**\) ; \n .. endif \n local file = c .. d .. intersect .. message -- print(file) local result = mpx:execute(file) local log= result.log if result.status 2 then print(Metapost run successful *) circle.show_result(x1,y1,r1,x2,y2,r2,circle.parse(log)) else print(Metapost run unsuccessful *) end print(log) end function circle.parse(log) local space = lpeg.S( \t\n) local yes = lpeg.C(**true**) local no= lpeg.C(**false**) local result = (yes + no) / circle.result local parser = space^0 * result * space^0 return parser:match(log) end function circle.result(str) return str == **true** end function circle.show_result(x1,y1,r1,x2,y2,r2,flag) local tprint = function(s) tex.sprint(tex.ctxcatcodes,s) end local result = Circles ( .. x1 .. , .. y1 .. ): .. r1 .. and ( .. x2 .. , .. y2 .. ): .. r2 .. if flag then result = result .. intersect. else result = result .. do not intersect. end tprint (result) end \stopluacode \starttext \startluacode circle.intersect(1,1,1,2,2,1.5) circle.intersect(1,1,1,3,3,0.5) \stopluacode \stoptext ___ 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 : https://foundry.supelec.fr/projects/contextrev/ wiki : http://contextgarden.net ___