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 tocenterpoint) from the new circleto 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 ___________________________________________________________________________________