Pythonで手書き曲線補間

物悲しそうにしているペンタブ君のために、手書き曲線を補間するコードを書いてあげました。

Google先生が教えてくれなかったので、仕方なく自分で考えました。僕が聞く単語間違ってるだけかもしれないですが。

まぁ、簡易的なものですけどね。




どうよ?ペンタブ君。

ペンタブ「精度悪すぎ」

(#^ω^)

追:ちなみに精度最大にすると

なんか予想と違うなーっと思ったら、実数じゃなくて、整数で計算してるからこうなってんだな。うっかりだ。



ソース
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
import Tkinter as Tk
import math
 
class FreeLine:
#precision property
target_range = 10
angle_range = 20
 
canvas = None
newBlock = True
n = 0
drawPoint = True
drawSubPoint = False
point_list = []
 
def __init__(self):
window = Tk.Tk()
self.canvas = Tk.Canvas(window, bg="white", width=512, height=384)
self.canvas.pack()
self.window = window
self.canvas.bind("<ButtonPress-1>", self.start)
self.canvas.bind("<B1-Motion>", self.writing)
self.canvas.bind("<ButtonRelease-1>", self.finish)
 
def start(self,event):
self.point_list = []
#for handline
self.sx = event.x
self.sy = event.y
#for freeline
self.point_list.append([event.x,event.y])
self.setOrigin(event.x,event.y)
 
def writing(self,event):
#drawing handline
self.canvas.create_line(self.sx, self.sy, event.x, event.y,
fill = "red", width = 1)
self.sx = event.x
self.sy = event.y
#scanning
if self.isRangeCircle(event):
return
 
if self.newBlock:
self.setTarget(event.x,event.y)
self.newBlock = False
return
 
if not self.isRangeBox(event):
self.setDestination(event.x,event.y)
self.addPoint()
self.newBlock = True
self.n += 1
self.setOrigin(event.x,event.y)
 
def finish(self,event):
self.setDestination(event.x,event.y)
self.point_list.append([event.x,event.y])
self.newBlock = True
ls = []
for p in self.point_list:
ls.append(p[0])
ls.append(p[1])
if self.drawPoint:
size = 4
self.canvas.create_oval(p[0]-size,p[1]-size,
p[0]+size,p[1]+size,
fill = "red",width=0)
if self.drawPoint:
self.canvas.create_line(ls,width=1,fill="red")
self.canvas.create_line(ls,smooth=True,width=3)
 
def setOrigin(self,x,y):
self.origin_x = x
self.origin_y = y
if self.drawSubPoint:
self.canvas.create_oval(x-3, y-3, x+3, y+3,
fill = "green", width=0)
print "set origin!",[x,y]
 
def setDestination(self,x,y):
self.dest_x = x
self.dest_y = y
if self.drawSubPoint:
self.canvas.create_oval(x-5, y-5, x+5, y+5,
fill = "orange",width=0)
print "set destination!",[x,y]
 
def setTarget(self,x,y):
self.target_x = x
self.target_y = y
if self.drawSubPoint:
self.canvas.create_rectangle(x-4, y-4, x+4, y+4,
fill = "blue",width=1)
print "set target!",[x,y]
 
def isRangeCircle(self,event):
distance = math.sqrt((event.x-self.origin_x)**2+
(event.y-self.origin_y)**2)
if distance > self.target_range:
return False
else:
return True
 
def isRangeBox(self,event):
[x1,y1,x2,y2] = [self.origin_x,self.origin_y,
self.target_x,self.target_y]
a = y1-y2
b = x2-x1
c = x1*y2-x2*y1
distance = (math.fabs(a*event.x+b*event.y+c)/
math.sqrt(a**2+b**2))
if distance > self.angle_range:
return False
else:
return True
 
def addPoint(self):
[x1,y1,x2,y2,x3,y3] = [self.origin_x,self.origin_y,
self.target_x,self.target_y,
self.dest_x ,self.dest_y ]
a = ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1))/((x2-x1)**2+(y2-y1)**2)
x = a*(x2-x1)+x1
y = a*(y2-y1)+y1
self.point_list.append([x,y])
print "add point!",self.n,"---------------"
 
 
def main():
app = FreeLine()
app.window.mainloop()
 
 
if __name__ == '__main__':
main()
 


えーと、中身はですねー。

起点(origin)、終点(destination)、ターゲット(target)の3点から、ポイントを算出します。ターゲットは起点からtarget_rangeを半径とする円の範囲外に出たときに打たれます。終点は起点とターゲットの2点を通る直線からの垂直距離がangle_range以上になった時に打たれます。
これを1ブロックとして、終点が打たれると、次の起点が同じ場所に打たれて、次のブロックになります。始めと終わりを除き、各ブロックに1つのポイントが打たれます。

で、ポイントと各点との位置関係ですが、起点、ターゲットの2点を通る直線と、終点を通る直線の垂線の交点にポイントが打たれます。意図したとおり書けているならw。


とまぁ、こんな風に考えたわけですけど、巷のアルゴリズムはどうなっているのか、まったく知らないんですよね~。どうなってんのかな。オープンソース?ソースなんて読めないよ!

これだと、180度角度変えたときなんか(というか鋭角)に対応しないわけですけど、それはおいおい。

あと変数drawPointをTrueで、ポイントとそれを結ぶ直線を表示。drawSubPointをTrueで起点、終点、ターゲットを表示します。
関連記事

コメント

こんにちは。
おおっ、かっこいいですね。私は以前VisualBasicでドローツールもどきを作ったことがあるのですが、そのときはフリーハンドツールとかは難しそうだったのでまったく手を出さずに終わりました。

今、ちょこっとInkscapeのソースファイルをのぞいて見ましたが、関係ありそうなファイルをたまたま発見できたのでご報告します。
フリーハンドツール自体のソースは
「src」フォルダのpencil-context.cppというのがそうみたいです。
その中でinterpolate()という関数がフリーハンドの処理をしているようで、さらにそのコード中でGeom::bezier_fit_cubic_r()という関数が、実際にBezier曲線のポイントを計算しているような気がします。
で、こういう場合「grep」というツールを使うと、その関数がどこにあるのか調べることができて、今回ならこんな感じで実行して...
$ grep -r bezier_fit_cubic_r *
「2geom」というフォルダの「bezier-utils.cpp」の中にその関数があることがわかりました。
そこからさらに、bezier_fit_cubic_full()という関数が再帰的に呼ばれています。
その中身はというと、ちょっと簡単にはわかりませんでした(笑)。

私も近いうちにSVG関係のコードに関わることになりそうなので、もう少し勉強したいと思っています。

こんにちは~。
自分で考えといてあれですが、正直あまり出来るとは思ってなかったので、こんな簡単なコードでそこそこ補間できることに感動しましたw。中学レベルの数学と格闘した甲斐がありました。厳密にとなると、やはり難しいのかも知れませんが。

ふむふむ。bezier_fit_cubic_fullは見つけましたが、まず引数が謎ですw。正直構造を理解しようと思うと気が遠くなりますね・・、うーん、皆さんどうやって読めるようになったんでしょうか。こんな時に頑張ってほしいVisualStudioは関数一覧の表示操作すらわからない始末。

個人的にはPythonで書かれているSkencilの中身が気になるのですが、デスクトップ環境がWindowsしかないため動作の確認ができないので、誰か解説してくれないかな~っと、あっ、独り言ですので気にしないでください(いやらしい)。


テクスチャが描けないタチなので、プラグイン楽しみにしてます。

こんばんわー。
結構いい感じですね!GreasePencilのsmoothっぽいですね~。

inkscapeの元のやつは、これのようです。
http://books.google.co.jp/books?ei=dcK8ScX4DZeSlASm3MCBDA&as_brr=3&q=An+Algorithm+for+Automatically+Fitting+Digitized+Curves&btnG=%E6%9B%B8%E7%B1%8D%E3%81%AE%E6%A4%9C%E7%B4%A2
↑高い洋書ですが、アルゴリズム、数式まで全部載ってます。自分はわざわざ図書館で読んだんですが、上で読めるところがほぼ全部でした。載ってないコード(fitcurve.c)はググれば見つかるので、あわせて読むと分かり易いです。でも、自分は流し読み程度で、まだ理解できてませんw

こんばんは。自分で考えたらこんなんなったwwwwと言う記事を書くつもりでいたのに思いのほかにw。

ぶっちゃけ、ラスタをベクタに変換するならまだしも、一から描くこと前提のドローソフトに手書き曲線なんて必要ないので、これでいいとも思ってます。角度変化に応じて、ポイントの位置をずらすとかすれば、もっと精度が上がるのかもしれませんが。

おお、これは! あとfitcurve.cありました。書籍は今のところポカーンですが、fitcurve.cがまだ読む気になるソースなのが救いですね。やっぱ巷のアルゴリズムは複雑だなぁ。

しかし、Inkscapeの手書き曲線でも、ポイントの数が多くなっちゃうし、正直使う気にはなりません^^;

こんばんは。
uimacさんは、こういう難しい本をたくさん読まれているんですね。
私は数学とか物理とか苦手な方なので、これだけの内容になると理解するのはかなり厳しいです。
プログラミングを始めてから相当の年月がたっているのに、未だに初心者レベルから抜けられないのは、このあたりのことも関係しているような気がします。

Skencilを少さわってみました。
ただ、公式サイトの最新ニュースが2006年3月ということもあってか、Ubuntuの最新版ではうまく動かず、一つ前の8.04で試してみました。
まず、フリーハンドツールに相当する機能についてですが、付いていないようでした。
それほど細かく見てはいないのですが、全体的にかなり基本的な機能だけに絞られている感じがしました。
ただ、私がCorelDrawなどでよく使っているBlendツールの機能については、InkscapeよりもSkencilの方が使いやすく感じました。

ちなみに、DevelopmentのページにWindows版があるようですが、Pythonのバージョンなどを2.3とかに合わせないといけないようで、きちんと動くようにするのは大変かもしれません。

こんばんは。出来る人は出来るだけの下積みがありますよね~。
僕はとにもかくにも作れば最小勉強量で身につくだろっと下積みそっちのけです。煮詰まってます。

Skencilの感想どうもです。いやらしい頼み方してすみません。Python標準ってことでTkinter使ってますが、重いのが気になってるもので、Tkinterでは仕方が無いのか、無駄処理が多いのかってことが見たいんですね。
あれ、フリーハンドなかったですか。Skencilのソースである的な記述をどこかで見たことがあるような気がしたのですが、申し訳ない。

Windows版はGTK関係が合わなくて断念した覚えがあります。当時は元々ライブラリを入れてませんでしたが、今更全部バーション入れ替えてってのも億劫ですね・・。

こんばんは。
Skencilが重いかどうかという点については、何も書いていなかったですね。すみません。
Skencilは画面の表示にアンチエイリアスがかかっていないので、その部分で処理が軽くなっているのかもしれませんが、普通に使う分には速度については気になりませんでした。
複雑な形状を扱っているときにどうなるかSVGファイルを読み込んで試そうとしたのですが、PythonのXMLモジュールのバージョンの問題でできませんでした。
XMLでなければOKということで、Vectexについていたtiger.svgをInkscapeでAdobe Illustrator形式で保存したら、問題なく読み込めました。
tiger.svg程度のデータでは重く感じることはまったくなくて、編集なども普通にできる感じです。

前のコメントで書いたブレンド機能についてVimeoの動画を作ってみました。
これをみても動作が重いかどうかはちょっとわからないかもしれませんが、よろしければ見てみてください。
http://vimeo.com/3693905

どうも~。詳細をありがとうございます。

やっぱそんなに重くないですか。じゃないとわざわざTkinterで作らないだろうとは思っていたんですが。一部にCが使われているらしいですが、フィルター関係でしょうね。となると、やはり無駄処理が多いのかorz。

ウィジットのメソッドをほとんど使わず、消してつけてを繰り返させて動かしているので、その辺かな~、っと言っても最適化なんて出来ないわけですけど^^;
既に色々と問題に見舞われているんですが、書きやすさを優先してこのまま行きます。

Vimeoはどうもプライベートモードとやらになっているようです。

すみません。
前にアップロードしたときは普通に公開されていたのに、いつのまにか非公開にしてました。
設定を変更したので、普通に見られるようになったと思います。
大変、失礼いたしました。

見れました。ありがとうございます。

むむ、Skencilあなどりがたし。Blendって色ごとの線を引いてるのかなぁ。だとすると結構な繰り返し処理をしてるはずですが、全然実用範囲ですね。改めて自分の塗りつぶし処理の稚拙さを痛感しましたw

コメントの投稿

非公開コメント

このブログについて
□ ブログ内容
決まった趣旨はありません。
興味を持ったこと・日常で行ったことを何でも書きます。

3DCG・プログラミングなどが多めです。

□ 現在の活動
・ウェブサイト制作
 (http://tiblab.net)
・3Dゲーム制作
 (コックパニック)
検索フォーム
ユーザータグ

Blender キャプチャ blendファイル BGE Python GameEngine ムービー Android CG  Red5 Terragen C# C++ 

カテゴリー
プロフィール

TiBra

Author:TiBra
趣味でCG制作、プログラミング等を行っています。メイカーズに憧れています。

ネットを通じた交流を広げたく思っていますので、コメント・メールはお気軽にどぞー

戯言程度のことは、こちらのブログに投稿しています。基本戯言なので、実質移転しているようなものです。

Mail:tibraあっとlive.jp
HP:TibLabmemocode
動画:VimeoFC2動画ニコニコ
ファイル:SkyDrive
企画:3Dゲーム作業実況

Blogリンク
不都合がございましたらご連絡ください。
当ブログのリンクバナー
FC2 ID
FC2カウンター
RSSフィード+解析コード