Znajdź wszystkie współrzędne całkowite w danym promieniu

Question

Biorąc pod uwagę dwuwymiarowy układ współrzędnych, w jaki sposób mogę znaleźć wszystkie punkty o współrzędnych całkowitych w promieniu od danego punktu? Chcę, aby punkty były współrzędnymi xi współrzędnymi y.

Znalezienie punktów w kwadracie wokół danego punktu jest łatwe i można zrobić tak:

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

Ale jak znajdę punktów w kręgu wokół danego punktu? Algorytm ten związany jest z wydajnością, ale nie z dokładnością. Nie ma więc znaczenia, czy punkt zamyka się do promienia niż 1, czy nie. Innymi słowy, nie potrzebuję dokładności zmiennoprzecinkowej.

Answer 1

rozwiązanie Najprostszy: wziąć kwadrat i przesączyć go:

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

Jednym ze sposobów jest zewnętrzna pętla na x od -R do + R i wewnętrzna pętla na y zgodnie z wartościami y okręgu przy tej wartości x (od -sqrt (r^2 - x^2) do sqrt (r^2 - x^2), jeśli środek jest na poziomie 0,0), jeśli środek jest w X, Y - po prostu dodaj X lub Y do wszystkich zakresów pętli w taki sam sposób, jak w twoim przykładzie

Answer 3

można zrobić małą modyfikację algorytmu kole środkowym, aby uzyskać pełen okrąg.

najpierw wygenerować współrzędne:

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

Następnie odwiedzić wszystkie wewnętrzne punkty:

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

To oszczędza trochę pracy odwiedzając punkty, które nie będą w kręgu, ale kosztem trochę wstępnego przetwarzania. Z pewnością nie pomoże mniejszym kręgom, a dla większych, no, szczerze mówiąc, nie wiem. Musiałbyś to porównać.

Answer 4

Następujący kod po prostu analizuje granicę wzdłuż kwadratu, aby określić obszar wewnętrzny. Nie trzeba obliczać odległości dla zewnętrznych punktów ani dla wewnętrznych punktów. (edit: ale w końcu, wszystkie punkty wypełnione koła są dodawane)

W niektórych mini-java-benchmarków, na małym promieniu (< 10), to jest z tą samą prędkością jak proste podejście z parsowania pełny kwadrat. Dla promienia 20-40 jest to około 2 razy szybsze i przyspiesza około 4 razy dla promienia> 50. Dla nieco większego promienia (> 200) przyspieszenie zmniejsza się ponownie, ponieważ dla każdego podejścia potrzebny jest czas dominujący do tworzenia i dodawania punktów> 100 tys. - niezależnie od tego, jak są określane.

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