Hi Steve, Looking at the picture you've provided suggests to me the following approach:
a) generate a Voronoi diagram [1] (I think this can be done quickly, i.e. in less than O(n^2) ) on a random set of n points; though I've never actually done it -- maybe somebody knows of a link to an SVG that does that already??; b) while generating, keep track of the edges (since these provide the incidence matrix of the graph); c) within each polygon, inscribe a circle -- inscribing a circle inside a convex polygon should be fairly easy it seems Whether the Voronoi diagrams would be representative of the set of all convex tessellations of the plane relevant to your purposes or not, I'm not sure. Alternative pseudo-random tessellations could be considered with domino tilings, rhombic tilings, or other nonperiodic tilings. That's probably how I'd try to do it. Alternative ways of approaching it would be to generate quasi 2-Euclidean graphs (as in [2]) (in which adjacency of nodes is based on a threshold of their 2-D Euclidean positions, followed by elimination of crossing lines); followed by expansion of circles until the radius equals half the distance of the nearest neighbor. Harary, I think, has a theorem of some sort establishing the number of distinct triangulations of a planar region -- one such triangulation could be induced upon a plane filled with n random points and from there the geometric dual would be something like a Voronoi diagram, it seems. holler when you get it done, since it'd be fun to see David [1] http://en.wikipedia.org/wiki/Voronoi_diagram [2] http://srufaculty.sru.edu/david.dailey/svg/graphs30.svg ----- Original Message ----- From: mercurysbane To: svg-developers@yahoogroups.com Sent: Tuesday, November 18, 2008 2:37 PM Subject: [svg-developers] Generate *non-overlapping* circles? Hey everyone! I have the need to generate non-overlapping circles, and I'm kind of dreading writing the code that will do it from scratch. In fact, it is even a little more complicated than that. I want to be able to take hierarchical information and generate a sort of random-looking web of nodes. Like this (imagine the middle circle is root): http://img4.pictiger.com/655/17374113.jpg I *think* I can write code that will generate something like this. I just know that it is going to take significant effort, so if anyone here has some ideas or previous experience doing something like this, or anything that might help me do it -- I'd really appreciate it. Right now, my plan is to do the actual graphics generation with dojo, unless someone can give me a better alternative... -Steve [Non-text portions of this message have been removed] ------------------------------------ ----- To unsubscribe send a message to: [EMAIL PROTECTED] -or- visit http://groups.yahoo.com/group/svg-developers and click "edit my membership" ----Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/svg-developers/ <*> Your email settings: Individual Email | Traditional <*> To change settings online go to: http://groups.yahoo.com/group/svg-developers/join (Yahoo! ID required) <*> To change settings via email: mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
