• ベストアンサー

円弧の描画方法

 円(または1/8円弧)の描画アルゴリズムとして ミッチェナーの円のアルゴリズムが知られています。 しかし、任意の円弧(例えば、長方形に内接するような→MFCのライブラリに あるような指定方法や3点を指定して円弧を描画する)を高速に描画する 方法はありますか?ミッチェナーの方法の変形(制限)でもいいので 教えてください。

質問者が選んだベストアンサー

  • ベストアンサー
  • ametsuchi
  • ベストアンサー率31% (81/257)
回答No.3

問題を2つに分けましょう。 (1) 3点から円弧を求める方法: とりあえず約束として、 P0:円弧始点 P1:円弧通過点 P2:円弧終点 O:求める円弧中心 R:円弧半径 とします。時計回りか、反時計回りかはここでは問いません。 線分P0P1、線分P1P2 にOから下ろした垂線の足は線分の中点ですから、線分長を L01 = dist(P0, P1) L12 = dist(P1, P2) として、 <P1-P0, O> - 0.5*L01^2 = 0 <P2-P1, O> - 0.5*L12^2 = 0 です。ここに、<, >は内積を表わします。 これは、Oの成分、Ox,Oyに関する連立一次方程式になり、 det = (P1x-P0x)*(P2y-P1y) – (P1y-P0y)*(P2x-P1x) として、 Ox = 0.5* {L01^2*(P2y-P1y) – L12^2*(P1y-P0y)} / det Oy = 0.5* {-L01^2*(P2x-P1x) + L12^2*(P1x-P0x)} / det……………Equ.1) が求まります。但し、3点の内2点が重なるとか、3点が一直線上に並ぶ場合はdet=0になるので注意が必要です。「円弧は求まらない」としてエラー処理しなくてはなりません。 半径は以下のように容易に求まります。 R = |P0 - O|…………………………………………………………………Equ.2) 始終角を求めます。先ず、 θ0 = atan2(P0y-Oy, P0x-Ox) θ1 = atan2(P1y-Oy, P1x-Ox) θ2 = atan2(P2y-Oy, P2x-Ox)…………………………………………………….Equ.3) として、円弧中心から見た3点の角度が-π~+πの範囲で求まります。 これを θ0’ = 0 θ1’ =θ1 -θ0 θ2’ =θ2 -θ0………………………………………………………………………Equ.4) と始点基準にします。 これを、0~2πの値に変換して、 ・θ2’ < θ1’ なら反時計回り ・θ1’ < θ2’ なら時計回り なのです。あと処理の都合のため、時計回り回りなら始終点を入れ替わると、必ず反時計回りになります。以下、「円弧」と言うと、 ・中心(上のOですが、あなたのプログラムでは、「x0, y0」です) ・半径(上のRですが、あなたのプログラムでは「r」です) ・始角(反時計回り) ・終角(反時計回り) で表現されるものとします。ただ、Equ.3)で分かるとおり、既に、コストのかかる逆三角関数を3回も用いています。 (2) 円弧ベクター->ラスター変換: 先ず、「ミッチェナーのアルゴリズム」ですが、ご存知のように、 1) 円を8分割し、対称性を利用して基本1パタン(東->北、0°~45°)を利用。 2) 基本パタンでは、y:必ず1Pixelずつ増加、x:0または1Pixel減少。 3) x: 0または-1を判断するのに、「真円からのx方向差分」を巧妙な計算で求める。 ただし、この差分は、x: 0または-1で異なる。 という非常に巧妙な仕掛けになっている訳です。三角関数は勿論、sqrt()も一度も使われていません。しかも近似計算ではなく、誤差は1/2Pixel以内というか、可能な限りでの正確な計算になっています。 本題に入ると、whileループに入る前に、(1)で求めた始終角から、 0) この1/8セルの処理区分, 開始y, 終了y 1) この1/8セルの処理区分, 開始y, 終了y 時計回り 2) この1/8セルの処理区分, 開始y, 終了y 時計回り 3) この1/8セルの処理区分, 開始y, 終了y 4) この1/8セルの処理区分, 開始x, 終了x 時計回り 5) この1/8セルの処理区分, 開始x, 終了x 6) この1/8セルの処理区分, 開始x, 終了x 7) この1/8セルの処理区分, 開始x, 終了x 時計回り なる8つの行からなるテーブルを作ったら如何でしょうか?8個固定ですから配列でなくてもいいです。 ・ 1/8セルの処理区分: (1) 全域無効、描かない、 (2) 全域有効、描く。 (3) 一部有効、開始~終了範囲だけ描く。 ・開始・終了y(x):必ず開始<終了になります。 0)~7)何れも、最大で=r、最小で=0.707*rです。ここは気を付けて下さい。 No.2で「forループにして、forループインデックスの範囲」てなこと言いましたが、whieループでいいと思います。「開始終了y(x)」を角度から求めるには始終点位置の角度に関しては残念ながら、三角関数を一度ずつ使わなくてはいけないでしょう。それ以外の場合は、r0.707*rです。三角関数計算は不要です。

その他の回答 (4)

  • ametsuchi
  • ベストアンサー率31% (81/257)
回答No.5

くどくて申し訳ない。 三角関数も使わずに済みそうです。 1)円の中心と半径は「No.3」のとおり求める。 2)「No.3」では、始終角を求めていたが、これの替わりに、3点が8セクタの内どこに落ちるか判定する。これは ・P0-O ・P1-O ・P2-O のx成分、y成分の大小関係などを調べれば容易に分かる。「O」は円弧中心座標。 3)一番難しいのは、円弧の有効側を調べ、8セクタ各々、「No.3」での3分類をすること。

  • ametsuchi
  • ベストアンサー率31% (81/257)
回答No.4

訂正します。 先程、始終角位置では、三角関数を一度づつ使わなくてはいけないと言いましたが、元々、3点が分かっているので、三角関数は使わなくて済みます。失礼しました。 逆三角関数(=atan2)を使わなくて出来るかどうか分かりません。上手く場合分けすると、逆三角関数を使わなくて済むかも知れません。 申し訳ないが、後はご自分で考えて下さい。

  • ametsuchi
  • ベストアンサー率31% (81/257)
回答No.2

すいません。質問がでてたんですね。sekinegooさんは、 1)プログラムの簡潔さ 2)処理効率 どちらを優先させようとしているのでしょう?実はsekinegooさんの目的自体イマイチ分かっていません。 私自身は、図形処理自体は職業として20年以上携わっていますが、ベクターデータが殆どです。ラスターデータは、画像データとか、地形標高データ(=DEM)位のものです。今回の ・ベクター-->ラスター変換 は、昔某テレビ局向けにPolygonデータを放送用の画像データに変換した位で、「ミッチェナーのアルゴリズム」の本の上で知っているに過ぎないのでシロートです。 我々図形処理屋は、ベクターデータが基本ですから、円弧は3点から求めたり、2線に接する半径Rの円弧を求めたり様々です。2D円弧は、 ・中心 ・半径 ・始角(反時計回り)、これを「FROM角」と名付けましょう。 ・終角(反時計回り)、これを「TO角」と名付けましょう。 という「標準形」で持つことが多いです。最近流行のNURBSで表現する手もありますが...。 で、効率を無視するなら、 (1)まず円弧を求める。(上の「標準形」で) (2)円弧を折れ線近似する。(折れ線の精度が問題!!) (3)折れ線の各線分をDDA変換 という手もあります。それならプログラムは簡単ですが、精度を上げるには折れ線を細かく分割しなくてはならず、三角関数計算を辺数に比例して行なわなくてはならないので処理効率が落ちます。処理効率を上げようとすると、今度は精度が失われます。しかも、ミッチェナーのアルゴリムとは何の関係もなくなっちゃいます。 一方、処理効率受重視なら、プログラムが多少複雑でも、 「SetPointで点を打つときに判定して打つ、打たない...」とし、「ややこしくなって」しまうのはやむを得ないのではないでしょうか? 先ず、「FROM角」、「TO角」から、8つの内そのセルどういうセルか分かります。 イ)全く描かないセル ロ)開始側の一部だけ描くセル ハ)終了側の一部だけ描くセル ニ)全部描くセル イ)とニ)は問題ないです。問題はロ)とハ)です。これも「FROM角」、「TO角」から分かります。というより、 ■「FROM角」、「TO角」から、8つのセルがイ)~ニ)どれに該当し、ロ)とハ)の場合、各セル毎の範囲が分かる。 わけです。できれば三角関数はコストのかかる計算ですから、避けたいですね。whileループになってますが、forループで、整数の範囲ではじければ理想です。No.1でも言ったように、1/8セル内では、円弧は単調増加(または減少)ですから、工夫次第で、角度範囲をforループインデックスの範囲(=整数値)に置き換えることができるはずです。 ではご健闘を!ウソがあったらごめんなさい!

sekinegoo
質問者

補足

わざわざ回答していただき、感謝致します。 三角関数は、使いたくないので、整数計算だけで行いたいと思います。 Cマガジンに図形描画の記事があって、バックナンバーをすべて購入して 読みましたが、円はあっても円弧は、ありませんでした。インターネットを 探しても、円はあっても円弧はありません。できれば3点円から描画したい と思いますが、ミッチェナーのアルゴリズムが高速なので、これの変形(点を打つ/打たないの判定を入れる)として 求めたいのですが、MFCのように範囲指定になってもかまいません。 虫のいい話ですが、Cの関数として、欲しいのです。ですから、簡単に 言えば、MFCのような引数で、実際のソースがあったらいいなと思って います。インターネットでもCマガジンでも円のソースはあっても、円弧の ソースは、どこにもありません。3点指定の円描画はあきらめるとしても 始点終点指定のプログラムがどこかにないかと探しています。 私が作ると、点描画する/しないの判定が、どうしても冗長になって しまいます。よろしくお願いします。

  • ametsuchi
  • ベストアンサー率31% (81/257)
回答No.1

ミッチェナーの方法の変形をすればいいのでは? 円を描くのも1/8円弧の組み合わせに過ぎない訳です。で、1/8円弧の特徴として、 ■単調性 即ち、xが増加した時、yが増加するか、減少するか何れかで、1/8円弧の範囲内で増減することはないことが挙げられます。 ですから、 1)描くべき円弧の中心と、始角・終角を求めておく。 2)描くべき円弧を分割する。1/8円弧に。 3)以下、各1/8円弧毎、 3.1)始角・終角がこの1/8円弧にかからないなら、ミッチェナーの円弧そのまま 3.2)始角・終角がこの1/8円弧にかかるなら、「単調性」を利用して、開始・終了x、yを抑えておき、ミッチェナーの円弧を生成する際、x,y(=座標値)が、 3.2.1)開始・終了範囲に入るなら、Pixelを描く。 3.2.2)開始・終了範囲に入らないなら、Pixelを描かない。この際、「描く」-->「描かない」になったら、Loopを抜けてよい。

sekinegoo
質問者

補足

ミッチェナーの円を具体的にプログラムにすると //************************************************************ // DrawCircle - ミッチェナーによる円描画 // //入力値: // int xo, yo 円の中心 // int r 円の半径 // int color 円周の色 //************************************************************ void DrawCircle(int xo, int yo, int r, int color) { int x, y; x = r; y = 0; while (x >= y){ SetPoint(xo + x, yo + y, color); SetPoint(xo + x, yo - y, color); SetPoint(xo - x, yo + y, color); SetPoint(xo - x, yo - y, color); SetPoint(xo + y, yo + x, color); SetPoint(xo + y, yo - x, color); SetPoint(xo - y, yo + x, color); SetPoint(xo - y, yo - x, color); r -= (y << 1) - 1; if (r < 0){ r += (x - 1) << 1; x--; } y++; } } こうなんですが、ここでSetPointで点を打つときに判定して 打つ、打たないをすれば良いわけですが、どうもややこしく なってしまいそうです。短いプログラムでできますか。

関連するQ&A

  • Bresenhamのアルゴリズムを用いた円弧描画

    Bresenhamを用いた直線、円、円弧(45度単位)での変換 アルゴリズムは調べることが出来たのですが、円弧の任意の角度 の変換方法が分かりません。 参考資料などありましたら 教えていただけないでしょうか? 例えば、  始点、終点、回転の向きを指定するとか、  30度と角度を指定する等。 宜しくお願い致します。

  • 円弧の描画について

    円弧の描画について お世話になります。 Visio2007を使用しています。 Visioで円を描画し、その円の情報を基に計算を行い、円弧の作成をしたいと考え ていますが、計算方法が分からずご質問させて頂きました。 以下の【元となる情報】から【求める情報】を計算にて求めます。 【元となる情報】 左上X座標:円の左上X座標 左上Y座標:円の左上Y座標 幅:円の幅 高さ:円の高さ 始点角度:円弧の始点の角度(円の中心から右方向を0度とし       時計回りの角度) 終点角度:円弧の終点の角度(始点角度を0度とし時計回りの角度) (始点角度と終点角度は1度単位で設定をします) 【求める情報】 http://msdn.microsoft.com/ja-jp/library/cc344284.aspx 例えば、 ・始点角度が0度、終点角度が90度の時は円の右下1/4の円弧が作成される ・始点角度が90度、終点角度が180度の時は円の左半分の円弧が作成される 以上の様な円弧を求めるような計算方法をご存知でしたらご教授 お願い致します。

  • 傾いた楕円の描画方法

    PCでの楕円の描画は、ライブラリに組み込まれていますが、水平(または垂直)の楕円については、関数1行で描画することができます。 ところが、傾いている楕円については、描画することができません。 そこで、ミッチェナーのアルゴリズムで円を描くプログラムを変形して、上下(左右)のプロット位置をずらせば、一応、楕円は描画できるので、さらにプロットする部分に回転をかければ回転した楕円を描画できると考えて、プログラムを作成してみました。 しかし、あまり綺麗な楕円を描画できません。 ミッチェナーのアルゴリズムを上下に圧縮した時点で、左右の部分が少し密になり(これは許容できる範囲ですが)それを回転させるとき、実数計算になるため、最終的な位置は、ドットのどちらかになってしまうので、あまりうまくいきません。 ミッチェナーのあるごりずむの原理を使って、傾いた楕円の式から、直接プロットしなければ綺麗な楕円を描画することができないと考えます。 最終的に欲しい関数は、傾いた楕円の外接する4点の座標を与えて、描画する関数です。

  • AutoCADで円弧を描く方法について

    AutoCAD Mechanical 2009を使用しています。 下記の円弧(又は円)を描きたいと考えております。 ・半径7000 ・長方形の1辺Aに接し、Aの中点に接する ・長方形の2辺B,Cを通る(通過点は指定無し) 無理やり描くには、辺Aの中点から長さ7000の線分を引き、その線分の端点を中心とする半径7000の円を描けばよいのですが、 極力無駄な線は描かずに、効率よく描く方法をご教授願います。 宜しくお願い致します。

  • 円弧の描画について

    ある参考書の内容について分からない点があります。(VB6です。) '変数と定数の定義 Dim startAngle As Double Dim endAngle As Double Const pi = 3.14152965 '角度の初期値 startAngle = 90 endAngle = 315 '線の色の指定 ForeColor = QBColor(4) '円弧の描画 circle (2000,1500) , 1000, , startAngle * pi / 180, endAngle * pi/180 End Sub 変数の定義で、startAngleとendAngleがDouble型で宣言されているのに、初期値は小数ではなく整数なのはなぜでしょうか。たぶん、初期値は整数だけど、startAngle * pi / 180, endAngle * pi / 180が小数になるからDouble型にしていると思うのですが、このあたりのことを教えていただけますか。

  • AutoCAD LT 2007での長方形描画について

    AutoCAD LT 2007です。 4点ABCDからなる長方形の対角2点の座標(”点Aと点C”または ”点Bと点D”)と長さを指定すれば、指定した長さ分内側に 長方形が描画出来るようなコマンド?マクロ?を作成することは 出来ますでしょうか? 例えば、座標0,0&座標7,10、長さ2(元の長方形)とすれば、 座標2,2&座標5,8を対角とする長方形(新たに描画される長方形)が 描けるといったようなことです。 教えて下さい。 何卒よろしくお願い申し上げます。

  • 【Fash actionscript】楕円を描画したい

    actionscriptで楕円を描画したいです。 円を描画するとこまでは、以下ページに説明があったので、 http://www.geocities.jp/swf_daisuke/school/class3.html できたのですが、応用ができなくて困ってます。 楕円といっても色々あるでしょうが、長方形が内接するような楕円です。 ご指導のほど、よろしくお願いいたします。

    • ベストアンサー
    • Flash
  • 線分や円弧をクリックして選択するプログラム

    CAD等で描かれた2次元の図面上の任意の線(線分や円弧)をクリックして選択するプログラムを作っています。 いまは叩き台として、各線のバウンディングボックス(線分や円弧を囲む最小の長方形)の情報(対角線の両端座標) が入った配列(実際はC++のSTL vectorです)を用意して、クリックした座標の一番近くに在る、若しくは内包する バウンディングボックスを線形探索して、見つかったバウンディングボックスに所属する線がクリック許容範囲内 であるかを分析しています。 しかし、この方法では線の数が少ないうちは良いのですが、大規模な図面になると時間が掛かってしまい 使い物になりません。 このような場合、どういったデータ構造でどのようなアルゴリズムで探索するのが良いのでしょうか? なにか定石的なものがあるのでしょうか? 恥ずかしながら、探索アルゴリズムというと学生の時に2分探索法等を習った程度で、2次元以上の高次元のもの 扱うアルゴリズムはピンときませんでした。

  • パラメトリック曲線の描画アルゴリズムについて

    x = f(t) y = g(t) のように表せるパラメトリック曲線を2次元のビットマップ画像に描画したいと考えています。 (たとえばNURBS) 描画アルゴリズムですが、tを適当に変化させてx,yの組を得てその点を打つことにより曲線 を書くことはできます。 ただこの場合tの増分の選び方が大きいと穴が開いてしまいますし、小さいと何度も同じx,yを 描画することになってしまい効率が悪いです。 x、yの適切な変化量(たとえばプラスマイナス1)となるtの増分を求められればいいのですが、 具体的なアルゴリズムが思い当たりません。 他の方法でも構いませんが、一般的にパラメトリック曲線を描画する高速なアルゴリズムをご存知 でしたらご教授いただけたらと思います。

  • 円の描画の太さを指定できるCコード

    円の描画を行うCコードを記述していますが Michenerのアルゴリズムにより円を下記サイトを参考に記述できました。 しかし、アルゴリズムの理解不足の為、円の太さを指定できるようにしたいのですが、なかなか上手くいっておりません。 もし、円の太さを指定できるCコードなどありましたら教えていただけないでしょうか?