Belirli bir yarıçaptaki tüm tamsayı koordinatlarını bulma

Question

İki boyutlu bir koordinat sistemi verildiği zaman, belirli bir noktadan bir yarıçaptaki tüm noktaları tamsayı koordinatlarıyla nasıl bulabilirim? Noktaları x koordinatı ve y koordinatı değeri olarak istiyorum.

verilen nokta etrafında bir meydanda noktaları bulmak kolaydır ve böyle yapılabilir:

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

Ama nasıl belirli nokta etrafında bir daire içinde noktaları bulabilirim? Bu algoritma performans ile ilgili, ancak doğrulukla ilgili değil. Yani, bir nokta eklendiğinde veya eklenmediğinde yarıçapa kadar bir nokta kapanması önemli değil. Başka bir deyişle, kayan nokta doğruluğuna ihtiyacım yok.

Answer 1

En basit çözüm: bir kare çekmek ve bunu filtre:

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

Tek yön, x üzerinde -R ile + R arasındaki bir dış döngü ve y üzerindeki y iç değerlerine göre y üzerindeki bir iç döngüdür (-sqrt (r^2 - x^2) konumundan sqtr (r^2 - x^2) merkez ise 0,0), eğer merkez X, Y ise - basitçe X veya Y'yi tüm döngü aralıklarına, örneğinizde yaptığınız gibi aynı şekilde ekleyiniz

Answer 3

bir dolu daire almak için orta nokta çember algoritması küçük bir değişiklik yapabilir.

İlk koordinatlarını oluşturur:

Sonra

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

tüm iç noktalarını ziyaret: daire içinde olmayacak noktaları ziyaret bazı işler kaydeder, ancak pahasına

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

biraz ön işlem. Bu kesinlikle daha küçük çevrelere ve daha büyükler için yardımcı olmayacaktır, dürüstçe bilmiyorum. Ölçmek zorundasın.

Answer 4

Aşağıdaki kod, iç alanı belirlemek için sınırı çeyrek daire boyunca ayrıştırır. Dış noktaların mesafesini ve iç noktaları hesaplamaya gerek yoktur. (düzenlemek: ancak son olarak, dolu daire tüm noktalar eklenir) küçük bir yarıçap (< 10) için bir mini Java testlerde ise

, bu ayrıştırma basit bir yaklaşım aynı hızda ait tam kare. Yarıçap 20-40 için yaklaşık 2 kat daha hızlıdır ve yarıçap> 50 için yaklaşık 4 kat hızlandırır. Daha büyük bir yarıçap için (> 200) hızlanma tekrar azalır, çünkü herhangi bir yaklaşım için baskın zamana ihtiyaç duyulur. nasıl belirlendiklerine bakmaksızın> 100k puan oluşturmak ve eklemek için.

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