Skip to content

Instantly share code, notes, and snippets.

@Rantanen

Rantanen/full.html

Last active August 29, 2015 14:19
Show Gist options
  • Save Rantanen/ad9e0f501967ee7141a7 to your computer and use it in GitHub Desktop.
Save Rantanen/ad9e0f501967ee7141a7 to your computer and use it in GitHub Desktop.
Download ZIP
Fast packing hexagon with circles
Raw
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>
Raw
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 );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment