用六边形填充圆形(另一种方法)

13

由于我的先前方法似乎不起作用,而且解决方案可能相当复杂,我决定尝试另一种方法,这可能会简单一些。

这次,在代码绘制任何六边形之前,它必须确定预定义圆中可以适合多少行和列,并基于此结果开始绘制所有六边形。

到目前为止,它有点有效,但就像我的先前的方法一样,有时六边形会重叠,或者在圆的下部留下一个大间隙。

另一个问题是,如何将这些六边形格式化成网格?

请注意,画布下面有一个小滑块,可以增加/减小圆的半径并重新绘制六边形。

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.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare.com/ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis.com/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>


我有点困惑。六边形和圆形的尺寸都给出了吗?你能更明确地陈述问题吗?硬性约束条件是什么,你试图最大化什么? - curious_cat
硬性限制是圆的大小,基于此生成六边形网格。 - Alexus
它必须呈六边形网格形式,因为我在其他计算中使用了每行放置的所有六边形的数量。然后将数字存储在六边形属性中,以找出六边形之间的关系。但所有这些都不是这个问题的一部分。 - Alexus
六边形的大小怎么样?六边形越小,你就可以在其中装更多东西。六边形的大小也是固定的吗?如果我漏掉了一些显而易见的内容,请原谅。 - curious_cat
你的六边形看起来不是紧密排列的。它们之间似乎有空隙。为了得到一个蜂窝状的图案,行必须嵌套且相互锁定,没有空隙。 - curious_cat
显示剩余3条评论
3个回答

6
以下是解决以圆心为中心的正六边形结构的装箱问题。 正常意思是:
  • 所有六边形的集合在围绕圆心旋转60度时对称。
各个六边形的坐标表示从中心开始计数的六边形壳层数和顺时针序号。
随着圆的扩大,新的六边形壳不一定会被完整填满。尽管部分填充外壳的自由度可以产生改进的解决方案,但仍不是最优的。放宽规则以使旋转对称性相对于60度以外的其他角度(即120和180度)将允许更高的覆盖率。
我将研究下一版代码背后的数学(可能会找到一个定理来证明围绕圆心的旋转对称性是最优条件的必要条件)。

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 honeycomb
             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-honeycomb
     } // 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 honeycomb
         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-honeycomb
     
     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.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare.com/ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis.com/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>


到目前为止,这是最好的答案,尽管它比我预期的要复杂得多...是否可能将其简化一点?(我指的是您在上面示例中使用的for循环数量。) - Alexus
最里面的6个循环可以在一个带有6个case的switch语句中折叠,以区分计算下一个六边形的中点所需的计算。同样地,部分shell的代码可以折叠到第一层循环中。然而,当前最内部六边形和圆的中点总是重合的。放松这一点将允许得到更好的解决方案,但是代码结构可能需要进行适当调整。我今晚会看看这个问题。 - collapsar
3
干得好。可以将那些内部循环转换成函数调用:https://jsfiddle.net/7ekv24ab/ 这样可以简化一些代码。 - tiffon

0
简短回答:没有简单的方法可以解决这个问题。你有太多特殊情况。为了说明这一点,从1、2、3、4、6和7个六边形开始,画出最小的圆,使其覆盖它们,并注意圆心的位置。
如您所见,圆心移动相当大。它可能位于六边形的中间、顶点或交叉点上。
从那时起,情况只会变得更糟。
我在这个问题上找到的最接近的解决方案是this page
编辑:您可能想查看以下博客页面,以获得关于编程中六边形的非常全面的处理。

http://www.redblobgames.com/grids/hexagons/


0
花了一些时间在你的代码上来打包十六进制。它并不完美,我相信有更好的方法来做这件事。如果有帮助的话,请查看它,或者如果你能修复十六进制步出圆圈的问题[现在,计算行大小存在问题]。也许我可以在有时间的时候再次看看它,或者我们可以考虑其他的方法来解决这个问题。

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.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<link href="https://cdnjs.cloudflare.com/ajax/libs/jqueryui/1.11.4/jquery-ui.min.css" rel="stylesheet"/>
<script src="https://ajax.googleapis.com/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>


由于您的解决方案违反了包含约束,因此被投下了反对票。 - collapsar

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接