将任意大小的圆圈放在另一个 shape/parallelogram

Question

我想要一个算法将多个任意（具有最小、最大）半径的圆圈放置在另一个形状内，主要是在矩形内，不重叠且（看似）随机位置。

Answer 1

我不确定这是否满足您的需求，但这是一种解决方法，本质上是强制执行并假设您有一个多边形（没有曲线）：

找到多边形的边界矩形。（我认为你只需要遍历所有点，并保持最大和最小 x 和 y 值。）
生成一个具有随机半径和位置的圆。
检查圆心是否在多边形内部 - 参见此处：https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
检查圆是否与任何直线相交 - 参见此处：https://math.stackexchange.com/questions/275529/check-if-line-intersects-with-circles-perimeter
使用勾股定理检查该圆是否与任何其他圆相交。（归功于 tevemadar）
重复第 2 步到第 5 步，直到你有足够的圈子或者它不断失败（可能意味着没有更多 space）。

Answer 2

你有两个约束：

圆应该留在矩形内
圆圈不应重叠

让圈子彼此远离

这个不依赖于矩形的细节：

如果圆的中点彼此之间的距离比它们的半径之和更近，则两个圆相交。否则它们不会（在相等的情况下它们可能会接触）。您可以使用毕达哥拉斯定理来计算距离。
如果半径是 r1 和 r2，中点是 x1,y1 和 x2,y2，检查看起来像

if(Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) >= r1+r2)
  okay
else
  not okay

其中 Math.sqrt() 计算某项的平方根（这里计算二次方是通过简单的乘法完成的）。

将圆保留在矩形内

这里半径又起了作用：如果圆的中点比它的半径更靠近任何边界，则它与该边界相交。

最简单的情况是矩形轴对齐，并且从 0,0 开始。在这种情况下，很明显半径为 r 和中点为 x,y 的圆不能有 x<r 或 y<r，因为在那种情况下圆将有一部分负 x 或 y 平面。其他限制是矩形的 width 和 height，x+r>width（或者更确切地说 x>width-r）将导致圆的某些部分 "beyond" 的限制矩形。
这可以很容易地扩展到轴对齐的矩形运行从 x1,y1 到 x2,y2:

if( x>=x1+r && x<=x2-r && y>=y1+r && y<=y2-r )
  okay
else
  not okay

但实际上您不会使用此检查，而是生成矩形内的圆：

选择一个半径r（介于合适的最小值和最大值之间）
从带角 x1+r, y1+r 和 x2-r, y2-r

所以这只是在一些限制之间生成随机数的经典任务。如果你碰巧有一个随机数生成器函数 random() 生成 0 和 1 之间的分数，并且限制 min 和 max，min+(max-min)*random() 是你可以使用的表达式。

放在一起 JavaScript:

function stuff(){
  let ctx=cnv.getContext("2d");
  ctx.clearRect(0,0,cnv.width,cnv.height);
  lineStyle="black";
  ctx.strokeRect(0,0,cnv.width,cnv.height);
  
  let x1=ix1.valueAsNumber,y1=iy1.valueAsNumber;
  let x2=ix2.valueAsNumber,y2=iy2.valueAsNumber;
  let cnt=icnt.valueAsNumber;
  let rmin=irmin.valueAsNumber,rmax=irmax.valueAsNumber;
  
  ctx.fillStyle="lightgray";
  ctx.fillRect(x1,y1,x2-x1,y2-y1);

  ctx.fillStyle="blue";
  let giveup=Date.now()+3000;
  let circles=[];
  while(circles.length<cnt && Date.now()<giveup){
    let r=rmin+(rmax-rmin)*Math.random();
    let x=x1+r+(x2-r-x1-r)*Math.random();
    let y=y1+r+(y2-r-y1-r)*Math.random();
    let okay=true;
    for(let c of circles)
      if(Math.sqrt((x-c.x)*(x-c.x)+(y-c.y)*(y-c.y))<r+c.r){
        okay=false;
        break;
      }
    if(okay){
      circles.push({x:x,y:y,r:r});
      ctx.beginPath();
      ctx.arc(x,y,r,0,Math.PI*2);
      ctx.fill();
      ctx.stroke();
    }
  }  
  ctx.strokeRect(x1,y1,x2-x1,y2-y1);
}
stuff();

input{width:50px}

x1:<input id="ix1" type="number" min="0" max="600" value="50" onchange="stuff()">
y1:<input id="iy1" type="number" min="0" max="150" value="10" onchange="stuff()">
x2:<input id="ix2" type="number" min="0" max="600" value="400" onchange="stuff()">
y2:<input id="iy2" type="number" min="0" max="150" value="140" onchange="stuff()">
#:<input id="icnt" type="number" min="0" max="50" value="10" onchange="stuff()">
rmin:<input id="irmin" type="number" min="1" max="50" value="20" onchange="stuff()">
rmax:<input id="irmax" type="number" min="1" max="50" value="50" onchange="stuff()">

<canvas id="cnv" width="600" height="150"></canvas>

由于很容易选择根本无法求解的参数，或者以不幸的方式放置前几个圆圈后可能无法求解，因此代码有时间限制，3 秒后放弃工作。

将任意大小的圆圈放在另一个 shape/parallelogram

Place arbitrary sized circles in another shape/parallelogram

algorithm

math

geometry

circle-pack