7

ブレゼンハムの直線アルゴリズムで円弧を作る方法を探しています。このアルゴリズムは完全な円を描画しますが、円弧 (0 から Pi まで) を描画し、それを 30 度 (たとえば) 回転させる必要がある場合はどうすればよいでしょうか?

void DrawCircle(HDC hdc,int x0, int y0, int radius) 
{
        int x = 0;
        int y = radius;
        int delta = 2 - 2 * radius;
        int error = 0;

        while(y >= 0) {
                //SetPixel(hdc,x0 + x, y0 + y,pencol);
                SetPixel(hdc,x0 + x, y0 - y,pencol);
                //SetPixel(hdc,x0 - x, y0 + y,pencol);
                SetPixel(hdc,x0 - x, y0 - y,pencol);
                error = 2 * (delta + y) - 1;
                if(delta < 0 && error <= 0) {
                        ++x;
                        delta += 2 * x + 1;
                        continue;
                }
                error = 2 * (delta - x) - 1;
                if(delta > 0 && error > 0) {
                        --y;
                        delta += 1 - 2 * y;
                        continue;
                }
                ++x;
                delta += 2 * (x - y);
                --y;
        }
}
4

2 に答える 2

4

ブレゼンハムを確認する必要がない場合は、このSO投稿で紹介されている高速ステップ方式があります。この方法では、中心点、開始点、および円弧角度を設定できます。すでにアルゴリズムに含まれているため（円弧角度による）、停止基準は必要ありません。高速化するのは、接線方向および半径方向の移動係数の事前計算であり、実際のループには三角関数の呼び出しはなく、乗算、加算、減算のみが行われます。

AFAIKには、次の3つのタイプの方法があります
。A）ブレゼンハムのようなインクリメンタル
B）この
ような細分割方法 C）ステップ（またはセグメント）方法

ステップメソッドの遅い例を取り上げます（速度が重要な場合はこれを使用しないでください）：

// I know the question is tagged c++, but the idea comes clear in javascript
var start_angle = 0.5, end_angle = 1.1, r = 30;
for(var i = start_angle; i < end_angle; i = i + 0.05)
{
  drawpixel(x: 50 + Math.cos(i) * r, y: 100 + Math.sin(i) * r); // center point is (x = 50, y = 100)
}

遅さは、ループで（不必要に）繰り返されるcosとsinから来ます。これは、上記のSOの投稿で説明されているように、cosとsinを事前に計算することで解決できます。これは、大幅な高速化を意味します（top5 javascriptエンジンで平均12倍）。

私は、さまざまな円と円弧の描画アルゴリズムの完全に比較できない速度テストを行いました。ブレゼンハムは高速ですが、開始基準と停止基準のロジックを追加する必要があります。これにより、アルゴリズムが少し遅くなります。ブレゼンハムとアークが本当に必要な場合、私にはこれに対する準備ができた解決策がなく、まだそのようなものは見つかりません。確かに可能です。ちなみに、事前に計算されたトリガーを使用するステップメソッドは、ブレゼンハムと比較してパフォーマンスがそれほど悪くありません（少なくともjavascriptでは）。C++でテストして報告してください。

于 2013-02-10T00:17:43.120 に答える
4

（円周率に対して）1/2円を取得するには、SetPixelルーチンの1つだけを呼び出します。円弧を30度回転させるには、いくつかのトリガーが必要です。x / y比がtan（30度）に等しくなるまで上記のループを実行し、次に、比が停止したい値に達するまで実際に描画を開始できます。最も効率的な方法ではありませんが、機能します。それをより良くするために、あなたはあなたの最初の4つのvar値を事前に計算する必要があるでしょう。上記の実行から値を取得し、それらを開始値としてプラグインすることができ、それは非常に効率的です。

上記のアルゴリズムは、MichaelAbrashのBlackBookのものから入手しましたか？そうでない場合は、高速の円/円弧の描画に関する2番目の参照ポイントとしてグーグルで検索します。

残念ながら、チャプターをリッピングする楕円はそこに含まれていませんでした。これが私がウェブ上で見つけた、Abrashからのものであると主張するものです：


/* One of Abrash's ellipse algorithms  */

void draw_ellipse(int x, int y, int a, int b, int color)
{
    int wx, wy;
    int thresh;
    int asq = a * a;
    int bsq = b * b;
    int xa, ya;

    draw_pixel(x, y+b, color);
    draw_pixel(x, y-b, color);

    wx = 0;
    wy = b;
    xa = 0;
    ya = asq * 2 * b;
    thresh = asq / 4 - asq * b;

    for (;;) {
        thresh += xa + bsq;

        if (thresh >= 0) {
            ya -= asq * 2;
            thresh -= ya;
            wy--;
        }

        xa += bsq * 2;
        wx++;

        if (xa >= ya)
          break;


        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }

    draw_pixel(x+a, y, color);
    draw_pixel(x-a, y, color);

    wx = a;
    wy = 0;
    xa = bsq * 2 * a;

    ya = 0;
    thresh = bsq / 4 - bsq * a;

    for (;;) {
        thresh += ya + asq;

        if (thresh >= 0) {
            xa -= bsq * 2;
            thresh = thresh - xa;
            wx--;
        }

        ya += asq * 2;
        wy++;

        if (ya > xa)
          break;

        draw_pixel(x+wx, y-wy, color);
        draw_pixel(x-wx, y-wy, color);
        draw_pixel(x+wx, y+wy, color);
        draw_pixel(x-wx, y+wy, color);
    }
}

円の8番目を一度にx4で描画し、次に反転して他の8番目を描画するというアイデアです。それでもあなたの質問に直接答えることはできません。それに取り組んでいます...

繰り返しますが、上記のコードは機能するはずです。開始条件と終了条件を注意深く制御する必要があります。y> = 0は、「弧」の長さを終えたときのyになる必要があり、開始値は弧の始点になるように計算する必要があります。

これは、現状のままでは簡単な作業ではありません。代わりに浮動小数点ルーチンを使用する方が簡単かもしれません。計算ははるかに簡単で、プロセッサはこれらの整数ルーチンが作成されたときよりもうまく処理できるようになりました。

于 2011-12-09T16:01:17.420 に答える