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

このQ&Aに関連する最新のQ&A

A 回答 (5件)

問題を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です。三角関数計算は不要です。
    • good
    • 0

くどくて申し訳ない。



三角関数も使わずに済みそうです。

1)円の中心と半径は「No.3」のとおり求める。

2)「No.3」では、始終角を求めていたが、これの替わりに、3点が8セクタの内どこに落ちるか判定する。これは

・P0-O
・P1-O
・P2-O

のx成分、y成分の大小関係などを調べれば容易に分かる。「O」は円弧中心座標。

3)一番難しいのは、円弧の有効側を調べ、8セクタ各々、「No.3」での3分類をすること。
    • good
    • 0

訂正します。



先程、始終角位置では、三角関数を一度づつ使わなくてはいけないと言いましたが、元々、3点が分かっているので、三角関数は使わなくて済みます。失礼しました。

逆三角関数(=atan2)を使わなくて出来るかどうか分かりません。上手く場合分けすると、逆三角関数を使わなくて済むかも知れません。

申し訳ないが、後はご自分で考えて下さい。
    • good
    • 0

すいません。

質問がでてたんですね。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ループインデックスの範囲(=整数値)に置き換えることができるはずです。

ではご健闘を!ウソがあったらごめんなさい!

この回答への補足

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

補足日時:2001/05/26 20:08
    • good
    • 0

ミッチェナーの方法の変形をすればいいのでは?



円を描くのも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を抜けてよい。

この回答への補足

ミッチェナーの円を具体的にプログラムにすると
//************************************************************
// 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で点を打つときに判定して
打つ、打たないをすれば良いわけですが、どうもややこしく
なってしまいそうです。短いプログラムでできますか。

補足日時:2001/05/14 13:48
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q「MFCを使用しない」から「MFCのスタティックライブラリを使用」

VC++初心者ですが、

Win32Applicationで「MFCを使用しない」で作成したプログラムが正常動作しました。 そこで
「MFCを使用しない」から「MFCのスタティックライブラリを使用」にしてビルドしたところ、リンク中に
どんどんエラーがでます。 関数関係のエラーなのですが。

(1) どうすればエラーを無くせるのでしょうか
(2) 「MFCのスタティックライブラリを使用」にするとどの様なメリットがあるのか(説明している参考URLなど)。

教えて下さい

Aベストアンサー

>(1) どうすればエラーを無くせるのでしょうか

プロジェクトを作り直すのが手っ取り早いです。ソースを修正したり、プロジェクトのリンク対処のライブラリを変更したりすれば何とかできることはできますがおすすめしません。

作り直したプロジェクトに、自分が追加ソースをコピペしていけばちゃんと動くと思います。(ウィザードが自動で追加した分も含む)

>(2) 「MFCのスタティックライブラリを使用」にするとどの様なメリットがあるのか(説明している参考URLなど)。

簡単に書くと、

メリット
・使用しない
実行ファイルサイズが小さくなる。

・使用する
実行するときにMFCのランタイムDLLが不要になる。


デメリット
・使用しない
MFCのDLLに依存するので、DLLのバージョンの違いで動作に不具合が出る可能性がある。

・使用する
実行ファイルのサイズが馬鹿でかくなる。

QBresenhamのアルゴリズムを用いた円描画

一つ下の質問をした後に、いろいろ考えて作ったプログラムなのですが、コンパイルが通りません。
頭がこんがらがってしまったので、教えていただけるとうれしいです。

main(){
   int x, y, r, d;

   printf("Enter coordinates of radius of circle. R = ");
   scanf("%d\n", &r);

   x = 0;
   y = r;
   d = 3 - 2 * r;

   while(y > x){
     plotcircle(x, y, r);
     if(d < 0){ /* select U */
        d = d + 4 * x + 6;
     }else{ /* select D */
        d = d + 4 * (x - y) + 10;
        y = y - 1;
     }
     x = x + 1;
   }

   if(x == y){
     plotcircle(x, y, r);
   }
}


plotcircle(int x, int y, int r){
   putpixel( x, y, r);
   putpixel( y, x, r);
   putpixel( y, -x, r);
   putpixel( x, -y, r);
   putpixel(-x, -y, r);
   putpixel(-y, -x, r);
   putpixel(-y, x, r);
   putpixel(-x, y, r);
}

一つ下の質問をした後に、いろいろ考えて作ったプログラムなのですが、コンパイルが通りません。
頭がこんがらがってしまったので、教えていただけるとうれしいです。

main(){
   int x, y, r, d;

   printf("Enter coordinates of radius of circle. R = ");
   scanf("%d\n", &r);

   x = 0;
   y = r;
   d = 3 - 2 * r;

   while(y > x){
     plotcircle(x, y, r);
     if(d < 0){ /* select U */
        d = d + 4 * x + 6;
   ...続きを読む

Aベストアンサー

計算は間違ってないようですので、描画をなんとかすれば動くと思います。

参考まで。(画面を50*50サイズで、円の中心を25,25に固定しています)

#include <stdlib.h>
#include <stdio.h>

char disp[50][50]; // 画面領域の定義(50*50固定)
void plotini(void); // 画面を消す
void plotcircle(int, int, int, int, int); // 画面に点を打つ
void plotdisp(void); // 画面を表示する

int main(){
 int x, y, r, d;

 printf("Enter coordinates of radius of circle. R = ");
 scanf("%d", &r);

 plotini();

 x = 0;
 y = r;
 d = 3 - 2 * r;

 while(y > x){
  plotcircle(x, y, 25, 25, 'X');
  if(d < 0){ /* select up */
   d = d + 4 * x + 6;
  }else{ /* select bottom */
   d = d + 4 * (x - y) + 10;
   y = y - 1;
  }
  x = x + 1;
 }

 if(x == y){
  plotcircle(x, y, 25, 25, 'X');
 }

 plotdisp();

 return 0;
}

void plotini(void) {
 int i,j;
 for (i=0; i<50; i++) for (j=0; j<50; j++) disp[i][j]=' ';
}

void plotcircle(int x, int y, int xc, int yc, int c) {
 int xx,yy;
 xx = xc+x; yy = yc+y; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc+y; yy = yc+x; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc+y; yy = yc-x; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc+x; yy = yc-y; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc-x; yy = yc-y; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc-y; yy = yc-x; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc-y; yy = yc+x; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
 xx = xc-x; yy = yc+y; if (xx>=0 && x<50 && yy>=0 && yy<50) disp[yy][xx]=c;
}

void plotdisp(void) {
 int i,j;
 for (i=0; i<50; i++) {
  for (j=0; j<50; j++) {
   printf("%c",disp[i][j]);
  }
  printf("\n");
 }
}

計算は間違ってないようですので、描画をなんとかすれば動くと思います。

参考まで。(画面を50*50サイズで、円の中心を25,25に固定しています)

#include <stdlib.h>
#include <stdio.h>

char disp[50][50]; // 画面領域の定義(50*50固定)
void plotini(void); // 画面を消す
void plotcircle(int, int, int, int, int); // 画面に点を打つ
void plotdisp(void); // 画面を表示する

int main(){
 int x, y, r, d;

 printf("Enter coordinates of radius of circle. R = ");
 scanf("%d", ...続きを読む

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

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

Aベストアンサー

座標を記録しなくても描画可能です。
単純ループではなく、以下のような2重ループ構成にします。
外: yを(R+0.5d)から0まで1づつ減らしていくループ
中: yがその座標に等しい間、xを増やしていくループ
これで、各y座標に対応するx座標が求まります。
あとは、
・yが(R+0.5d)~(R-0.5d)の間
→外周のMichenerについてだけ中ループを実施、求まったx座標から線を引く
・yが(R-0.5d)~0の間
 →外周・内周両方のMichenerについて中ループを実行、内周と外周両方のx座標を求めて、その間を結ぶ線分を描画
といった形にすればOK。

Q角が丸い長方形の描画

角が丸い長方形を描画する自作関数を作成中なのですが、どうやったら角に丸みをつけられるのでしょうか?
SetPixelで1ドットずつ描画しています。
また、その図形に影をつけたいのですがどこか参考になるサイト等ありましたら教えてください。

開発環境は
WindowsXP
Visual C++ 6.0 です。

よろしくお願いいたします。

Aベストアンサー

★アドバイス
・API に RoundRect() 関数があります。
 下の『参考URL』をどうぞ。
・自作する場合は Arc()、Pie() と直線(長方形)を組み合わせて描画します。
 特に自作する必要がなければ RoundRect() 関数を利用しましょう。
・以上。

参考URL:http://wisdom.sakura.ne.jp/system/winapi/win32/win24.html

QMFC 分割ウィンドウのそれぞれ窓の描画に関して

MFCプログラミング初心者ですが、宜しくお願いいたします。

---------------プログラム環境---------------
WinXP2 Visula Studio 2005 Pro
--------------------------------------------

現在、上記の環境で、SDIプログラムを書いています。
ご教示していただきたいことは、分割ウィンドウにおけるそれぞれの窓の
表示内容を変えたいということです。TCP/IPのプログラムで、受信したMessageをstrstrなどで振り分けて、各々の窓に表示したいのですが、
どういう風にやればいいのですか??
なお、一つのViewに受信メッセージを表示させることは出来ました。
非常に困っています。

現在、CMainFrame::OnCreateClient(~~~)とMainFrame.cppに書き、
ウィンドウを3分割にしております。

m_wndSplitter.CreateStatic(this,1,2);
m_wndSplitter.CreateStatic(&m_wndSplitter,2,1,WS_CHILD | WS_VISIBLE,WS_BORDER,m_wndSplitter.IdFromRowCol(0,1));

m_wndSplitter.CreateView(0,0,RUNTIME_CLASS(??View)),~~
m_wndSplitter1.CreateView(0,0,RUNTIME_CLASS(??View)),~~
m_wndSplitter1.CreateView(1,0,RUNTIME_CLASS(??View)),~~

この用に記述しております。

説明しずらいのですが、??Viewの箇所にスケルトンの時にできていたView
クラスを入れてやると、そのエリアに受信メッセージが表示されます。
初心者なので、まと外れかもしれませんが、新しいViewクラスを作成して
なにかやれば、よいのでしょうか?? 現在3つのウィンドウにそれぞれの
メッセージを表示させたいので、Viewクラスはそれぞれ3個なければ、いけないのでしょうか??
わかりずらい説明で申し訳ないですが、宜しくお願いいたします。

MFCプログラミング初心者ですが、宜しくお願いいたします。

---------------プログラム環境---------------
WinXP2 Visula Studio 2005 Pro
--------------------------------------------

現在、上記の環境で、SDIプログラムを書いています。
ご教示していただきたいことは、分割ウィンドウにおけるそれぞれの窓の
表示内容を変えたいということです。TCP/IPのプログラムで、受信したMessageをstrstrなどで振り分けて、各々の窓に表示したいのですが、
どういう風にやればいいのですか??
なお、一...続きを読む

Aベストアンサー

MFCのクラスをそのまま使うってことはないかもしれないけど
あえてそれを無視して、という前提で。

左側は
((CEditView *)m_wndSplitter.GetPane(0,0))->SetWindowText("左だよ");
右側の上は
((CEditView *)m_wndSplitter1.GetPane(0,0))->SetWindowText("上だよ");
右側の下は
((CEditView *)m_wndSplitter1.GetPane(1,0))->SetWindowText("下だよ");
かな。

#実際はSetWindowTextなんか使わないと思うけど、
#ここは一例ということで。


このカテゴリの人気Q&Aランキング

おすすめ情報