Rantanen/full.html

## full.html
<!doctype HTML>
<html>
<head>
</head>
<body>
<h1>Packing hexagon with circles</h1>
<canvas id="canvas1" width="1000" height="800"></canvas>
<h1>Intermediate (u,v) coordinates</h1>
<canvas id="canvas2" width="1000" height="1000"></canvas>
<script>

// Our parameters
var radius_m = 400;
var diameter_circle = 10;

// A magic number we'll calculate here just to save some performance later.
// Ignore for now.
var magic = Math.sqrt( 3.0 ) / 6.0 - 0.5;

// Calculate how many circles there will be one one of the hexagon "spokes":
//           _____________
//          /o           /\
//         /  o         /  \
//        /    o       /    \
//       /      o     /      \
//      /        o   /        \
//     /          o /          \
//    /____________o____________\
//    \           / \           /
//
var radius = Math.floor( radius_m / diameter_circle );

// Let's assume vectors u and v that draw the hexagon:
//
// In (x,y) space the hexagon looks like:
//        ______
//       /\     \
//      /  \     \
//     /____\ ____\
//     ^     \    /
//     u\     \  /
//       \ ___>\/
//          v
//       (Fig 1)
//
// Two of the triangle edges are omitted in the figure above, because...
// In (u,v) vector space the hexagon is tilted:
//            ____
//          /|    |
//        /  |    |
//      /____|____|
//      ^    |    /
//    u |    |  /
//      |___>|/
//        v
//       (Fig 2)
//
// Assuming the centerpoint is (0,0) this means the "hexagon" is contained in a
// square going from:
//
//
//              / u = v + 1
//    1       /___
//          /|    |     / u = v - 1
//        /  |    |   /
//      /____|____| /
//    / ^    |    /
//  /   |    |  /
//   -1 |___>|/
//          /
//     -1         1
//        (Fig 3)
//
// So essentially the whole hexagon in (u,v) space is defined as:
//
// { (u,v) : -1 < u < 1 && -1 < v < 1 && u < v + 1 && u > v - 1 }
//
// To scale the hexagon we'll just substitute 1 and -1 with radius and -radius
// defined above.

var uv_circles = [];
var circles = [];
var start = Date.now();

// This gives us the following for loop which spans the full square (ignoring
// clipped corners).
for( var u = -radius; u <= radius; u++ ) {
    for( var v = -radius; v <= radius; v++ ) {

        // To remove the clipped corners we need to ignore the cases where:
        // u > v + 1 or u < v - 1
        if( u > v + radius || u < v - radius )
            continue;

        // Now (u,v) will span the Fig 2 shape.
        uv_circles.push([ u, v ]);

        // Now we could use some fancy vector maths to turn the (u,v)
        // coordinates into (x,y) coordinates suitable for the mercerator, but
        // if we use one more trick we can optimize that transformation.
        //
        // Instead of having the vectors spanning (x,y) shape in Fig 1, we can
        // rotate the diamonds a bit:
        //
        // ______       \''---,,
        // \     \       \      \
        //  \     \  =>   \      \
        //   \_____\       ''---,,\
        //           (Fig 4)
        //
        // Now instead of being sheared like the original shape the new shape
        // is only scaled along the diagonal. This makes it easy to transform
        // the square-(u,v) shape into the diamond shape required for the
        // hexagon by offsetting the points by their distance.
        //
        // Although the scaling changes the magnitude of the coordinates so we
        // need to further scale the x/y coordiantes with ( 1 - magic )
        //
        // 'magic' here is a number I won't explain in detail (as I can't
        // remember the formulas I used to calculate it in the first place.
        // :p). Essentially it's the answer to:
        //
        //    How much a point u or v must be offset to turn square from Fig 2
        //    into the diamond in Fig 4.
        //
        var offset = ( u + v ) * magic;
        x = ( u + offset ) * ( 1 - magic );
        y = ( v + offset ) * ( 1 - magic );

        // This gives us coordinates in our ideal coordinate system. For the
        // real world coordinates these need to be further scaled by the circle
        // diameter.
        x *= diameter_circle;
        y *= diameter_circle;

        circles.push([ x, y ]);
    }
}

// Report performance
console.log( circles.length + ' circles generated in ' + ( Date.now() - start ) + ' ms' );

// Let's draw the circles for fun.
//
// Our canvas.
var canvas = document.getElementById( 'canvas1' );
var context = canvas.getContext( '2d' );
var centerX = canvas.width / 2;
var centerY = canvas.height / 2;

// Let's first draw the ideal circle:
context.beginPath();
context.arc(
    centerX,
    centerY,
    radius_m,
    0, 2 * Math.PI, false );
context.strokeStyle = '#ff0000';
context.stroke();

start = Date.now();
for( var c in circles ) {
    var x = circles[c][0];
    var y = circles[c][1];

    // Now (u,v) will span the Fig 2 shape.
    context.beginPath();
    context.arc(
        x + centerX,
        y + centerY,
        diameter_circle / 2,
        0, 2 * Math.PI, false );
    context.strokeStyle = '#00ff00';
    context.stroke();
}

// Report performance
console.log( circles.length + ' circles drawn in ' + ( Date.now() - start ) + ' ms' );

// For visualization let's draw the (u,v) circles as well.
var canvas = document.getElementById( 'canvas2' );
var context = canvas.getContext( '2d' );
var centerX = canvas.width / 2;
var centerY = canvas.height / 2;

start = Date.now();
for( var c in uv_circles ) {
    var x = uv_circles[c][0];
    var y = uv_circles[c][1];

    // Now (u,v) will span the Fig 2 shape.
    context.beginPath();
    context.arc(
        x * diameter_circle + centerX,
        y * diameter_circle + centerY,
        diameter_circle / 2,
        0, 2 * Math.PI, false );
    context.strokeStyle = '#00ff00';
    context.stroke();
}
</script>
</html>

## minimal.js
// The essential function without comments:

var radius_m = 400;
var diameter_circle = 10;
var radius = Math.floor( radius_m / diameter_circle );

var magic = Math.sqrt( 3.0 ) / 6.0 - 0.5;
var circles = [];
for( var u = -radius; u <= radius; u++ ) {
    for( var v = -radius; v <= radius; v++ ) {

        if( u > v + radius || u < v - radius )
            continue;

        var offset = ( u + v ) * magic;
        circles.push([
          ( u + offset ) * ( 1 - magic ) * diameter_circle,  // x
          ( v + offset ) * ( 1 - magic ) * diameter_circle,  // y
        });
    }
}

console.log( circles );
	<!doctype HTML>
	<html>
	<head>
	</head>
	<body>
	<h1>Packing hexagon with circles</h1>
	<canvas id="canvas1" width="1000" height="800"></canvas>
	<h1>Intermediate (u,v) coordinates</h1>
	<canvas id="canvas2" width="1000" height="1000"></canvas>
	<script>

	// Our parameters
	var radius_m = 400;
	var diameter_circle = 10;

	// A magic number we'll calculate here just to save some performance later.
	// Ignore for now.
	var magic = Math.sqrt( 3.0 ) / 6.0 - 0.5;

	// Calculate how many circles there will be one one of the hexagon "spokes":
	// _____________
	// /o /\
	// / o / \
	// / o / \
	// / o / \
	// / o / \
	// / o / \
	// /____________o____________\
	// \ / \ /
	//
	var radius = Math.floor( radius_m / diameter_circle );

	// Let's assume vectors u and v that draw the hexagon:
	//
	// In (x,y) space the hexagon looks like:
	// ______
	// /\ \
	// / \ \
	// /____\ ____\
	// ^ \ /
	// u\ \ /
	// \ ___>\/
	// v
	// (Fig 1)
	//
	// Two of the triangle edges are omitted in the figure above, because...
	// In (u,v) vector space the hexagon is tilted:
	// ____
	// /\| \|
	// / \| \|
	// /____\|____\|
	// ^ \| /
	// u \| \| /
	// \|___>\|/
	// v
	// (Fig 2)
	//
	// Assuming the centerpoint is (0,0) this means the "hexagon" is contained in a
	// square going from:
	//
	//
	// / u = v + 1
	// 1 /___
	// /\| \| / u = v - 1
	// / \| \| /
	// /____\|____\| /
	// / ^ \| /
	// / \| \| /
	// -1 \|___>\|/
	// /
	// -1 1
	// (Fig 3)
	//
	// So essentially the whole hexagon in (u,v) space is defined as:
	//
	// { (u,v) : -1 < u < 1 && -1 < v < 1 && u < v + 1 && u > v - 1 }
	//
	// To scale the hexagon we'll just substitute 1 and -1 with radius and -radius
	// defined above.

	var uv_circles = [];
	var circles = [];
	var start = Date.now();

	// This gives us the following for loop which spans the full square (ignoring
	// clipped corners).
	for( var u = -radius; u <= radius; u++ ) {
	for( var v = -radius; v <= radius; v++ ) {

	// To remove the clipped corners we need to ignore the cases where:
	// u > v + 1 or u < v - 1
	if( u > v + radius \|\| u < v - radius )
	continue;

	// Now (u,v) will span the Fig 2 shape.
	uv_circles.push([ u, v ]);

	// Now we could use some fancy vector maths to turn the (u,v)
	// coordinates into (x,y) coordinates suitable for the mercerator, but
	// if we use one more trick we can optimize that transformation.
	//
	// Instead of having the vectors spanning (x,y) shape in Fig 1, we can
	// rotate the diamonds a bit:
	//
	// ______ \''---,,
	// \ \ \ \
	// \ \ => \ \
	// \_____\ ''---,,\
	// (Fig 4)
	//
	// Now instead of being sheared like the original shape the new shape
	// is only scaled along the diagonal. This makes it easy to transform
	// the square-(u,v) shape into the diamond shape required for the
	// hexagon by offsetting the points by their distance.
	//
	// Although the scaling changes the magnitude of the coordinates so we
	// need to further scale the x/y coordiantes with ( 1 - magic )
	//
	// 'magic' here is a number I won't explain in detail (as I can't
	// remember the formulas I used to calculate it in the first place.
	// :p). Essentially it's the answer to:
	//
	// How much a point u or v must be offset to turn square from Fig 2
	// into the diamond in Fig 4.
	//
	var offset = ( u + v ) * magic;
	x = ( u + offset ) * ( 1 - magic );
	y = ( v + offset ) * ( 1 - magic );

	// This gives us coordinates in our ideal coordinate system. For the
	// real world coordinates these need to be further scaled by the circle
	// diameter.
	x *= diameter_circle;
	y *= diameter_circle;

	circles.push([ x, y ]);
	}
	}

	// Report performance
	console.log( circles.length + ' circles generated in ' + ( Date.now() - start ) + ' ms' );

	// Let's draw the circles for fun.
	//
	// Our canvas.
	var canvas = document.getElementById( 'canvas1' );
	var context = canvas.getContext( '2d' );
	var centerX = canvas.width / 2;
	var centerY = canvas.height / 2;

	// Let's first draw the ideal circle:
	context.beginPath();
	context.arc(
	centerX,
	centerY,
	radius_m,
	0, 2 * Math.PI, false );
	context.strokeStyle = '#ff0000';
	context.stroke();

	start = Date.now();
	for( var c in circles ) {
	var x = circles[c][0];
	var y = circles[c][1];

	// Now (u,v) will span the Fig 2 shape.
	context.beginPath();
	context.arc(
	x + centerX,
	y + centerY,
	diameter_circle / 2,
	0, 2 * Math.PI, false );
	context.strokeStyle = '#00ff00';
	context.stroke();
	}

	// Report performance
	console.log( circles.length + ' circles drawn in ' + ( Date.now() - start ) + ' ms' );

	// For visualization let's draw the (u,v) circles as well.
	var canvas = document.getElementById( 'canvas2' );
	var context = canvas.getContext( '2d' );
	var centerX = canvas.width / 2;
	var centerY = canvas.height / 2;

	start = Date.now();
	for( var c in uv_circles ) {
	var x = uv_circles[c][0];
	var y = uv_circles[c][1];

	// Now (u,v) will span the Fig 2 shape.
	context.beginPath();
	context.arc(
	x * diameter_circle + centerX,
	y * diameter_circle + centerY,
	diameter_circle / 2,
	0, 2 * Math.PI, false );
	context.strokeStyle = '#00ff00';
	context.stroke();
	}
	</script>
	</html>
	// The essential function without comments:

	var radius_m = 400;
	var diameter_circle = 10;
	var radius = Math.floor( radius_m / diameter_circle );

	var magic = Math.sqrt( 3.0 ) / 6.0 - 0.5;
	var circles = [];
	for( var u = -radius; u <= radius; u++ ) {
	for( var v = -radius; v <= radius; v++ ) {

	if( u > v + radius \|\| u < v - radius )
	continue;

	var offset = ( u + v ) * magic;
	circles.push([
	( u + offset ) * ( 1 - magic ) * diameter_circle, // x
	( v + offset ) * ( 1 - magic ) * diameter_circle, // y
	});
	}
	}

	console.log( circles );