javascript - 使用中点圆算法生成实心圆的点

Question

我需要生成并存储一个实心圆的每个点的坐标，比如 Javascript 中的半径 10。

似乎最好的方法是使用midpoint circle algorithm，但我不确定如何调整它以找到圆中的每个点。坐标将作为对象存储在数组中。

有人可以帮我实施吗？

Answer 1

就我个人而言，我认为在这种情况下测试边界框中的所有像素到中心的距离可能会更快。如果<= r那么该点在圆圈中，应该被推到您的阵列上。

function distance(p1, p2)
{
   dx = p2.x - p1.x; dx *= dx;
   dy = p2.y - p1.y; dy *= dy;
   return Math.sqrt( dx + dy );
}

function getPoints(x, y, r)
{
    var ret = [];
    for (var j=x-r; j<=x+r; j++)
       for (var k=y-r; k<=y+r; k++)
           if (distance({x:j,y:k},{x:x,y:y}) <= r) ret.push({x:j,y:k});
    return ret;
}

Answer 2

您遍历所有可能的点，然后对它们运行 Point-In-Circle 检查。

像下面这样就足够了......

var result = [];
var d = 10;
var r = d / 2;
var rr = r*r;
for(var y=0; y<d; y++)
 for(var x=0; x<d; x++)
  if((x-r)*(x-r)+(y-r)*(y-r) < rr)
   result.push({"x": x, "y": y});

修改上述算法以处理其他（更复杂的）形状/路径/多边形将很困难。对于更通用的解决方案，您可以使用 HTML5 CANVAS。您创建一个画布，获取 2d 上下文以纯黑色绘制所有形状/路径/多边形，然后遍历像素数据并找到 alpha 通道大于 0（或 127，如果您想减轻反抗误报）的像素-混叠）。

var r = 5; // radius of bounding circle
//
// set up a canvas element
//
var canvas = document.createElement("canvas");
canvas.width = r*2;
canvas.height = r*2;
canvas.style.width = (r*2) + "px";
canvas.style.height = (r*2) + "px";
var ctx = canvas.getContext("2d");
ctx.fillStyle = "#000";
//
// draw your shapes/paths/polys here
//
ctx.beginPath();
ctx.arc(r, r, r, 0, Math.PI*2, true); 
ctx.closePath();
ctx.fill();
//
// process the pixel data
//
var imageData = ctx.getImageData(0,0,(r*2),(r*2));
var data = imageData.data;
var result = [];
var str = "";
for(var y = 0; y<(r*2); y++) {
    for(var x = 0; x<(r*2); x++) {
        var pixelOffset = (y * (r*2) + x) * 4;
        if(data[pixelOffset+3] > 127) {
            result.push({x: x, y: y});
            str += "(" + x + ", " + y + ") "; // debug
        }
    }
}
//
// debug/test output
//
document.body.innerHTML += str;
document.body.appendChild(canvas);
alert(result.length);