質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

4回答

10854閲覧

直線を書くアルゴリズムについて

退会済みユーザー

退会済みユーザー

総合スコア0

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1グッド

6クリップ

投稿2018/09/30 14:40

編集2018/09/30 14:53

直線が書きたいため直線を書くアルゴリズムを探しているのですが、自分が思うような直線を書くアルゴリズムが見つからないため質問です。

ブレゼンハムのアルゴリズムという直線を書くアルゴリズムでは鉄板のアルゴリズムがあるのですが、
ブレゼンハムのアルゴリズムを使うと、以下の画像のように線が通っているピクセル(座標(0,1)と(2,2))を描画できません。

始点が(0,0)、終点が(2,3)の線(左上の座標を(0,0)とする)
イメージ説明

つまり、始点が(0,0)、終点が(2,3)として線を引く場合、座標(0,1)と(2,2)を線が通るため、下の画像のように描画したいと考えています。
イメージ説明

かなり初歩的な、基礎的なレンダリングなので、オーソドックスなアルゴリズムがあると思うのですが、ご存知の方よろしくお願い致します。

atata0319👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

最初にちょっと余談です

基礎的なレンダリングなので、オーソドックスなアルゴリズムがある

とのことですが「基礎的なレンダリング」であるとは必ずしも言えない気がします。お望みの線分は方向によって見た目の線の太さが変わってしまいます多くの場合より太い線分が描画されてしまいます。特徴として

(A) 本来の線分が通過する画素は必ずプロットする
(B) 線分の太さをなるべく細くする

という背反する要件のうち通常は(B)の方が重視される気がするのです・・・自信はないですが。


それはともかく・・・残念ながら自分は(A)の要件を満たすアルゴリズムとしてポピュラーなものがあるかどうか知りません。しかしながらこれはプレゼンハムのアルゴリズムの考え方をそのまま踏襲して若干手を入れればできそうな気もします。

ご質問の線分の例でいうとx方向の差分が2, y方向の差分が3なのでy座標を1ずつずらしながらx座標を1増やすかどうかその都度判断しますね?プレゼンハムのアルゴリズム(の改良版かな?)の要点はこのずらすかどうかの判定を微分法の素朴なシミュレーションによりデジタル的に行う点です。複雑さを避けるため条件つきの限定的なアルゴリズムを書くと・・・

C

1// 始点の座標はx0, y0, 終点はx1, y1とする 2// 簡単のため 3// xの増加方向は右, yの増加方向は下(コンピューターグラフィックでおなじみの座標系) 4// 始点から見た終点は右下にありyの変化量がxの変化量より大きい前提 5int dx = x1 - x0; // 前提により必ず正の値 6int dy = y1 - y0; // 前提により必ず正の値 7int x = x0; 8int y = y0; 9int delta_x_mid = dy / 2; // 最初のコードではdx/2としてましたがこちらが適切だと思います 10int delta_x = delta_x_mid; 11for (;;) { 12 plotPixel(x, y); 13 // ---- ここに挿入 ---- 14 if (y == y1) break; 15 y++; 16 delta_x += dx; 17 if (delta_x >= dy) { 18 delta_x -= dy; 19 x++; 20 } 21}

こんな感じですね。ここでdelta_xの意味を考えてみると、一つの画素の幅が(便宜上)~~dx(間違えました!)~~dyだとしたときの本来の線分がそのy座標でのxの本来の座標を近似する値といえます。つまり

text

1 +-----+ +-----+ +-----+ 2 | | | | | | 3 * | | * | | * 4 | | | | | | 5 +-----+ +-----+ +-----+ 6delta_x 0 dy/2 dy-1

図の*が本来の線分が通過する点のあたりとみなせるということです。この意味にさえ気づけば上記のコードの「ここに挿入」とコメントした位置にこんな処理を追加すればそれっぽい線分(※)がプロットできると思います。

C

1 ... 2 plotPixel(x, y); 3 // ---- 挿入コード(ここから) ---- 4 if (delta_x < delta_x_mid) { 5 plotPixel(x - 1, y); 6 } else if (delta_x > delta_x_mid) { 7 plotPixel(x + 1, y); 8 } 9 // ---- 挿入コード(ここまで) ---- 10 if (y == y1) break; 11 ...

試しにやってみたところこんな感じになりました。

イメージ説明

※: 「それっぽい」なんてアバウトな言い方をしましたがそれは「厳密に検証してないのでひょっとしたら本来の線分が通過する画素をプロットしそこねる場合もあるかも知れない」と思ったからです。すみませんが少々面倒だったので検証を省いちゃいました。不備があったらすみません。一つのアイデアとしてみていただければと思います。

==>追記:傾きを変えて複数の線分の描画を観察してみたところ、案の定、要件を満たさないかも知れないケース(実行例の図の左から2番目の線分)があることに気づきました。
これが許容できるならよいのですが、まずいならもっと境界条件等を慎重に検討する必要がありそうです。修正方法がわかったら回答へ反映したいと思いますが・・・思いつかないかも知れません。その時はゴメンナサイ


追記2:
あまりきれいとは言えないかもしれませんが、一応前述の問題をクリアできそうなコードを挙げておきます。
追記3:
何度もすみませんが、さらに間違いに気づいたので追記2のコードを訂正します。追記2のコードでは(0,0)->(1,5)などの線分を描画すると余計な画素までプロットされてしまってました orz

C

1int dx = (x1 - x0) * 2; // 必ず2で割り切れるようにする 2int dy = (y1 - y0) * 2; // 同上 3int x = x0; 4int y = y0; 5int delta_x_mid = dy / 2; 6int delta_x = delta_x_mid; 7for (;;) { 8 plotPixel(x, y); // ... この画素を「主画素」ということにします 9 if (y == y1) break; 10 if (y != y0) { 11 // y0 < y < y1であるような点でのみ左右の画素を追加すべきか判定 12 if (delta_x < delta_x_mid) { 13 // yが0.5だけ小さい位置のx座標を吟味し主画素の左に追加すべきか判定 14 if (delta_x - dx / 2 < 0) { //追記2では!=0となっていました。 15 plotPixel(x - 1, y); 16 } 17 } else if (delta_x > delta_x_mid) { 18 // yが0.5だけ大きい位置のx座標を吟味し主画素の右に追加すべきか判定 19 if (delta_x + dx / 2 > dy) { //追記2では!=dyとなっていました 20 plotPixel(x + 1, y); 21 } 22 } 23 } 24 y++; 25 delta_x += dx; 26 if (delta_x >= dy) { 27 delta_x -= dy; 28 x++; 29 } 30}

イメージ説明

投稿2018/09/30 16:10

編集2018/10/01 05:04
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/10/01 14:59

ソースコードまでありがとうございます。 おっしゃる通りで、他の方の回答を見るとオーソドックスなものはなさそうな感じがします。 実際に動かしてみたところいい感じになりました。ありがとうございます。 参考にさせていただきます。
KSwordOfHaste

2018/10/01 17:59 編集

プレゼンハムのアルゴリズムって初めて見たときは考え方がすぐにピンとくるとは限らないと思います。自分が初めてこの手のものに触れたとき意味を把握するのにかなり考え込んだ覚えがあります。こうしたものは多少苦労しても「なぜ動くのか」や「他の考え方とどこが違うか」なんてことを考えるとよいと思います。そうすれば理解が深まりますしそれだけ応用も利くようになると思います。
guest

0

ベストアンサー

A Fast Voxel Traversal Algorithm for Ray Tracing という直線が通るピクセルを見つける方法について記載がある論文を見つけたので実装してみました。
引用数が 868 件だったので、それなりに信用できるかと思います。
一応試した限りでは、すべてのピクセルが埋められているようです。

仕組みについて一部理解できていない部分があるので、わかったら追記しますね。

アルゴリズム部分

ピクセル (x1, y1) と ピクセル (x2, y2) が通るピクセルの一覧を返す。

python

1import numpy as np 2 3def calc_points(x1, y1, x2, y2, ax): 4 '''ピクセル (x1, y1) と ピクセル (x2, y2) が通るピクセルの一覧を返す 5 ''' 6 points = [] 7 8 # ピクセル座標を実2次元座標に変換する。 9 # 例: ピクセル (1, 1) から (3, 2) へ線を引く場合、実2次元座標で点 (1.5, 1.5) から 10 # (3.5, 2.5) を結ぶ線とする。 11 x1, y1 = x1 + 0.5, y1 + 0.5 # ピクセルの中心 12 x2, y2 = x2 + 0.5, y2 + 0.5 # ピクセルの中心 13 14 # 初期化 15 x, y = x1, y1 16 cell_w, cell_h = 1, 1 # セルの大きさ、今回はピクセルなので (1, 1) 17 step_x = np.sign(x2 - x1) # (x1, y1) から (x2, y2) へ進むときの x 方向のステップ数 18 step_y = np.sign(y2 - y1) # (x1, y1) から (x2, y2) へ進むときの y 方向のステップ数 19 delta_x = cell_w / abs(x2 - x1) 20 delta_y = cell_h / abs(y2 - y1) 21 # a / b % 1 は a / b の計算値の小数部分 (例: 3 / 2 % 1 = 1.5 % 1 = 0.5) 22 max_x = delta_x * (x1 / cell_w % 1) 23 max_y = delta_y * (y1 / cell_h % 1) 24 25 points.append([x, y]) # 開始点 26 reached_x, reached_y = False, False # 到達判定用フラグ 27 while not (reached_x and reached_y): 28 if max_x < max_y: 29 max_x += delta_x 30 x += step_x 31 else: 32 max_y += delta_y 33 y += step_y 34 35 points.append([x, y]) # 点を追加 36 37 # 終点に到達したかどうか 38 if (step_x > 0 and x >= x2) or (step_x <= 0 and x <= x2): 39 reached_x = True 40 if (step_y > 0 and y >= y2) or (step_y <= 0 and y <= y2): 41 reached_y = True 42 43 return np.array(points).astype(int)

描画結果

python

1 2# 白紙の画像を作成する。 3img = np.full((10, 10, 3), 255, dtype=np.uint8) 4 5# 点が通るピクセル一覧を計算する。 6x1, y1 = 8, 5 7x2, y2 = 1, 1 8 9# 点を計算する。 10points = calc_points(x1, y1, x2, y2, ax) 11print(points) 12for x, y in points: 13 img[y, x] = [255, 0, 0] # 赤 14 15# 描画部分 16################################################## 17import matplotlib.pyplot as plt 18from matplotlib.lines import Line2D 19fig, ax = plt.subplots(figsize=(8, 8), facecolor='w') 20 21# 画像を表示する。 22ax.imshow(img, interpolation='none') 23# 線を描画する。 24ax.add_line(Line2D([x1, x2], [y1, y2], color='g')) 25# グリッド 26ax.grid(which='minor', color='b', linestyle='-', linewidth=1) 27# x、y 軸の目盛りのラベル 28ax.set_xticks(np.arange(0, 10, 1)) 29ax.set_yticks(np.arange(0, 10, 1)) 30ax.set_xticklabels(np.arange(10)) 31ax.set_yticklabels(np.arange(10)) 32# x、y 軸の目盛りの位置 33ax.set_xticks(np.arange(-.5, 10, 1), minor=True) 34ax.set_yticks(np.arange(-.5, 10, 1), minor=True) 35plt.show()

イメージ説明

投稿2018/09/30 19:29

編集2018/10/01 08:51
tiitoi

総合スコア21956

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/09/30 21:35

事後報告で申し訳ありませんが描画部分コード拝借させて頂きました。 ありがとうございます。
退会済みユーザー

退会済みユーザー

2018/10/01 14:59

ソースコードもありがとうございます。とてもわかりやすいです。論文から探すというのは盲点でした。 ループの部分も処理が軽そうでかなり実用的そうです。参考にさせていただきます。
guest

0

線分の上に点が載っているか判定する

判定部分は上記から引用し改修しました。
描画部分は@tiitoiさんコードから引用し改修しました。
上記参考コードをそのまま移植するだけでは判定出来ませんでした。
試行錯誤したところ、判定条件式 a * p.x + b * p.y + c == 0 から下記のように変更することで欲しい結果が得られました。
@tiitoiさんの回答にある論文はさっぱり分かりませんが、引用したコードの条件式を手探りで発見し要件を満たす結果が得られたことはとても満足しています。
@tiitoiさんの描画部分のコードのおかげで試行錯誤とテストが捗りとても感謝しています。

変更した判定条件式

chk = a * p.x + b * p.y + c len_x = e.x - s.x len_y = e.y - s.y if len_x == len_y: v = 0 else: v = len_x // 2 + len_y // 2 if chk >= v * -1 and chk <= v: return True else: return False

イメージ説明

Python3

1import sys 2import numpy as np 3print(sys.version) 4 5class Point_(): 6 7 def __init__(self, x_init, y_init): 8 self.x = x_init 9 self.y = y_init 10 11 12def chk(s, e, p): 13 if s.x <= p.x and p.x <= e.x: 14 if s.y <= e.y \ 15 and (s.y <= p.y and p.y <= e.y) \ 16 or s.y >= e.y \ 17 and (s.y >= p.y \ 18 and p.y >= e.y) \ 19 : 20 a = e.y - s.y 21 b = s.x - e.x 22 c = s.x * (s.y - e.y) - s.y * (s.x - e.x) 23 24 #以下判定条件式を追加改修 25 chk = a * p.x + b * p.y + c 26 27 len_x = e.x - s.x 28 len_y = e.y - s.y 29 if len_x == len_y: 30 v = 0 31 else: 32 v = len_x // 2 + len_y // 2 33 34 if chk >= v * -1 and chk <= v: 35 return True 36 else: 37 return False 38 #追加改修以上 39 40# 描画部分は@tiitoiさんコードから引用しコードに合わせて改修 41import matplotlib.pyplot as plt 42from matplotlib.lines import Line2D 43 44def show_image(ax, img): 45 ax.imshow(img, interpolation='none') 46 ax.grid(which='minor', color='b', linestyle='-', linewidth=1) 47 # Major ticks 48 ax.set_xticks(np.arange(0, 10, 1)) 49 ax.set_yticks(np.arange(0, 10, 1)) 50 # Labels for major ticks 51 ax.set_xticklabels(np.arange(10)) 52 ax.set_yticklabels(np.arange(10)) 53 # Minor ticks 54 ax.set_xticks(np.arange(-.5, 10, 1), minor=True) 55 ax.set_yticks(np.arange(-.5, 10, 1), minor=True) 56 57def draw_line(img, p1, p2, color=[255, 0, 0]): 58 x1, y1 = p1 59 x2, y2 = p2 60 61 slope = (y2 - y1) / (x2 - x1) 62 63 xs = np.arange(x1, x2 + 1, 0.01) 64 ys = y1 + slope * (xs - x1) 65 pts = np.vstack([xs, ys]).T 66 print(pts.shape) 67 68 pts = np.ceil(pts).astype(int) # 離散化する。 69 pts = np.unique(pts, axis=0) # 重複する点を削除 70 71# 座標入力 72s = Point_(1, 2) 73e = Point_(8, 7) 74 75print(f'直線({s.x},{s.y})-({e.x},{e.y})') 76points = [] 77for p_x in range(s.x,e.x+1,1): 78 for p_y in range(s.y,e.y+1,1): 79 p = Point_(p_x, p_y) 80 ret = chk(s,e,p) 81 if ret: 82 points.append([p_x,p_y]) 83 84points = np.array(points) 85 86# 白紙の画像を作成する。 87img = np.full((10, 10, 3), 255, dtype=np.uint8) 88 89for x, y in points: 90 img[y, x] = [255, 0, 0] # 赤 91 92fig, ax = plt.subplots(figsize=(8, 8), facecolor='w') 93ax.add_line(Line2D([s.x, e.x], [s.y, e.y], color='g')) 94show_image(ax, img) 95# plt.savefig('test.png')

GitHub

投稿2018/09/30 16:00

編集2018/09/30 21:45
opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/10/01 14:58

ソースコードまでありがとうございます。貼ってくださったサイトも含めて参考にさせていただきます。
guest

0

直感的に解りやすい画素の判定方法はこんなでしょうか?
(下記コードは圧倒的全探索ですが……
ブレゼンハム的に,見るべきところだけを見るようにすればまぁ……)

void Plot( int x, int y ) { std::cout << x << ", " << y << std::endl; } //inner product inline int IP( int nx, int ny, int px, int py ) { return nx*px + ny*py; } //main int main(void) { //線分:(sx,sy) - ( ex,ey ) int sx = 1; int sy = 2; int ex = 8; int ey = 7; //-----処理----- //線分の法線 int ny = ex - sx; int nx = -(ey - sy); int sx2 = sx*2; int sy2 = sy*2; int ex2 = ex*2; int ey2 = ey*2; for( int y2=sy2; y2<=ey2; y2+=2 ) { int t = y2 - sy2 - 1; int b = y2 - sy2 + 1; for( int x2=sx2; x2<=ex2; x2+=2 ) { int l = x2 - sx2 - 1; int r = x2 - sx2 + 1; if(//判定 ( IP( nx,ny, l,t ) * IP( nx,ny, r,b ) < 0 ) || ( IP( nx,ny, r,t ) * IP( nx,ny, l,b ) < 0 ) ) { Plot( x2>>1, y2>>1 ); } } } return 0; }

投稿2018/10/01 02:04

編集2018/10/01 02:06
fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/10/01 14:59

ソースコードまでありがとうございます。 直感的にわかりやすいです。参考にさせていただきます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問