This algorithm moves along the circle and removes the overlapping of the nodes laid out on a circle maintaining a custom gap between them. O(n), doesn't use trigonometry. Relaxation sometimes cannot be completed in one sweep, cause it moves nodes in one direction: clockwise.
Special case is when a node is pushed across the 0° mark.
| <!doctype html> | |
| <html> | |
| <head> | |
| <title>Remove overlaps on a radial layout</title> | |
| <script src="https://unpkg.com/d3@4.4.1"></script> | |
| <style> | |
| circle { | |
| fill-opacity: 0.3; | |
| stroke: #000000; | |
| stroke-width: 0.5; | |
| } | |
| text { | |
| font-family: sans-serif; | |
| font-size: 10px; | |
| fill: #000000; | |
| } | |
| .isect { | |
| fill-opacity: 0.8; | |
| fill: red; | |
| stroke: red; | |
| stroke-width: 0.5; | |
| } | |
| .isect.prime { | |
| fill: green; | |
| } | |
| .ln { | |
| stroke-weight: 0.5; | |
| } | |
| .control { | |
| position: absolute; | |
| top: 20px; | |
| right: 20px; | |
| padding: 10px 20px; | |
| font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; | |
| font-weight: 300; | |
| background: #fff; | |
| border-radius: 4px; | |
| box-shadow: 0 0 5px rgba(0,0,0,0.5); | |
| } | |
| .control h4 { | |
| font-weight: 300; | |
| } | |
| .control input[type=number] { | |
| width: 50px; | |
| } | |
| .general { | |
| fill: none; | |
| stroke-weight: 0.5; | |
| stroke: red; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div class="control"> | |
| <h4>Remove overlaps on a radial layout</h4> | |
| <p><label><input id="n" value="60" type="number" min="0" step="1" /> Vertices</label></p> | |
| <p><label><input id="gap" value="10" type="number" min="0" step="1" max="5" /> Gap (px)</label></p> | |
| <p><button id="relax">Remove overlaps</button><button id="generate">Generate</button></p> | |
| </div> | |
| <script src="index.js"></script> | |
| </body> | |
| </html> |
| const h = document.documentElement.clientHeight; | |
| const w = h; | |
| const deg2rad = Math.PI / 180; | |
| const color = d3.interpolateRgb('steelblue', 'brown'); | |
| // canvas | |
| const svg = d3.select('body') | |
| .append('svg') | |
| .attr('width', w) | |
| .attr('height', h) | |
| .attr('viewBox', [-w/2, -h/2, w, h].join(' ')) | |
| .append('g'); | |
| let circles, texts; | |
| var C = [ 0, 0]; | |
| var N = 40; | |
| var GAP = 2; | |
| var R; | |
| var sizes, angles; | |
| var X = []; | |
| var Y = []; | |
| // render nodes | |
| function render () { | |
| circles | |
| .attr('cx', (d, i) => X[i]) | |
| .attr('cy', (d, i) => Y[i]) | |
| .attr('r', (d) => d) | |
| .attr('fill', (d, i) => color(i / N)); | |
| texts | |
| .attr('dx', (d, i) => X[i] - (i < 10 ? 3 : 6)) | |
| .attr('dy', (d, i) => Y[i] + 4) | |
| .text((d, i) => i); | |
| } | |
| /** | |
| * Sort points clockwise around a center point | |
| * @param {number} ax | |
| * @param {number} ay | |
| * @param {number} bx | |
| * @param {number} by | |
| * @param {number} cx | |
| * @param {number} cy | |
| * @return {number} | |
| */ | |
| function compare (ax, ay, bx, by, cx, cy) { | |
| if (ax - cx >= 0 && bx - cx < 0) return 1; | |
| if (ax - cx < 0 && bx - cx >= 0) return -1; | |
| if (ax - cx === 0 && bx - cx === 0) { | |
| return (ay - by >= 0 || by - cy >= 0) ? (ay - by) : (by - ay); | |
| } | |
| // compute the cross product of vectors (center -> a) x (center -> b) | |
| var det = (ax - cx) * (by - cy) - (bx - cx) * (ay - cy); | |
| if (det < 0) return 1; | |
| if (det > 0) return -1; | |
| // points a and b are on the same line from the center | |
| // check which point is closer to the center | |
| var d1 = (ax - cx) * (ax - cx) + (ay - cy) * (ay - cy); | |
| var d2 = (bx - cx) * (bx - cx) + (by - cy) * (by - cy); | |
| return d1 - d2; | |
| } | |
| function crossProduct (ax, ay, bx, by, cx, cy) { | |
| // compute the cross product of vectors (center -> a) x (center -> b) | |
| var det = (ax - cx) * (by - cy) - (bx - cx) * (ay - cy); | |
| if (det < 0) return 1; | |
| if (det > 0) return -1; | |
| return 0; // same dir | |
| } | |
| function dotProduct (ax, ay, bx, by, cx, cy) { | |
| return (ax - cx) * (bx - cx) + (ay - cy) * (by - cy); | |
| } | |
| function distance (ax, ay, bx, by) { | |
| var dx = ax - bx; | |
| var dy = ay - by; | |
| return Math.sqrt(dx * dx + dy * dy); | |
| } | |
| /** | |
| * Intersection point of 2 circles | |
| * | |
| * http://paulbourke.net/geometry/circlesphere/ | |
| * | |
| * @param {number} x0 | |
| * @param {number} y0 | |
| * @param {number} r0 | |
| * @param {number} x1 | |
| * @param {number} y1 | |
| * @param {number} r1 | |
| * @return {null|Array.<Array.<number>>} | |
| */ | |
| function circleCircleIntersection (x0, y0, r0, x1, y1, r1) { | |
| let a, dx, dy, d, h, rx, ry; | |
| let x2, y2; | |
| // dx and dy are the vertical and horizontal distances between | |
| // the circle centers. | |
| dx = x1 - x0; | |
| dy = y1 - y0; | |
| // Determine the straight-line distance between the centers. */ | |
| d = Math.sqrt(dx * dx + dy * dy); | |
| // no solution. circles do not intersect. | |
| if (d > (r0 + r1)) return null; | |
| // no solution. one circle is contained in the other | |
| if (d < Math.abs(r0 - r1)) return null; | |
| // 'point 2' is the point where the line through the circle | |
| // intersection points crosses the line between the circle | |
| // centers. | |
| // Determine the distance from point 0 to point 2. | |
| a = ((r0 * r0) - (r1 * r1) + (d * d)) / (2 * d); | |
| // Determine the coordinates of point 2. | |
| x2 = x0 + (dx * a / d); | |
| y2 = y0 + (dy * a / d); | |
| // Determine the distance from point 2 to either of the | |
| // intersection points. | |
| h = Math.sqrt((r0 * r0) - (a * a)); | |
| // Now determine the offsets of the intersection points from point 2. | |
| rx = -dy * (h / d); | |
| ry = dx * (h / d); | |
| // Determine the absolute intersection points | |
| return [ | |
| [x2 + rx, y2 + ry], | |
| [x2 - rx, y2 - ry] | |
| ]; | |
| } | |
| /** | |
| * Get arch length of a bigger circle, spanned by the radius of a smaller one | |
| * @param {number} r | |
| * @param {number} R | |
| * @return {number} | |
| */ | |
| function chordToArcLength(r, R) { | |
| var halfr = r / 2; | |
| var h = R - Math.sqrt(R * R - (r * r) / 4); // arc height | |
| var l = Math.sqrt(h * h + (r * r) / 4); | |
| var L = r; | |
| // Huygens formula | |
| return 2 * l + (1 / 3) * (2 * l - L); | |
| } | |
| function relax ({ X, Y, sizes, indexes, R, N, center, gap = 0 }) { | |
| N = indexes.length; | |
| const SWEEP_MAX = 10; | |
| let I = N * 2; // ensure 2 sweeps | |
| let cx = center[0], | |
| cy = center[1]; | |
| // special cases | |
| if (N === 1) return; // obviously | |
| if (N === 2) { // just move them apart, if possible | |
| var a = indexes[0]; | |
| var b = indexes[1]; | |
| var ax = X[a], ay = Y[a], as = sizes[a]; | |
| var bx = X[b], by = Y[b], bs = sizes[b]; | |
| var minDist = chordToArcLength(as, R) + | |
| chordToArcLength(bs, R) + gap; | |
| var dist = distance(ax, ay, bx, by); | |
| var arcLength = chordToArcLength(dist, R); | |
| if (arcLength < minDist) { | |
| var angle = minDist / R; | |
| var dx = ax - cx, | |
| dy = ay - cy; | |
| var sin = Math.sin(angle), | |
| cos = Math.cos(angle); | |
| dx = dx * cos - dy * sin; | |
| dy = dx * sin + dy * cos; | |
| X[b] = cx + dx; | |
| Y[b] = cy + dy; | |
| } | |
| return; | |
| } | |
| let sorted = indexes.sort((a, b) => { | |
| return compare(X[a], Y[a], X[b], Y[b], cx, cy); | |
| }); | |
| let start = sorted[N - 1]; | |
| let x0 = X[start], y0 = Y[start]; // fix start point | |
| let hop = false; | |
| for (var i = -1; i < I - 1; i++) { | |
| var a = i % N, b = (i + 1) % N; | |
| if (i === -1) { | |
| a = 0; | |
| b = N - 1; | |
| } | |
| a = sorted[a]; | |
| b = sorted[b]; | |
| var ax = X[a], ay = Y[a]; | |
| var bx = X[b], by = Y[b]; | |
| var as = sizes[a], bs = sizes[b]; | |
| var minDist = as + bs + gap; | |
| var shift = minDist - distance(ax, ay, bx, by); | |
| var dir = compare(ax, ay, bx, by, cx, cy); | |
| if (dir === -1 && hop) dir = 1; | |
| // if order was broken or distance is too small | |
| if (dir === 1 || shift > 1e-3) { | |
| var shifted = circleCircleIntersection(cx, cy, R, ax, ay, minDist); | |
| if (shifted) { | |
| var target = shifted[0]; | |
| hop = (bx > cx && target[0] < cx); // 0 degrees hop | |
| bx = X[b] = target[0]; | |
| by = Y[b] = target[1]; | |
| } | |
| } else { | |
| hop = false; | |
| } | |
| // render (); | |
| // debugger; | |
| if (i % N === N - 2) { | |
| var last = N - 1; | |
| // only I and IV quaters of the circle, crossed the sorting 0 angle | |
| if (Y[sorted[last]] > cy && Y[sorted[0]] > cy && | |
| X[sorted[last]] - sizes[sorted[last]] < X[sorted[0]] + sizes[sorted[0]]) { | |
| var x = 0; | |
| I = Math.min(N * SWEEP_MAX, I + N); | |
| while (Y[sorted[last]] > cy && Y[sorted[0]] > cy && | |
| X[sorted[last]] < X[sorted[0]] && ++x < N) { | |
| sorted.unshift(sorted.pop()); | |
| } | |
| } | |
| } | |
| } | |
| // rotate the whole circle back to compensate the shift | |
| var ax = x0 - cx, ay = y0 - cy, | |
| bx = X[start] - cx, by = Y[start] - cy; | |
| // can be NaN if the vector didn't move | |
| var theta = ax === bx ? 0 : Math.abs(Math.acos( | |
| (ax * bx + ay * by) / | |
| (Math.sqrt(ax * ax + ay * ay) * Math.sqrt(bx * bx + by * by)) | |
| )); | |
| if (theta !== 0) { | |
| var sin = Math.sin(-theta); | |
| var cos = Math.cos(-theta); | |
| var x, y, index; | |
| for (var i = 0; i < N; i++) { | |
| index = sorted[i]; | |
| // translate point back to origin: | |
| x = X[index] - cx; | |
| y = Y[index] - cy; | |
| // rotate and translate back | |
| X[index] = (x * cos - y * sin) + cx; | |
| Y[index] = (x * sin + y * cos) + cy; | |
| } | |
| } | |
| } | |
| function rotate (angle) { | |
| angle = angle * Math.PI / 180; | |
| var cx = C[0], cy = C[1]; | |
| var sin = Math.sin(angle); | |
| var cos = Math.cos(angle); | |
| var x, y; | |
| for (var i = 0; i < N; i++) { | |
| index = indexes[i]; | |
| // translate point back to origin: | |
| x = X[index] - cx; | |
| y = Y[index] - cy; | |
| // rotate and translate back | |
| X[index] = (x * cos - y * sin) + cx; | |
| Y[index] = (x * sin + y * cos) + cy; | |
| } | |
| render(); | |
| } | |
| function generate () { | |
| N = parseInt(document.querySelector('#n').value); | |
| sizes = new Array(N).fill(20).map(m => m - Math.random() * m); | |
| angles = new Array(N).fill(359).map(a => (0 + a * Math.random()) % 360); | |
| GAP = parseInt(document.querySelector('#gap').value); | |
| R = Math.min(h / 2, Math.max(20, (sizes.reduce((a, b) => a + b * 2, 0) + GAP * (sizes.length - 1)) / (2 * Math.PI))); | |
| console.log(R); | |
| angles.forEach((a, i) => { | |
| X[i] = C[0] + R * Math.sin(a * deg2rad); | |
| Y[i] = C[1] - R * Math.cos(a * deg2rad); | |
| }); | |
| // 3 nodes example | |
| // N = 3; | |
| // X = [22.021999176858913, 16.793700989603053, 17.036710556863795]; | |
| // Y = [79.80257238118364, 97.05521471469118, 92.39301694600297]; | |
| // C = [45.01420575034524, 96.18873037068559]; | |
| // R = distance(X[0], Y[0], C[0], C[1]); | |
| // sizes = [12,12,12]; | |
| // 3 nodes example | |
| // X = [-27.977495193481445, -22.992206573486328, -28.220504760742188]; | |
| // Y = [-3.795713424682617, -16.386157989501953, 0.8664843440055847]; | |
| // C = [0, 0]; | |
| // R = distance(X[0], Y[0], C[0], C[1]); | |
| // sizes = [5, 5, 5]; | |
| // double sweep example | |
| // N = 21; | |
| // X = [-99.6483154296875, -95.16764068603516, -90.74275970458984, -85.27777099609375, -107.66104888916016, -104.49362182617188, -101.25088500976562, -96.01097869873047, -77.29906463623047, -110.34211730957031, -106.17959594726562, -112.3492202758789, -84.74922943115234, -109.85372161865234, -111.34769439697266, -113.35269927978516, -113.55818176269531, -81.09383392333984, -112.11846923828125, -113.39584350585938, -113.6285629272461]; | |
| // Y = [-54.62138748168945, -62.09994888305664, -68.40348052978516, -75.10649108886719, -36.36457061767578, -44.658329010009766, -51.59013366699219, -60.78795623779297, -83.29548645019531, -27.164316177368164, -40.48675537109375, -17.056873321533203, -75.70238494873047, -29.076515197753906, 22.693044662475586, -8.028022766113281, 4.221722602844238, -79.60574340820312, -18.51302146911621, -7.393646717071533, 1.3537389039993286]; | |
| // sizes = [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]; | |
| // C = [0, 0]; | |
| // R = distance(X[0], Y[0], C[0], C[1]); | |
| svg.selectAll('circle').remove(); | |
| svg.selectAll('text').remove(); | |
| circles = svg.selectAll('circle') | |
| .data(sizes) | |
| .enter() | |
| .append('circle'); | |
| svg | |
| .append('circle') | |
| .attr('class', 'center') | |
| .attr('cx', C[0]).attr('cy', C[1]) | |
| .attr('r', 2); | |
| svg | |
| .append('circle') | |
| .attr('class', 'general') | |
| .attr('cx', C[0]).attr('cy', C[1]) | |
| .attr('stroke-dasharray', '2, 4') | |
| .attr('r', R); | |
| texts = svg.selectAll('text') | |
| .data(sizes) | |
| .enter() | |
| .append('text'); | |
| render(); | |
| } | |
| generate(); | |
| document.querySelector('#generate').addEventListener('click', generate, false); | |
| document.querySelector('#relax').addEventListener('click', () => { | |
| GAP = parseInt(document.querySelector('#gap').value) | |
| console.time('relax'); | |
| relax({ | |
| X, Y, sizes, | |
| indexes: window.indexes || sizes.map((s, i) => i), | |
| R, N, gap: GAP, | |
| center: C | |
| }); | |
| console.timeEnd('relax'); | |
| render(); | |
| }, false); |
