Trova tutte le coordinate integer in un dato raggio

Question

Dato un sistema di coordinate bidimensionale come posso trovare tutti i punti con coordinate intere in un raggio da un punto dato? Voglio i punti come coordinata x e valore coordinata y.

Trovare punti in un quadrato attorno al punto dato è semplice e si potrebbe fare così:

for(int x = -radius + point.x; x < radius + point.x; ++x) 
for(int y = -radius + point.y; y < radius + point.y; ++y) 
{ 
    points.insert(point(x, y)); 
} 

Ma come posso trovare i punti in un cerchio intorno al punto dato? Questo algoritmo è correlato alle prestazioni ma non alla precisione. Quindi non importa se un punto si chiude al raggio di quello che viene aggiunto o meno. In altre parole, non ho bisogno di precisione a virgola mobile.

Answer 1

più semplice soluzione: prendere un quadrato e filtrarlo:

Point point(100, 100); 
for(int x = -radius; x <= radius; ++x) 
for(int y = -radius; y <= radius; ++y) 
if(x*x + y*y <= radius* radius) { 
    points.insert(Point(x + point.x, y + point.y)); 
} 

Answer 2

Un modo è un ciclo esterno su x da -R a + R e un ciclo interno su y in base ai valori y del cerchio a quel valore x (da -sqrt (r^2 - x^2) a sqrt (r^2 - x^2) se il centro è a 0,0), se il centro è a X, Y - aggiungi semplicemente X o Y a tutti gli intervalli di loop nello stesso modo che hai nell'esempio

Answer 3

si può fare una piccola modifica all'algoritmo cerchio punto centrale per ottenere un cerchio pieno.

Prima generare le coordinate

data = new int[radius]; 
int f = 1 - radius, ddF_x = 1; 
int ddF_y = -2 * radius; 
int x = 0, y = radius; 
while (x < y) 
{ 
    if (f >= 0) 
    { 
     y--; 
     ddF_y += 2; f += ddF_y; 
    } 
    x++; 
    ddF_x += 2; f += ddF_x; 
    data[radius - y] = x; data[radius - x] = y; 
} 

quindi visitare tutti i punti interni:

int x0 = center.X; 
int y0 = center.Y - Radius; 
int y1 = center.Y + Radius - 1; 

for (int y = 0; y < data.Length; y++) 
{ 
    for (int x = -data[y]; x < data[y]; x++) 
    { 
     doSomething(x + x0, y + y0); 
     doSomething(x + x0, y1 - y); 
    } 
} 

Questo consente di risparmiare un po 'di lavoro di visitare i punti che non saranno nel cerchio, ma a scapito di un po 'di pre-elaborazione. Sicuramente non sarà di aiuto per le cerchie più piccole, e per quelle più grandi, beh, sinceramente non lo so. Dovresti confrontarlo.

Answer 4

Il seguente codice analizza il limite lungo un quarto di cerchio per determinare l'area interna. Non ha bisogno di calcolare la distanza per i punti esterni, né per i punti interni. (modifica: ma alla fine, vengono aggiunti tutti i punti del cerchio pieno)

In alcuni mini-Java-benchmark, per piccolo raggio (< 10), è della stessa velocità del semplice approccio con l'analisi del piazza piena Per raggio 20-40 è circa 2 volte più veloce e raggiunge un aumento di velocità di circa 4 volte per raggio> 50. Per un raggio molto più grande (> 200) la velocità diminuisce ancora, poiché per qualsiasi approccio è necessario il tempo dominante per creare e aggiungere i> 100k punti - indipendentemente da come sono determinati.

// add the full length vertical center line once 
for (int y = -radius + point.y; y <= radius + point.y; ++y) 
    points.insert(Point(point.x, y)); 

int sqRadius = radius * radius; 

// add the shorter vertical lines to the left and to the right 
int h = radius; 
for (int dx = 1; dx <= radius; ++dx) { 
    // decrease h 
    while (dx*dx + h*h > sqRadius && h > 0) 
     h--; 

    for (int y = -h + point.y; y <= h + point.y; ++y) { 
     points.insert(Point(point.x + dx, y)); 
     points.insert(Point(point.x - dx, y)); 
    } 
}