Disegnare cerchi concentrici senza spazi vuoti

L'algoritmo del punto medio ti fornisce l'insieme di punti che si trovano "esattamente" a una certa distanza dal centro.

Quello che vorresti fare è usare un altro algoritmo per testare se la distanza è inferiore a (e non uguale a) del raggio.

L'algoritmo della forza bruta dovrebbe essere quello di controllare ogni cella della griglia, ma se vuoi davvero essere efficiente, puoi eseguire il test di prossimità (simile all'algoritmo del punto medio) ed eseguire una sorta di scansione lineare a partire dall'alto ( x_start = x_radius; y_start = y_radius + raggio).

Un esempio in pseudo-codice:

foreach i in i_range:
    foreach j in j_range:
        y = i - ry
        x = j - rx
        if (x^2 + y^2)^0.5 - 0:
           paint_cell(i,j)

Non esattamente quello che hai chiesto, ma penso che solo una scansione verticale sia più semplice:

line((x_center-r,y_center)-(x_center+r,y_center))
for(y=y_center+1;y_center+r;y++) {
    w=sqrt((r+y)(r-y))
    x_min=x_center-w
    x_max=x_center+w
    y_mirror=2*y_center-y
    line((x_min,y)-(x_max,y))
    line((x_min,y_mirror)-(x_max,y_mirror))
}

Quindi se un cerchio nel tuo schermo ha un diametro di 101 pixel, richiederà il calcolo di 50 radici quadrate e il disegno di 101 linee orizzontali (ci sono 2 linee per ogni lunghezza).

It is important that the circle is filled using concentric passes

Non puoi disegnare nulla di "perfetto" usando "passaggi concentrici" sul sistema di coordinate cartesiane, che è in definitiva ciò che devi fare. I pixel non sono allineati con i cerchi con passaggio N. Tuttavia, puoi fare una buona approssimazione. E il metodo che usi dovrebbe dipendere dal tuo obiettivo finale.

... because i also update some metadata in the cells as I get them in groups (each one corresponding to a circumference).

Questo suona come se avessi bisogno di operare punto per punto su tutti i punti in cui potrebbe essere parte del cerchio, determinando la "relazione con il centro" di ognuno mentre vai .

Quindi, quello che finirai con è qualcosa di molto simile alla soluzione di heltonbiker , ma che dipinge e / o imposta metadati per ogni punto al suo passaggio. Potresti volere due funzioni:

// a simple distance function
var distanceFrom = function(x, y, cx, cy) {
    return Math.sqrt(
        Math.pow(cx - x, 2) + Math.pow(cy - y, 2)
    );
};

// something to determine the "value" of a pixel, based on the circle center
var getValue = function(x, y) {

    // in your real application, these three vars will be parameters ...
    var radius = 7;
    var center_x = 7;
    var center_y = 7;

    var d = distanceFrom(x, y, center_x, center_y);
    if (d <= radius) {
        return d / radius;
    } else {
        return 1; // white/off
    }
}; // getValue()

E un semplice loop ... da qualche parte in un metodo con nome appropriato:

// something that loops through all the relevant pixels.
// ... this does NOT need to look at every pixel. it only
// needs to look at the pixels within the box that bounds
// your circle.
for (var y = 0; y < 15; y++) {
    for (var x = 0; x < 15; x++) {
        paint(x, y, getValue(x, y));
    }
}

Vedi questo violino , ingrandito di 32 per mostrare i "pixel".

Pensochepuoivederedalrisultatocheicerchiconcentriciforzanolecorrispondenzetrapixelecerchichesonosemplicementebrutti.L'approcciopixelperpixelnonsologarantiscecheognipixelsiavalutatoedisegnato,macheognipixelpossaessereassociatoalcerchiooalraggiopiùrilevanti.

Sestaicercandounoschemanonagradiente,devisoloaggiornarelafunzionevalore:

//alternating/concentric-ishcircles....vargetValue=function(x,y){varradius=7;varcenter_x=7;varcenter_y=7;vard=distanceFrom(x,y,center_x,center_y);if(d<=radius){returnMath.floor(d)%2===0?0:0.5;}else{return1;//white/off}};//getValue()

Visibile come violino qui . Ed ecco cosa produce:

E,naturalmente,sestaicercandodicolorareunsingolo"cerchio" che sia compatibile con le tue altre cerchie, potresti iniziare con l'approccio non ottimizzato della scansione dell'intera area del cerchio e disegnare solo i pixel di cui floored o arrotondato la distanza dal centro corrisponde a un raggio intero (o pavimentato / arrotondato).

var getValue = function(x, y) {
    var radius = 7;
    var center_x = 7;
    var center_y = 7;

    // the radius of the "circle" we're drawing (should be parametized)
    var draw_only = 5;

    var d = distanceFrom(x, y, center_x, center_y);

    // the new condition is tacked on here:
    if (d <= radius && Math.floor(d) === draw_only) {
        return Math.floor(d) % 2 === 0 ? 0 : 0.5;
    } else {
        return 1; // white/off
    }
}; // getValue()

Non è efficiente , ma gli anelli che disegna dovrebbero essere allineati con quelli dell'esempio con i colori alternati:

Vedi il violino .

Se stai cercando di fare quello che ho fatto nell'ultimo esempio, disegnando solo un singolo anello alla volta, può potenzialmente essere ottimizzato (per cerchi di grandi dimensioni) camminando attorno al cerchio e processando blocchi di pixel che sono "probabilmente" sta per essere colorato. Qualcosa simile a questo codice totalmente non testato ...

// radius of the circle we want to draw
var radius = 5;
for (var deg = 0; deg < 360; deg++) {
  var radians = 2 * Math.PI * deg/360;

  var focus_x = Math.floor(radius * Math.cos(radians));
  var focus_y = Math.floor(radius * Math.sin(radians));

  // i'm not sure how much "fuzz" you need ... play with it:
  var x1 = focus_x - 2;
  var x2 = focus_x + 2;
  var y1 = focus_y - 2;
  var y2 = focus_y + 2;

  for (var y = y1; y < y2; y++) {
    for (var x = x1; x < x2; x++) {
      paint(x, y, getValue(x, y), radius); // again, radius needs to be parametized
    }
  }
}

Dichiarazione di non responsabilità: Né la presente risposta né il violino associato hanno lo scopo di dimostrare l'uso corretto o corretto di canvas HTML5 .

L'approccio più semplice a cui riesco a pensare è: iniziare con un cerchio completamente riempito in rosa e (utilizzare la risposta di @ Mandrill per esempio) e disegnare solo i cerchi bianchi in seguito sul cerchio rosa, usando l'algoritmo del punto medio esistente. Ciò non lascerà punti neri, tutte le macchie nere avranno il colore con cui hai iniziato.

Tuttavia, se non vuoi disegnare qualcosa due volte, ecco un'idea su come affrontarlo:

• disegna le "circonferenze" nell'ordine di raggio crescente

• modifica l'algoritmo del punto medio nel seguente modo: ogni volta che imposti una cella nella metà sinistra della tua cerchia a un colore specifico, verifica se nella stessa riga ci sono dei punti neri a destra della cella. Se questo è il caso, riempili anche con il colore corrente, fino a raggiungere un punto non nero o la colonna centrale. Fai lo stesso se stai colorando una cella nella metà destra, ma per quelle celle riempi i punti neri a sinistra nella riga corrente.

Ad esempio:

Ilvantaggiodiquestoapproccioècheituoi"cerchi intermedi" soddisfano sempre le tue esigenze, non solo il risultato finale. E i "punti neri" non vengono riempiti tutti con lo stesso "colore preferito", ma si ottiene un rapporto più uniformemente distribuito tra il bianco e il rosa. Il tempo di esecuzione è ancora proporzionale al numero di celle colorate.

Questo può essere facilmente modificato per creare un algoritmo che produce le coordinate di "circonferenza" di un raggio specifico in qualsiasi ordine tu voglia. Crea una funzione

  IEnumerable<Point> MidpointCircle(int radius,Point center){...}

Quindi usalo in questo modo (struttura approssimativa in C #, attenzione, codice aereo):

  IEnumerable<Point> Circumference(int radius,Point center)
  {
       if(radius==0)
          yield break;
       var points = MidpointCircle(radius,center);
       var innerPoints =new Hashset(MidpointCircle(radius-1,center));
       foreach(var p in points)
       {
            yield return p;
            if(p.X<center.X)
            {
               Point q = new Point(p.X+1,p.Y);
               while(q.X<center.X && !innerPoints.Contain(q))
               {
                  yield return q;
                  q = new Point(p.X+1,p.Y);
               }
            }
            else
            {
               // similar code for points right from the center
            }
       }
  }

Questo dovrebbe darti il risultato che stai cercando.

In ritardo alla festa, ma ho trovato l'algoritmo del cerchio "4-connesso" di Tony Barrera in Will Perone's site , sembra riempire le lacune ed essere il più veloce allo stesso tempo, codice Javascript qui sotto o in fiddle . Questa risposta può essere applicata anche a Algoritmo Cerchio con disegno spessori .

var canvas = document.querySelector('canvas')
var ctx = canvas.getContext('2d');
ctx.fillStyle = 'blue';

var DrawPixel = function (x, y) {
    ctx.fillRect(x, y, 1, 1);
}

function Barrera4(x0, y0, radius) {
    var x = 0;
    var y = radius;
    var d = -(radius >>> 1);

    while(x <= y) {
        DrawPixel(x + x0, y + y0);
        DrawPixel(y + x0, x + y0);
        DrawPixel(-x + x0, y + y0);
        DrawPixel(-y + x0, x + y0);
        DrawPixel(-x + x0, -y + y0);
        DrawPixel(-y + x0, -x + y0);
        DrawPixel(x + x0, -y + y0);
        DrawPixel(y + x0, -x + y0);

        if(d <= 0) {
            x++;
            d += x;
        } else {
            y--;
            d -= y;
        }
    }
}

for(var r = 100; 0 < r; r--) {
    ctx.fillStyle = (r%8 < 4) ? 'pink' : 'white';
    //DrawCirle(120, 120, r);
    Barrera4(120, 120, r);
    //Barrera8(120, 120, r);
}

canvas {
  background-color: black;
}

<canvas width=300 height=300></canvas>

Se sei interessato a disegnare cerchi concentrici e non ti preoccupare di eseguire uno sward sweep del AABB quindi il test da eseguire su ciascun pixel è:

distanceFromCenter <= radius && distanceFromCenter > (radius - someThreshold)

O come esempio più concreto:

void drawCircle(Point center, int radius, int thickness, Color color) {
    for (var x = center.x - radius; x < center.x + radius; x++) {
        for (var y = center.y - radius; y < center.y + radius; y++) {
            float distance = distanceFrom(x, y, center.x, center.y);
            if (distance <= radius && distance > radius - thickness) {
                drawPixel(x, y, color);
            }
        }
    }
}

Se queste cerchie devono essere aggiornate di frequente e le prestazioni diventano un problema, i pixel pertinenti possono essere archiviati in un array di punti o in un maschera .