| license: mit |
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.
forked from w8r's block: Removing overlaps on radial layout
| <!doctype html> | |
| <html> | |
| <head> | |
| <title>Remove overlaps on a radial layout</title> | |
| <script src="https://unpkg.com/[email protected]"></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; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div class="control"> | |
| <h4>Remove overlaps on a radial layout</h4> | |
| <p><label><input id="n" value="30" type="number" min="0" step="1" /> Vertices</label></p> | |
| <p><label><input id="gap" value="5" 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] | |
| ]; | |
| } | |
| function relax ({ X, Y, sizes, indexes, R, N, center, gap }) { | |
| N = indexes.length; | |
| let I = N; | |
| let cx = center[0], | |
| cy = center[1]; | |
| let sorted = indexes.sort((a, b) => { | |
| return compare(X[a], Y[a], X[b], Y[b], cx, cy); | |
| }); | |
| console.log(sorted, center, sorted.length, N); | |
| 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); | |
| 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 * 10, 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(30).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 = (sizes.reduce((a, b) => a + b * 2, 0) + GAP * 3 * (sizes.length - 1)) / (2 * Math.PI); | |
| angles.forEach((a, i) => { | |
| X[i] = C[0] + R * Math.sin(a * deg2rad); | |
| Y[i] = C[1] - R * Math.cos(a * deg2rad); | |
| }); | |
| // X = [ | |
| // 75.82254791259766, | |
| // 43.08230972290039, | |
| // 26.89663314819336, | |
| // 19.295494079589844, | |
| // 21.451080322265625, | |
| // 33.03097915649414, | |
| // 52.24942398071289, | |
| // 76.14268493652344, | |
| // 101.02611541748047, | |
| // 123.0624008178711, | |
| // 138.85324096679688, | |
| // 145.96351623535156, | |
| // 143.2967071533203, | |
| // 131.2640838623047, | |
| // 111.72122955322266, | |
| // 100.71785736083984 | |
| // ]; | |
| // Y = [ | |
| // 66.19557189941406, | |
| // 52.83225631713867, | |
| // 33.77907180786133, | |
| // 9.962634086608887, | |
| // -14.944262504577637, | |
| // -37.10065841674805, | |
| // -53.08976364135742, | |
| // -60.44585418701172, | |
| // -58.03452682495117, | |
| // -46.22765350341797, | |
| // -26.845979690551758, | |
| // -2.8784143924713135, | |
| // 21.97894287109375, | |
| // 43.89277267456055, | |
| // 59.48369216918945, | |
| // 63.91008758544922 | |
| // ]; | |
| // sizes = [ | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10, | |
| // 10 | |
| // ]; | |
| // C = [ | |
| // 82.56354522705078, | |
| // 2.8914947509765625 | |
| // ]; | |
| // R = 63.661979412695295; | |
| 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); | |
| 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); |