주어진 반지름에서 모든 정수 좌표 찾기

Question

주어진 2 차원 좌표계 주어진 반지름에서 정수 좌표를 갖는 모든 점을 어떻게 찾을 수 있습니까? 포인트를 x 좌표 및 y 좌표 값으로 지정합니다.

주어진 점을 중심 사각형에 포인트를 찾기가 쉽고, 그렇게 할 수 있습니다 :

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

하지만 어떻게 주어진 점을 중심 원의 포인트를 찾을 수 있습니까? 이 알고리즘은 성능과 관련이 있지만 정확도와 관련이 없습니다. 따라서 점이 반경에 가까워지면 1이 더해 지든 상관없이 상관 없습니다. 즉, 부동 소수점 정확도가 필요하지 않습니다.

Answer 1

간단한 솔루션 : 사각형을하고 필터링 :

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

편도는 -R에서 + R까지의 x에 대한 외부 루프와 해당 x 값에서의 원의 y 값에 따라 y에 대한 내부 루프입니다 (-sqrt (r^2 - x^2)부터 중심이 0,0에있는 경우 sqrt (r^2 - x^2), 중심이 X, Y에있는 경우 - 예제에서와 같은 방식으로 모든 루프 범위에 X 또는 Y를 간단히 추가하십시오.

Answer 3

당신은 채워진 원을 얻기 위해 중간 원 알고리즘에 작은 수정을 할 수 있습니다.

먼저 좌표를 생성합니다

다음

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

모든 내부 점을 방문하십시오 원되지 않습니다 점을 방문 몇 가지 작업을 저장하지만의 비용

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

약간의 전처리. 더 작은 원에 대해서는 도움이되지 않을 것이며, 더 큰 원에 대해서는 도움이되지 않을 것입니다. 벤치마킹해야합니다.

Answer 4

다음 코드는 내부 영역을 결정하기 위해 1/4 원을 따라 경계를 파싱합니다. 바깥 쪽 점이나 안쪽 점의 거리를 계산할 필요가 없습니다. (편집 :하지만 마지막으로 채워진 원의 모든 포인트가 추가됩니다) 작은 반경 (< 10)에 대한 몇 가지 미니 자바 벤치 마크에서

은, 그것은 구문 분석과 간단한 방법으로 동일한 속도이다 전체 사각형. 반경 20-40 인 경우 약 2 배 빨라지고 반경이 50보다 큰 경우 약 4 배의 속도 향상을 얻습니다. 반경이 훨씬 큰 반경 (> 200)의 경우 어떤 방법 으로든 지배 시간이 필요하므로 속도가 다시 감소합니다 100k 점을 생성하고 추가하는 방법은 결정 방법에 관계없이

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