| /** | |
| * This is a comparator for two points to position them along the circle around C(x,y) | |
| * | |
| * @example | |
| * points.sort(function (a, b) { | |
| * return comparator(a.x, a.y, bx, b.y, c.x, c.y); | |
| * }); | |
| * | |
| * @param {number} ax | |
| * @param {number} ay |
| /** | |
| * 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 |
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.
| // Prototype of a utility function to swap two integers | |
| const swap = (arr, x, y) => { | |
| let tmp = arr[x]; | |
| arr[x] = arr[y]; | |
| arr[y] = tmp; | |
| }; | |
| const parent = (index) => Math.floor((index - 1) / 2); | |
| /** | |
| * Min heap priority queue implementation | |
| * | |
| * @param {Array} [arr] [[]] | |
| * @param {function (a:number, b:number)} [cmp] [function (a, b) { return a - b; }] Comparator | |
| * @return {Object} | |
| */ | |
| const heap = function (arr, cmp = (a, b) => a - b) { | |
| /** |
Christiaan Huygens arc length approximation through the arc height and chord length
Simple directed layout to pack different-sized circles as close as possible
This is an implementation of Welzl (1991) algorithm of smallest enclosing circle. Uses some parts of Mike Bostock's code for circumscribed discs.
Move points around and click to add new ones.
| function minHeap (cmp, arr = []) { | |
| const up = (i) => { | |
| let object = arr[i]; | |
| while (i > 0) { | |
| let up = ((i + 1) >> 1) - 1, | |
| parent = arr[up]; | |
| if (cmp(object, parent) >= 0) break; | |
| arr[parent.index = i] = parent; | |
| arr[object.index = i = up] = object; |
| license: gpl-3.0 | |
| height: 960 |
