As my previous approach doesn't seem to work and a solution would be rather plex, I have decided to try another approach which might be a little bit simpler.
This time, before the code draws any hexagon, it has to determine as how many rows and columns can fit in the pre-defined circle and based on this oute it then starts drawing all the hexagons.
So far it kind of work, but as in my previous approach, there are times when the hexes are overlapping , or leaving a large gap in the lower part of the circle.
Another concern is , how do I format these hexagons into a grid?
Note, there is a small slider under the canvas, that lets you increase/decrease circle's radius and redraw the hexagons.
var c_el = document.getElementById("myCanvas");
var ctx = c_el.getContext("2d");
var canvas_width = c_el.clientWidth;
var canvas_height = c_el.clientHeight;
var circle = {
r: 120, /// radius
pos: {
x: (canvas_width / 2),
y: (canvas_height / 2)
}
}
var hexagon = {
r: 20,
pos:{
x: 0,
y: 0
}
}
var hex_w = hexagon.r * 2;
var hex_h = Math.floor( Math.sqrt(3) * hexagon.r );
var hex_s = (3/2) * hexagon.r;
fill_CircleWithHex( circle );
function fill_CircleWithHex(circle){
drawCircle( circle );
var c_h = circle.r * 2; /// circle height ////
var c_w = c_h; //// circle width /////
var max_hex_H = Math.round( c_h / hex_h );
var row_sizes = []
for(var row= 0; row< max_hex_H; row++){
var d = circle.r - ( row* hex_h); //// distance from circle's center to the row's chord ////
var c = 2 * (Math.sqrt((circle.r*circle.r) - (d * d))); /// length of the row's chord ////
var row_length = Math.floor(c / (hexagon.r * 3));
row_sizes.push( row_length )
}
console.log("circle_r : "+circle.r);
console.log("hex_r : "+hexagon.r);
console.log("max_hex_H : "+max_hex_H);
console.log("max_hex_W : ", row_sizes)
for(var row = 0; row < row_sizes.length; row++){
var max_hex_W = row_sizes[row];
var x_offset = Math.floor((c_w - (max_hex_W * hex_w)) / 2);
for(var col = 1; col < max_hex_W; col++){
hexagon.pos.x = (col * hex_w) + (circle.pos.x - circle.r) + x_offset ;
hexagon.pos.y = (row * hex_h) + (circle.pos.y - circle.r);
ctx.fillText(row+""+col, hexagon.pos.x - 6, hexagon.pos.y+4);
drawHexagon(hexagon)
}
}
}
function drawHexagon(hex){
var angle_deg, angle_rad, cor_x, cor_y;
ctx.beginPath();
for(var c=0; c <= 5; c++){
angle_deg = 60 * c;
angle_rad = (Math.PI / 180) * angle_deg;
cor_x = hex.r * Math.cos(angle_rad); //// corner_x ///
cor_y = hex.r* Math.sin(angle_rad); //// corner_y ///
if(c === 0){
ctx.moveTo(hex.pos.x+ cor_x, hex.pos.y+cor_y);
}else{
ctx.lineTo(hex.pos.x+cor_x, hex.pos.y+cor_y);
}
}
ctx.closePath();
ctx.stroke();
}
function drawCircle( circle ){
ctx.beginPath();
ctx.arc(circle.pos.x, circle.pos.y, circle.r, 0, 2 * Math.PI);
ctx.stroke();
}
$(function() {
$( "#slider" ).slider({
max: 200,
min:0,
value:100,
create: function( event, ui ) {
$("#value").html( $(this).slider('value') );
},
change: function( event, ui ) {
$("#value").html(ui.value);
},
slide: function( event, ui){
$("#value").html(ui.value);
circle.r = ui.value;
ctx.clearRect(0,0, canvas_width, canvas_height);
fill_CircleWithHex(circle);
}
});
});<script src=".11.1/jquery.min.js"></script>
<link href=".11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src=".11.4/jquery-ui.min.js"></script>
<canvas id="myCanvas" width="350" height="250" style="border:1px solid #d3d3d3;"> </canvas>
<div style="width: 200px; height: 40px;">
<div id="slider" style="position:relative; width: 150px; top: 4px;float: left;"></div> <div id="value" style="float: left;"> 0 </div>
</div>As my previous approach doesn't seem to work and a solution would be rather plex, I have decided to try another approach which might be a little bit simpler.
This time, before the code draws any hexagon, it has to determine as how many rows and columns can fit in the pre-defined circle and based on this oute it then starts drawing all the hexagons.
So far it kind of work, but as in my previous approach, there are times when the hexes are overlapping , or leaving a large gap in the lower part of the circle.
Another concern is , how do I format these hexagons into a grid?
Note, there is a small slider under the canvas, that lets you increase/decrease circle's radius and redraw the hexagons.
var c_el = document.getElementById("myCanvas");
var ctx = c_el.getContext("2d");
var canvas_width = c_el.clientWidth;
var canvas_height = c_el.clientHeight;
var circle = {
r: 120, /// radius
pos: {
x: (canvas_width / 2),
y: (canvas_height / 2)
}
}
var hexagon = {
r: 20,
pos:{
x: 0,
y: 0
}
}
var hex_w = hexagon.r * 2;
var hex_h = Math.floor( Math.sqrt(3) * hexagon.r );
var hex_s = (3/2) * hexagon.r;
fill_CircleWithHex( circle );
function fill_CircleWithHex(circle){
drawCircle( circle );
var c_h = circle.r * 2; /// circle height ////
var c_w = c_h; //// circle width /////
var max_hex_H = Math.round( c_h / hex_h );
var row_sizes = []
for(var row= 0; row< max_hex_H; row++){
var d = circle.r - ( row* hex_h); //// distance from circle's center to the row's chord ////
var c = 2 * (Math.sqrt((circle.r*circle.r) - (d * d))); /// length of the row's chord ////
var row_length = Math.floor(c / (hexagon.r * 3));
row_sizes.push( row_length )
}
console.log("circle_r : "+circle.r);
console.log("hex_r : "+hexagon.r);
console.log("max_hex_H : "+max_hex_H);
console.log("max_hex_W : ", row_sizes)
for(var row = 0; row < row_sizes.length; row++){
var max_hex_W = row_sizes[row];
var x_offset = Math.floor((c_w - (max_hex_W * hex_w)) / 2);
for(var col = 1; col < max_hex_W; col++){
hexagon.pos.x = (col * hex_w) + (circle.pos.x - circle.r) + x_offset ;
hexagon.pos.y = (row * hex_h) + (circle.pos.y - circle.r);
ctx.fillText(row+""+col, hexagon.pos.x - 6, hexagon.pos.y+4);
drawHexagon(hexagon)
}
}
}
function drawHexagon(hex){
var angle_deg, angle_rad, cor_x, cor_y;
ctx.beginPath();
for(var c=0; c <= 5; c++){
angle_deg = 60 * c;
angle_rad = (Math.PI / 180) * angle_deg;
cor_x = hex.r * Math.cos(angle_rad); //// corner_x ///
cor_y = hex.r* Math.sin(angle_rad); //// corner_y ///
if(c === 0){
ctx.moveTo(hex.pos.x+ cor_x, hex.pos.y+cor_y);
}else{
ctx.lineTo(hex.pos.x+cor_x, hex.pos.y+cor_y);
}
}
ctx.closePath();
ctx.stroke();
}
function drawCircle( circle ){
ctx.beginPath();
ctx.arc(circle.pos.x, circle.pos.y, circle.r, 0, 2 * Math.PI);
ctx.stroke();
}
$(function() {
$( "#slider" ).slider({
max: 200,
min:0,
value:100,
create: function( event, ui ) {
$("#value").html( $(this).slider('value') );
},
change: function( event, ui ) {
$("#value").html(ui.value);
},
slide: function( event, ui){
$("#value").html(ui.value);
circle.r = ui.value;
ctx.clearRect(0,0, canvas_width, canvas_height);
fill_CircleWithHex(circle);
}
});
});<script src="https://ajax.googleapis./ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare./ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis./ajax/libs/jqueryui/1.11.4/jquery-ui.min.js"></script>
<canvas id="myCanvas" width="350" height="250" style="border:1px solid #d3d3d3;"> </canvas>
<div style="width: 200px; height: 40px;">
<div id="slider" style="position:relative; width: 150px; top: 4px;float: left;"></div> <div id="value" style="float: left;"> 0 </div>
</div>- I'm confused. Are the sizes of both hexagon & circle given? Can you state the problem more precisely? What are the hard constraints & what are you trying to maximize. – curious_cat Commented Feb 26, 2016 at 10:57
- the hard constrain is the circle's size, based on this the hexagon grid is being generated. – Alexus Commented Feb 26, 2016 at 11:04
- Does it just have to look like a hexagon pattern? Do the hexagons have to be numbered? I'm thinking of just applying smart css backgrounds to generate a hexagon style. – Paul Commented Feb 26, 2016 at 11:13
- it has to be formed in hexagon grid as I'm using the count of all hexagons placed in each row in other calculations. The numbers are then stored in hexagon properties, to figure out the relations between hexagons. But all that's not part of this problem. – Alexus Commented Feb 26, 2016 at 11:26
- What about the size of the hexagons? The smaller the hexagon the more you can pack in there. Is hexagon size fixed too? Sorry if I am missing something obvious here. – curious_cat Commented Feb 26, 2016 at 11:40
3 Answers
Reset to default 6 +50The following solves the packing problem for a regular honeyb structure centered on the circle's midpoint. Regular means:
- the set of all hexagons is symmetric under 60 deg rotations around the circle's center.
The coordinates of the individual hexagons represent the ordinal number of the hexagon shell countered from the center and the clockwise sequence number starting at high noon.
As the circle widens, new hexagon shells do not necessarily get filled as a whole. Though the degree of freedom to fill the outer shell partially produces an improved solution, it is still not optimal. Relaxing the regularity to rotational symmetries wrt other angles than 60 deg ( namely 120 and 180 deg ) will permit a higher coverage of the circle's interior.
I shall look into the math behind that for the next revision of this code (and possibly find a theorem to prove rotational symmetry around the circle'smidpoint is a necessary condition for optimality).
var c_el;
var ctx;
var canvas_width;
var canvas_height;
var circle;
var hexagon;
var hex_w;
var hex_h;
var hex_s;
var delta;
function drawHexagonAt ( po_ctr_hex, pn_circle, pn_sector ) {
var cur
;
cur = { x: po_ctr_hex.x - 0.5 * hexagon.r, y: po_ctr_hex.y - delta };
ctx.beginPath();
ctx.moveTo(cur.x, cur.y);
cur.x = cur.x + hexagon.r;
cur.y = cur.y;
ctx.lineTo(cur.x, cur.y);
cur.x = cur.x + hexagon.r / 2;
cur.y = cur.y + delta;
ctx.lineTo(cur.x, cur.y);
cur.x = cur.x - hexagon.r / 2;
cur.y = cur.y + delta;
ctx.lineTo(cur.x, cur.y);
cur.x = cur.x - hexagon.r;
cur.y = cur.y;
ctx.lineTo(cur.x, cur.y);
cur.x = cur.x - hexagon.r / 2;
cur.y = cur.y - delta;
ctx.lineTo(cur.x, cur.y);
cur.x = cur.x + hexagon.r / 2;
cur.y = cur.y - delta;
ctx.lineTo(cur.x, cur.y);
ctx.closePath();
ctx.stroke();
cur.x = cur.x + hexagon.r / 2;
cur.y = cur.y + delta;
ctx.fillText(pn_circle + "/" + pn_sector, cur.x-6, cur.y+4);
} // drawHexagonAt
function fill_CircleWithHex(circle){
drawCircle( circle );
var radacc2;
var iter = 0;
var sector = 0;
var i, j;
var ctr = { x: circle.pos.x , y: circle.pos.y };
var cur = { x: 0 , y: 0 };
delta = Math.floor(Math.sqrt(3) * 0.5 * hexagon.r);
radacc2 = hexagon.r * hexagon.r;
while ( (radacc2 < circle.r * circle.r) ) {
cur.x = ctr.x;
cur.y = ctr.y - iter * 2 * delta;
if (iter === 0) {
drawHexagonAt ( cur, 0, 0 );
}
else {
for ( var i=0; i < 6; i++ ) {
// j-loops -- next honeyb
sector = 0;
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x + 1.5 * hexagon.r;
cur.y = cur.y + delta;
drawHexagonAt ( cur, iter, sector++ );
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x;
cur.y = cur.y + 2 * delta;
drawHexagonAt ( cur, iter, sector++ );
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x - 1.5 * hexagon.r;
cur.y = cur.y + delta;
drawHexagonAt ( cur, iter, sector++ );
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x - 1.5 * hexagon.r;
cur.y = cur.y - delta;
drawHexagonAt ( cur, iter, sector++ );
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x;
cur.y = cur.y - 2 * delta;
drawHexagonAt ( cur, iter, sector++ );
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x + 1.5 * hexagon.r;
cur.y = cur.y - delta;
drawHexagonAt ( cur, iter, sector++ );
}
} // i-loop -- meta-honeyb
} // if -- Iteration 1 vs. n > 1
// radacc update
iter++;
radacc2 = ((2*iter + 1) * delta) * ((2*iter + 1) * delta) + hexagon.r * hexagon.r / 4;
} // while -- komplette Shells
//
// Partielle Shells
//
var proceed;
do {
cur.x = ctr.x;
cur.y = ctr.y - iter * 2 * delta;
proceed = false;
for ( var i=0; i < 6; i++ ) {
// j-loops -- next honeyb
sector = 0;
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x + 1.5 * hexagon.r;
cur.y = cur.y + delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x;
cur.y = cur.y + 2 * delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x - 1.5 * hexagon.r;
cur.y = cur.y + delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x - 1.5 * hexagon.r;
cur.y = cur.y - delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x;
cur.y = cur.y - 2 * delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
for ( var j=0; j < iter; j++ ) {
cur.x = cur.x + 1.5 * hexagon.r;
cur.y = cur.y - delta;
sector++
if ( Math.sqrt ( ( cur.x - ctr.x) * ( cur.x - ctr.x) + ( cur.y - ctr.y) * ( cur.y - ctr.y) ) + hexagon.r < circle.r ) {
drawHexagonAt ( cur, iter, sector );
proceed = true;
}
}
} // i-loop -- meta-honeyb
iter++;
} while (proceed && (iter < 15));
} // fill_CircleWithHex
function drawCircle( circle ){
ctx.beginPath();
ctx.arc(circle.pos.x, circle.pos.y, circle.r, 0, 2 * Math.PI);
ctx.stroke();
}
$(function() {
$( "#slider" ).slider({
max: 200,
min:0,
value:100,
create: function( event, ui ) {
$("#value").html( $(this).slider('value') );
},
change: function( event, ui ) {
$("#value").html(ui.value);
},
slide: function( event, ui){
$("#value").html(ui.value);
circle.r = ui.value;
ctx.clearRect(0,0, canvas_width, canvas_height);
fill_CircleWithHex(circle);
}
});
});
$(document).ready(function () {
c_el = document.getElementById("myCanvas");
ctx = c_el.getContext("2d");
canvas_width = c_el.clientWidth;
canvas_height = c_el.clientHeight;
circle = {
r: 120, /// radius
pos: {
x: (canvas_width / 2),
y: (canvas_height / 2)
}
};
hexagon = {
r: 20,
pos:{
x: 0,
y: 0
}
};
hex_w = hexagon.r * 2;
hex_h = Math.floor( Math.sqrt(3) * hexagon.r );
hex_s = (3/2) * hexagon.r;
fill_CircleWithHex( circle );
});<script src="https://ajax.googleapis./ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare./ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis./ajax/libs/jqueryui/1.11.4/jquery-ui.min.js"></script>
<canvas id="myCanvas" width="350" height="250" style="border:1px solid #d3d3d3;"> </canvas>
<div style="width: 200px; height: 40px;">
<div id="slider" style="position:relative; width: 150px; top: 4px;float: left;"></div> <div id="value" style="float: left;"> 0 </div>
</div>Spent some time on your code to pack the hex's. Its not perfect and am sure there is a better way to do this. Check it out if it helps, or if you could fix the hex's stepping out of the circle [now, there is an issue with calculation of row_sizes]. Maybe I can look at it again whenever I get time, or we can look at other ways to do this.
var c_el = document.getElementById("myCanvas");
var ctx = c_el.getContext("2d");
var canvas_width = c_el.clientWidth;
var canvas_height = c_el.clientHeight;
var circle = {
r: 120, /// radius
pos: {
x: (canvas_width / 2),
y: (canvas_height / 2)
}
}
var hexagon = {
r: 20,
pos:{
x: 0,
y: 0
}
}
var hex_w = hexagon.r * 3; /// added spacing
var hex_h = Math.floor( Math.sqrt(3) * hexagon.r / 2 ); /// added spacing
var hex_s = (3/2) * hexagon.r;
var hex_width = 33.4; //based on r = 20
fill_CircleWithHex( circle );
function fill_CircleWithHex(circle){
drawCircle( circle );
var c_h = circle.r * 2; /// circle height ////
var c_w = c_h; //// circle width /////
var max_hex_H = Math.round( c_h / ( hex_h ));
var row_sizes = []
for(var col= 0; col < max_hex_H; col++){
var d = circle.r - ( col * hex_h ); //// distance from circle's center to the row's chord ////
var c = 2 * (Math.sqrt((circle.r*circle.r) - (d * d))); /// length of the row's chord ////
row_sizes.push( Math.ceil(c / (hexagon.r * 3)) )
}
for(var row = 0; row < row_sizes.length; row++){
var max_hex_W = row_sizes[row];
console.log(hex_w);
var x_offset = Math.floor((c_w - (max_hex_W * hex_w))) + row%2 * hex_width - hex_width/2; // changed offset to define a zig zag
for(var col = 1; col < max_hex_W; col++){
hexagon.pos.x = (col * hex_w) + (circle.pos.x - circle.r) + x_offset ;
hexagon.pos.y = (row * 17.3) + (circle.pos.y - circle.r) ;
ctx.fillText(row+""+col, hexagon.pos.x - 6, hexagon.pos.y+4);
drawHexagon(hexagon)
}
}
}
function drawHexagon(hex){
var angle_deg, angle_rad, cor_x, cor_y;
ctx.beginPath();
for(var c=0; c <= 5; c++){
angle_deg = 60 * c;
angle_rad = (Math.PI / 180) * angle_deg;
cor_x = hex.r * Math.cos(angle_rad); //// corner_x ///
cor_y = hex.r* Math.sin(angle_rad); //// corner_y ///
if(c === 0){
ctx.moveTo(hex.pos.x+ cor_x, hex.pos.y+cor_y);
}else{
ctx.lineTo(hex.pos.x+cor_x, hex.pos.y+cor_y);
}
}
ctx.closePath();
ctx.stroke();
}
function drawCircle( circle ){
ctx.beginPath();
ctx.arc(circle.pos.x, circle.pos.y, circle.r, 0, 2 * Math.PI);
ctx.stroke();
}
$(function() {
$( "#slider" ).slider({
max: 200,
min:0,
value:100,
create: function( event, ui ) {
$("#value").html( $(this).slider('value') );
},
change: function( event, ui ) {
$("#value").html(ui.value);
},
slide: function( event, ui){
$("#value").html(ui.value);
circle.r = ui.value;
ctx.clearRect(0,0, canvas_width, canvas_height);
fill_CircleWithHex(circle);
}
});
});<script src="https://ajax.googleapis./ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare./ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis./ajax/libs/jqueryui/1.11.4/jquery-ui.min.js"></script>
<canvas id="myCanvas" width="350" height="250" style="border:1px solid #d3d3d3;"> </canvas>
<div style="width: 200px; height: 40px;">
<div id="slider" style="position:relative; width: 150px; top: 4px;float: left;"></div> <div id="value" style="float: left;"> 0 </div>
</div>The short answer: there is no easy way to do this. You have too many special cases. To illustrate that, start simple with 1, 2, 3, 4, 6 and 7 hexagons, draw the minimum circle that will fit over them, and make note where the center of the circle ends up.
As you can see the center of the circle moves around quite a bit. It can end up in the middle of a hexagon, on a vertex or a junction.
From then on it only gets worse.
The closest I could find on this problem is this page.
EDIT: You may want to check out the following blog page for a very prehensive treatment on hexagons in programming.
http://www.redblobgames./grids/hexagons/