Skip to content

Instantly share code, notes, and snippets.

💭
learning

Alexander Milevski w8r

💭
learning
View GitHub Profile
@w8r
w8r / mindisc.js
Created Aug 27, 2018
Minimum enclosing disc
View mindisc.js
function circleContainsCircle(cx, cy, cr, x, y, r) {
const dx = cx - x;
const dy = cy - y;
const dr = cr - r;
// reduce precision not to deal with square roots
return (dx * dx + dy * dy) < (dr * dr + 1e-6);
}
function from2discs(ax, ay, bx, by, ar, br) {
const dx = bx - ax;
@w8r
w8r / sortedArrayToBST.js
Created Aug 21, 2018
Non-recursive BST build from sorted array
View sortedArrayToBST.js
export default function sortedArrayToBST(data) {
let root = {};
const Q = [root];
const stack = [0, data.length - 1];
while (Q.length !== 0) {
const right = stack.pop();
const left = stack.pop();
const cur = Q.pop();
@w8r
w8r / clz.js
Created Aug 17, 2018
Count leading zeros
View clz.js
/**
* Count leading zeros in binary representation
* @param {number} m
* @return {number} 0-32
*/
export default function clz(m) {
let c = 1 << 31, i;
for (let i = 0; i < 32; i += 1) {
if (c & m) return i;
c >>>= 1;
@w8r
w8r / sigly_list.js
Created Aug 2, 2018
sibly linked list
View sigly_list.js
export default class SinglyList {
constructor () {
this._length = 0;
this.head = null;
}
add (value) {
const newNode = new { data: value, next: null };
let current = this.head;
@w8r
w8r / .block
Last active Aug 1, 2018
Transferrable objects demo
View .block
license: mit
height: 500
border: no
@w8r
w8r / graph-quadtree.cpp
Created Jul 30, 2018
PMR Edges-quadtree for a graph GNU license, (C) 2005 Scott Czepiel <http://czep.net/>
View graph-quadtree.cpp
///////////////////////////////////////////////////////////////////////////
// This file is part of Quicksilver - a bike messenger simulation game //
// Copyright (C) 2005 Scott Czepiel <http://czep.net/> //
// //
// This program is free software; you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation; either version 2 of the License, or //
// (at your option) any later version. //
// //
// This program is distributed in the hope that it will be useful, //
View ball-tree.js
// class BallTree {
// constructor (points) {
// const X = new Array(points.length);
// const Y = new Array(points.length);
// for (let i = 0; i < points.length; i++) X[i] = Y[i] = i;
// X.sort((a, b) => points[a].x - points[b].x);
// Y.sort((a, b) => points[a].y - points[b].y);
@w8r
w8r / Readme.md
Last active Jul 26, 2018
Simple recursive quadtree (slow)
View Readme.md

Simple recursive quadtree

This one is quite slow due to function calls in recursion, and naive splitting.

It runs in about 300ms for 125k points (MBP 2.7 GHz Intel Core i5)

  • 1 more Array per node → +100ms
  • implement as a class → +100ms
View event_emitter.js
var isArray = Array.isArray;
class EventTarget {
/**
* @param {string} name
* @param {function} cb
* @return {EventTarget}
*/
@w8r
w8r / d3-verlet.js
Created Jun 29, 2018
d3 corrected verlet
View d3-verlet.js
function tick() {
var i, n = nodes.length, node;
alpha += (alphaTarget - alpha) * alphaDecay;
iterations++;
forces.each(function(force) {
force(alpha);
});
You can’t perform that action at this time.