javascript - 中点円アルゴリズムを使用して、塗りつぶされた円の点を生成します

Question

Javascriptで半径10などの塗りつぶされた円の各点の座標を生成して保存する必要があります。

これを行うための最良の方法は、中点円アルゴリズムを使用することであるように思われますが、円内のすべての点を見つけるためにそれをどのように適応させるかはわかりません。座標は、オブジェクトとして配列に格納されます。

誰かが実装を手伝ってくれませんか？

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});

上記のアルゴリズムを変更して、他の（より複雑な）形状/パス/ポリゴンを処理することは困難です。より一般的なソリューションとして、HTML5CANVASを使用できます。キャンバスを作成し、2Dコンテキストですべての形状/パス/ポリゴンを黒一色で描画してから、ピクセルデータを反復処理し、アルファチャネルが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);