StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I was working a bit in this, as I also needed something similar, but I had delayed the algorithm development. You helped me to get some impulse :D </p> <p>I also needed the source code, so here it is. I worked it out in Mathematica, but as I haven't used heavily the functional features, I guess it'll be easy to translate to any procedural language.</p> <h2>A historic perspective</h2> <p> First I decided to develop the algorithm for circles, because the intersection is easier to calculate. It just depends on the centers and radii. </p> <p>I was able to use the Mathematica equation solver, and it performed nicely. </p> <p>Just look:</p> <p><a href="https://i.stack.imgur.com/SiElU.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SiElU.png" alt="alt text"></a></p> <p>It was easy. I just loaded the solver with the following problem:</p> <pre><code>For each circle Solve[ Find new coördinates for the circle Minimizing the distance to the geometric center of the image Taking in account that Distance between centers > R1+R2 *for all other circles Move the circle in a line between its center and the geometric center of the drawing ] </code></pre> <p>As straightforward as that, and Mathematica did all the work. </p> <p>I said "Ha! it's easy, now let's go for the rectangles!". But I was wrong ...</p> <h2>Rectangular Blues</h2> <p>The main problem with the rectangles is that querying the intersection is a nasty function. Something like:</p> <p><img src="https://i.stack.imgur.com/g8R2k.png" width="420" height="60"></p> <p> So, when I tried to feed up Mathematica with a lot of these conditions for the equation, it performed so badly that I decided to do something procedural. </p> <p> My algorithm ended up as follows: </p> <pre><code>Expand each rectangle size by a few points to get gaps in final configuration While There are intersections sort list of rectangles by number of intersections push most intersected rectangle on stack, and remove it from list // Now all remaining rectangles doesn't intersect each other While stack not empty pop rectangle from stack and re-insert it into list find the geometric center G of the chart (each time!) find the movement vector M (from G to rectangle center) move the rectangle incrementally in the direction of M (both sides) until no intersections Shrink the rectangles to its original size </code></pre> <p>You may note that the "smallest movement" condition is not completely satisfied (only in one direction). But I found that moving the rectangles in any direction to satisfy it, sometimes ends up with a confusing map changing for the user. </p> <p>As I am designing a user interface, I choose to move the rectangle a little further, but in a more predictable way. You can change the algorithm to inspect all angles and all radii surrounding its current position until an empty place is found, although it'll be much more demanding. </p> <p>Anyway, these are examples of the results (before/ after): </p> <p><a href="https://i.stack.imgur.com/tFpAc.png" rel="noreferrer"><img src="https://i.stack.imgur.com/tFpAc.png" alt="alt text"></a></p> <p>Edit> More examples <a href="https://i.stack.imgur.com/Lz5F4.png" rel="noreferrer">here</a></p> <p>As you may see, the "minimum movement" is not satisfied, but the results are good enough. </p> <p>I'll post the code here because I'm having some trouble with my SVN repository. I'll remove it when the problems are solved. </p> <h2>Edit: </h2> <p>You may also use <a href="http://en.wikipedia.org/wiki/R-tree" rel="noreferrer">R-Trees</a> for finding rectangle intersections, but it seems an overkill for dealing with a small number of rectangles. And I haven't the algorithms already implemented. Perhaps someone else can point you to an existing implementation on your platform of choice. </p> <p>Warning! Code is a first approach .. not great quality yet, and surely has some bugs. </p> <p>It's Mathematica. </p> <pre><code>(*Define some functions first*) Clear["Global`*"]; rn[x_] := RandomReal[{0, x}]; rnR[x_] := RandomReal[{1, x}]; rndCol[] := RGBColor[rn[1], rn[1], rn[1]]; minX[l_, i_] := l[[i]][[1]][[1]]; (*just for easy reading*) maxX[l_, i_] := l[[i]][[1]][[2]]; minY[l_, i_] := l[[i]][[2]][[1]]; maxY[l_, i_] := l[[i]][[2]][[2]]; color[l_, i_]:= l[[i]][[3]]; intersectsQ[l_, i_, j_] := (* l list, (i,j) indexes, list={{x1,x2},{y1,y2}} *) (*A rect does intesect with itself*) If[Max[minX[l, i], minX[l, j]] < Min[maxX[l, i], maxX[l, j]] && Max[minY[l, i], minY[l, j]] < Min[maxY[l, i], maxY[l, j]], True,False]; (* Number of Intersects for a Rectangle *) (* With i as index*) countIntersects[l_, i_] := Count[Table[intersectsQ[l, i, j], {j, 1, Length[l]}], True]-1; (*And With r as rectangle *) countIntersectsR[l_, r_] := ( Return[Count[Table[intersectsQ[Append[l, r], Length[l] + 1, j], {j, 1, Length[l] + 1}], True] - 2];) (* Get the maximum intersections for all rectangles*) findMaxIntesections[l_] := Max[Table[countIntersects[l, i], {i, 1, Length[l]}]]; (* Get the rectangle center *) rectCenter[l_, i_] := {1/2 (maxX[l, i] + minX[l, i] ), 1/2 (maxY[l, i] + minY[l, i] )}; (* Get the Geom center of the whole figure (list), to move aesthetically*) geometryCenter[l_] := (* returs {x,y} *) Mean[Table[rectCenter[l, i], {i, Length[l]}]]; (* Increment or decr. size of all rects by a bit (put/remove borders)*) changeSize[l_, incr_] := Table[{{minX[l, i] - incr, maxX[l, i] + incr}, {minY[l, i] - incr, maxY[l, i] + incr}, color[l, i]}, {i, Length[l]}]; sortListByIntersections[l_] := (* Order list by most intersecting Rects*) Module[{a, b}, a = MapIndexed[{countIntersectsR[l, #1], #2} &, l]; b = SortBy[a, -#[[1]] &]; Return[Table[l[[b[[i]][[2]][[1]]]], {i, Length[b]}]]; ]; (* Utility Functions*) deb[x_] := (Print["--------"]; Print[x]; Print["---------"];)(* for debug *) tableForPlot[l_] := (*for plotting*) Table[{color[l, i], Rectangle[{minX[l, i], minY[l, i]}, {maxX[l, i], maxY[l, i]}]}, {i, Length[l]}]; genList[nonOverlap_, Overlap_] := (* Generate initial lists of rects*) Module[{alist, blist, a, b}, (alist = (* Generate non overlapping - Tabuloid *) Table[{{Mod[i, 3], Mod[i, 3] + .8}, {Mod[i, 4], Mod[i, 4] + .8}, rndCol[]}, {i, nonOverlap}]; blist = (* Random overlapping *) Table[{{a = rnR[3], a + rnR[2]}, {b = rnR[3], b + rnR[2]}, rndCol[]}, {Overlap}]; Return[Join[alist, blist] (* Join both *)];) ]; </code></pre> <p><strong>Main</strong></p> <pre><code>clist = genList[6, 4]; (* Generate a mix fixed & random set *) incr = 0.05; (* may be some heuristics needed to determine best increment*) clist = changeSize[clist,incr]; (* expand rects so that borders does not touch each other*) (* Now remove all intercepting rectangles until no more intersections *) workList = {}; (* the stack*) While[findMaxIntesections[clist] > 0, (*Iterate until no intersections *) clist = sortListByIntersections[clist]; (*Put the most intersected first*) PrependTo[workList, First[clist]]; (* Push workList with intersected *) clist = Delete[clist, 1]; (* and Drop it from clist *) ]; (* There are no intersections now, lets pop the stack*) While [workList != {}, PrependTo[clist, First[workList]]; (*Push first element in front of clist*) workList = Delete[workList, 1]; (* and Drop it from worklist *) toMoveIndex = 1; (*Will move the most intersected Rect*) g = geometryCenter[clist]; (*so the geom. perception is preserved*) vectorToMove = rectCenter[clist, toMoveIndex] - g; If [Norm[vectorToMove] < 0.01, vectorToMove = {1,1}]; (*just in case*) vectorToMove = vectorToMove/Norm[vectorToMove]; (*to manage step size wisely*) (*Now iterate finding minimum move first one way, then the other*) i = 1; (*movement quantity*) While[countIntersects[clist, toMoveIndex] != 0, (*If the Rect still intersects*) (*move it alternating ways (-1)^n *) clist[[toMoveIndex]][[1]] += (-1)^i i incr vectorToMove[[1]];(*X coords*) clist[[toMoveIndex]][[2]] += (-1)^i i incr vectorToMove[[2]];(*Y coords*) i++; ]; ]; clist = changeSize[clist, -incr](* restore original sizes*); </code></pre> <p>HTH!</p> <h2>Edit: Multi-angle searching</h2> <p><p> I implemented a change in the algorithm allowing to search in all directions, but giving preference to the axis imposed by the geometric symmetry.<br> At the expense of more cycles, this resulted in more compact final configurations, as you can see here below:</p> <p><a href="https://i.stack.imgur.com/r3vpU.png" rel="noreferrer"><img src="https://i.stack.imgur.com/r3vpU.png" alt="enter image description here"></a></p> <p>More samples <a href="https://i.stack.imgur.com/8gY7c.png" rel="noreferrer">here</a>.</p> <p>The pseudocode for the main loop changed to:</p> <pre><code>Expand each rectangle size by a few points to get gaps in final configuration While There are intersections sort list of rectangles by number of intersections push most intersected rectangle on stack, and remove it from list // Now all remaining rectangles doesn't intersect each other While stack not empty find the geometric center G of the chart (each time!) find the PREFERRED movement vector M (from G to rectangle center) pop rectangle from stack With the rectangle While there are intersections (list+rectangle) For increasing movement modulus For increasing angle (0, Pi/4) rotate vector M expanding the angle alongside M (* angle, -angle, Pi + angle, Pi-angle*) re-position the rectangle accorging to M Re-insert modified vector into list Shrink the rectangles to its original size </code></pre> <p>I'm not including the source code for brevity, but just ask for it if you think you can use it. I think that, should you go this way, it's better to switch to R-trees (a lot of interval tests needed here)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload