채워진 원을 그리는 빠른 알고리즘?
빠른 원 그리기는 브레센햄의 원 알고리즘을 사용하고 있습니다.다만, (사용자의 요구에 따라) 채워진 동그라미도 그립니다.
빠르고 효율적인 방법이 있을까요?브레센햄과 같은 방식으로요?
제가 사용하는 언어는 C입니다.
좋은 생각이야!수천 개의 원을 그려야 하는 프로젝트에 종사하고 있기 때문에, 여기서의 모든 제안을 평가했습니다(반경의 제곱을 미리 계산해 몇 개 개선했습니다).
http://quick-bench.com/mwTOodNOI81k1ddaTCGH_Cmn_Ag
Rev 베리에이션은 x와 y만 교환됩니다.이는 y축을 따라 연속적으로 액세스하는 것이 그리드/캔버스 구조가 작동하는 방식으로 더 빠르기 때문입니다.
확실한 승자는 Daniel Earwicker의 메서드(DrawCircleBruteforcePrec)입니다.이 메서드는 불필요한 반지름 체크를 피하기 위해 Y 값을 사전에 계산합니다.약간 의외로 sqrt 콜에 의한 추가 계산이 무효가 됩니다.
일부 코멘트는 단일 루프에서 작동하는 kmillen의 바리안트(DrawCircleSingleLoop)는 매우 빨라야 한다고 제안하지만, 여기서는 가장 느립니다.나는 그것이 모든 분열 때문이라고 생각한다.하지만 아마도 제가 그 코드의 글로벌 변수에 잘못 적응한 것 같습니다.누가 한번 봐주면 좋을 것 같아요.
편집: 대학 시절 이후 처음으로 어셈블러 코드를 찾아본 결과, 서클의 기원을 최종적으로 추가한 것이 범인임을 알게 되었습니다.그것들을 사전에 계산해, 벤치에 의하면, 가장 빠른 방법을 3.7-3.9배로 개선했습니다.http://quick-bench.com/7ZYitwJIUgF_OkDUgnyMJY4lGlA 대단합니다.
제 암호는 다음과 같습니다.
for (int x = -radius; x < radius ; x++)
{
int hh = (int)std::sqrt(radius_sqr - x * x);
int rx = center_x + x;
int ph = center_y + hh;
for (int y = center_y-hh; y < ph; y++)
canvas[rx][y] = 1;
}
그냥 무력을 사용하세요.이 방법은 너무 많은 픽셀을 반복하지만 정수 곱셈과 덧셈만 사용합니다.브레센햄의 복잡성과 sqrt의 병목 가능성을 완전히 피할 수 있습니다.
for(int y=-radius; y<=radius; y++)
for(int x=-radius; x<=radius; x++)
if(x*x+y*y <= radius*radius)
setpixel(origin.x+x, origin.y+y);
브레센햄(또한 '미드포인트') 서클 알고리즘에 있는 위키피디아 페이지를 읽으면, 가장 쉽게 할 수 있는 것은 동작을 수정하는 것 같습니다.
setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);
그 대신 할 때마다 비슷합니다.
lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);
각 쌍)에 , 「」(「」)를 사용합니다.y브레센햄이 플롯을 만들었으면 하는 경우, 대신 선으로 연결합니다.
여기 C#의 대략적인 가이드가 있습니다(C에 대한 올바른 아이디어를 얻는 것은 그리 어렵지 않습니다). 이것은 반복적인 제곱근을 제거하기 위해 브레센햄을 사용하지 않는 "원시" 형식입니다.
Bitmap bmp = new Bitmap(200, 200);
int r = 50; // radius
int ox = 100, oy = 100; // origin
for (int x = -r; x < r ; x++)
{
int height = (int)Math.Sqrt(r * r - x * x);
for (int y = -height; y < height; y++)
bmp.SetPixel(x + ox, y + oy, Color.Red);
}
bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");
팜3D의 무차별적인 알고리즘이 좋은 출발점이라고 생각했어요이 방법에서는 동일한 전제를 사용하지만 대부분의 픽셀 검사를 건너뛰는 몇 가지 방법이 있습니다.
먼저, 코드는 다음과 같습니다.
int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
for (int x = largestX; x >= 0; --x) {
if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
largestX = x;
break; // go to next y coordinate
}
}
}
그 다음 설명입니다.
첫 번째 주의사항은 주어진 수평선의 원 안에 있는 최소 x 좌표를 찾으면 최대 x 좌표를 즉시 알 수 있다는 것입니다.이것은 원의 대칭성 때문이다.최소 x 좌표가 원의 경계 상자 왼쪽보다 10픽셀 앞일 경우 최대 x는 원의 경계 상자 오른쪽보다 10픽셀 뒤입니다.
높은 x 값에서 낮은 x 값으로 반복하는 이유는 최소 x 값이 더 적은 반복으로 발견되기 때문입니다.이는 이 이미지에서 볼 수 있듯이 원이 바깥쪽으로 구부러져 있기 때문에 최소 x 값이 대부분의 선에서 원의 중심 x 좌표보다 경계 상자의 왼쪽에 가깝기 때문입니다.다음으로 주목해야 할 점은 원도 수직으로 대칭이기 때문에 각 선에서 찾을 때마다 두 번째 선을 자유롭게 그릴 수 있다는 것입니다.원의 위쪽 절반에서 선을 찾으면 아래쪽 절반에서 반지름-y 좌표의 선을 얻을 수 있습니다.따라서 선이 발견되면 2개를 그릴 수 있으며 y 값의 위쪽 절반만 반복하면 됩니다.
마지막으로 주목해야 할 것은 원의 중심에 있는 y 값에서 시작하여 y의 위쪽을 향해 이동하면 다음 각 선의 최소 x 값은 마지막 줄보다 원의 중심 x 좌표에 더 가까워야 한다는 것입니다.이것은 또한 원을 위로 올라갈수록 원이 중심 x 값을 향해 더 가까이 구부러지기 때문입니다.여기 그것이 어떻게 적용되는지에 대한 시각 자료입니다.
요약:
- 선의 최소 x좌표를 찾으면 최대 x좌표를 무료로 얻을 수 있습니다.
- 원의 위쪽 절반에 선을 그릴 때마다 원의 아래쪽 절반에 선을 무료로 제공합니다.
- 모든 최소 x 좌표는 중심 y 좌표에서 상단까지 반복할 때 각 선의 이전 x 좌표보다 원의 중심에 더 가까워야 합니다.
또한 다음 값을 저장할 수 있습니다.(radius * radius), 및 기타(y * y)여러 번 계산하는 대신 말이죠.
다음을 사용할 수 있습니다.
void DrawFilledCircle(int x0, int y0, int radius)
{
int x = radius;
int y = 0;
int xChange = 1 - (radius << 1);
int yChange = 0;
int radiusError = 0;
while (x >= y)
{
for (int i = x0 - x; i <= x0 + x; i++)
{
SetPixel(i, y0 + y);
SetPixel(i, y0 - y);
}
for (int i = x0 - y; i <= x0 + y; i++)
{
SetPixel(i, y0 + x);
SetPixel(i, y0 - x);
}
y++;
radiusError += yChange;
yChange += 2;
if (((radiusError << 1) + xChange) > 0)
{
x--;
radiusError += xChange;
xChange += 2;
}
}
}
나는 팜3가 좋다D의 대답.폭력적이기 때문에, 이것은 놀라울 정도로 빠른 해결책입니다.속도를 늦추는 제곱근이나 삼각함수는 없습니다.그것의 단점은 중첩 루프입니다.
이것을 1개의 루프로 변환하면, 이 기능은 거의 2배의 속도로 동작합니다.
int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;
for (int i = 0; i < area; i++)
{
int tx = (i % rr) - r;
int ty = (i / rr) - r;
if (tx * tx + ty * ty <= r2)
SetPixel(x + tx, y + ty, c);
}
이 단일 루프 솔루션은 선긋기 솔루션의 효율성에 필적합니다.
int r2 = r * r;
for (int cy = -r; cy <= r; cy++)
{
int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
int cyy = cy + y;
lineDDA(x - cx, cyy, x + cx, cyy, c);
}
방법은 다음과 같습니다.
2비트 정밀도의 고정 소수점 값을 사용하고 있습니다(반점 및 반점 제곱 값을 관리해야 함).
앞의 답변에서도 언급했듯이, 저도 제곱근 대신 제곱근을 사용하고 있습니다.
첫째, 원의 1/8 부분에서 원의 테두리 한계를 감지합니다.이 점들의 계율을 사용해서 원의 4개의 "보더"를 그립니다.그리고 원 안에 정사각형을 그리고 있어요.
중간점 원 알고리즘과 달리 이 알고리즘은 짝수 직경(및 약간의 변경만 있으면 실수 직경)에서 작동합니다.
제 설명이 명확하지 않았다면 용서해주세요.프랑스어라서요;)
void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)
{
const int FULL = (1 << 2);
const int HALF = (FULL >> 1);
int size = (circleDiameter << 2);// fixed point value for size
int ray = (size >> 1);
int dY2;
int ray2 = ray * ray;
int posmin,posmax;
int Y,X;
int x = ((circleDiameter&1)==1) ? ray : ray - HALF;
int y = HALF;
circlePosX -= (circleDiameter>>1);
circlePosY -= (circleDiameter>>1);
for (;; y+=FULL)
{
dY2 = (ray - y) * (ray - y);
for (;; x-=FULL)
{
if (dY2 + (ray - x) * (ray - x) <= ray2) continue;
if (x < y)
{
Y = (y >> 2);
posmin = Y;
posmax = circleDiameter - Y;
// Draw inside square and leave
while (Y < posmax)
{
for (X = posmin; X < posmax; X++)
setPixel(circlePosX+X, circlePosY+Y);
Y++;
}
// Just for a better understanding, the while loop does the same thing as:
// DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);
return;
}
// Draw the 4 borders
X = (x >> 2) + 1;
Y = y >> 2;
posmax = circleDiameter - X;
int mirrorY = circleDiameter - Y - 1;
while (X < posmax)
{
setPixel(circlePosX+X, circlePosY+Y);
setPixel(circlePosX+X, circlePosY+mirrorY);
setPixel(circlePosX+Y, circlePosY+X);
setPixel(circlePosX+mirrorY, circlePosY+X);
X++;
}
// Just for a better understanding, the while loop does the same thing as:
// int lineSize = circleDiameter - X*2;
// Upper border:
// DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);
// Lower border:
// DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);
// Left border:
// DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);
// Right border:
// DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);
break;
}
}
}
void DrawSquare(int x, int y, int size)
{
for( int i=0 ; i<size ; i++ )
DrawHorizontalLine(x, y+i, size);
}
void DrawHorizontalLine(int x, int y, int width)
{
for(int i=0 ; i<width ; i++ )
SetPixel(x+i, y);
}
void DrawVerticalLine(int x, int y, int height)
{
for(int i=0 ; i<height ; i++ )
SetPixel(x, y+i);
}
정수 직경이 아닌 직경을 사용하려면 고정점의 정밀도를 높이거나 이중 값을 사용할 수 있습니다.dY2 + (ray - x) * (ray - x)와 ray2 (dx² + dy² 및 r²)의 차이에 따라 일종의 안티 에일리어스를 만들 수도 있습니다.
포인트 리스트를 생성하고 폴리곤 그리기 함수를 사용하여 렌더링합니다.
빠른 알고리즘을 원하는 경우 N개의 변이 있는 폴리곤을 그리는 것이 좋습니다. N이 높을수록 원이 더 정밀해집니다.
원하는 알고리즘이 아닐 수도 있고 가장 성능이 좋은 알고리즘이 아닐 수도 있습니다.
저는 항상 이런 걸 해요.
void fillCircle(int x, int y, int radius){
// fill a circle
for(int rad = radius; rad >= 0; rad--){
// stroke a circle
for(double i = 0; i <= PI * 2; i+=0.01){
int pX = x + rad * cos(i);
int pY = y + rad * sin(i);
drawPoint(pX, pY);
}
}
}
다음 두 가지 방법은 원의 여러 부분을 한 번에 그려서 반복 제곱근 계산을 피할 수 있으므로 매우 빠릅니다.
void circleFill(const size_t centerX, const size_t centerY, const size_t radius, color fill) {
if (centerX < radius || centerY < radius || centerX + radius > width || centerY + radius > height)
return;
const size_t signedRadius = radius * radius;
for (size_t y = 0; y < radius; y++) {
const size_t up = (centerY - y) * width;
const size_t down = (centerY + y) * width;
const size_t halfWidth = roundf(sqrtf(signedRadius - y * y));
for (size_t x = 0; x < halfWidth; x++) {
const size_t left = centerX - x;
const size_t right = centerX + x;
pixels[left + up] = fill;
pixels[right + up] = fill;
pixels[left + down] = fill;
pixels[right + down] = fill;
}
}
}
void circleContour(const size_t centerX, const size_t centerY, const size_t radius, color stroke) {
if (centerX < radius || centerY < radius || centerX + radius > width || centerY + radius > height)
return;
const size_t signedRadius = radius * radius;
const size_t maxSlopePoint = ceilf(radius * 0.707106781f); //ceilf(radius * cosf(TWO_PI/8));
for (size_t i = 0; i < maxSlopePoint; i++) {
const size_t depth = roundf(sqrtf(signedRadius - i * i));
size_t left = centerX - depth;
size_t right = centerX + depth;
size_t up = (centerY - i) * width;
size_t down = (centerY + i) * width;
pixels[left + up] = stroke;
pixels[right + up] = stroke;
pixels[left + down] = stroke;
pixels[right + down] = stroke;
left = centerX - i;
right = centerX + i;
up = (centerY - depth) * width;
down = (centerY + depth) * width;
pixels[left + up] = stroke;
pixels[right + up] = stroke;
pixels[left + down] = stroke;
pixels[right + down] = stroke;
}
}
언급URL : https://stackoverflow.com/questions/1201200/fast-algorithm-for-drawing-filled-circles
'programing' 카테고리의 다른 글
| C에서 =+는 무엇을 의미합니까? (0) | 2022.09.01 |
|---|---|
| JDBC에서의 접속 풀링 옵션: DBCP와 C3P0 (0) | 2022.09.01 |
| 스테이트먼트와 Prepared 스테이트먼트의 차이 (0) | 2022.09.01 |
| Java 8 LocalDate Jackson 형식 (0) | 2022.09.01 |
| vuex에서 데이터 분리 (0) | 2022.09.01 |