トップページ⇒tech
61コメント24KB

滑らかな曲線

■ このスレッドは過去ログ倉庫に格納されています
0001OPPNGNG
滑らかな曲線を描くプログラムを作成したくて、いろいろ資料をさがしているのですが
なかなかいいところがありません。
具体的には、任意の３点をすべて通過する曲線を描きたいのですが。
調べたところ、スプライン曲線、エルミート曲線等が該当するようですが、細かい
理論が書いてある資料が見当たりません。
どこかいいホームページや、くわしいひといませんか？
　￣￣￣￣∨￣￣￣￣
　　　　　 ∧,,∧　　　　　　　　　　(´´
　　 ＼,,,,ミ,,ﾟДﾟ彡　　　　　　(´⌒(´
　　⊂,,,,,,,,,つつ.≡≡≡(´⌒;;;≡≡≡
　　　　　　　　　　 (´⌒(´⌒;;
　　　　　　ｽﾞｻﾞｰｰｰｰｰｯ
0002デフォルトの名無しさんNGNG
3次方程式を使いなさい。

p[a], p[b], p[c] を通過するものとする。

p[a] での目標微分値を p'[a] とする。
p[c] での目標微分値を p'[c] とする。

以下の全ての条件を満たす三次方程式

f(x) = Ax^3 + Bx^2 + Cx + D の各係数を求めればよい。

f(a) = p[a]
f(b) = p[b]
f(c) = p[c]
f'(a) = p'[a]
f'(c) = p'[c]
0003デフォルトの名無しさんNGNG
　　　　　　　 　　 　　/ ） ／￣￣￣￣￣￣￣
　　　　　　　 　　　 ./ /　|　　宇治社中は
　　　　　　　　　　 / /　　＼　　　　　　　　　 ／￣￣￣
　　　　　　 　　　 / /　　　　￣|／￣￣￣￣|　どうですか？
　　　　　　　　　./ /＿Λ　　　　　, -つ　　　＼
　　　　　　　 　/ / ´Д｀）　 .／__ノ　　　　　　　￣∨￣￣￣￣
　　　　　　　　/　　　　＼　／ /　　 ⊂_ヽ､
　　　　　　　 .|　　　　へ／ ／　　　　　　.＼＼　Λ＿Λ
　　　　　　　 |　　　　ﾚ'　 /､二つ　　　　 　 ＼ （　´Д｀）
　　　　　　　 |　　　　　／.　　　　　　　　　　.　>　　⌒ヽ
　　　　　　　/　　　／　　　　　　 　　　　　　/　　　 へ ＼
　　　　　　 /　 ／　　　　　　 　 　　　　　　/　 　 /　　 ＼＼
　　　　　　/　 /　　　　　　　　　 　　　　　ﾚ　　ノ　　　　　ヽ_つ
　　　　 ／　ノ　　　　　　　　　　　　　　　/　 /
　　　_/　／　　　　　　　　　　　 　　　　/　 /|
　 ノ　／　　　　　　　　　　　　　　　　　（　（　､
⊂ -'　　　　　　　　　　　　　　　 　　　　|　 |､　＼
　　　　　　　　　　　　　　 　　　　　　.　　|　/　＼　⌒l
　　　　　　　　　　　　　　　　　　　　　　　|　|　　　）　/
　　　　　　　　　　　　　　　　　　　　　　ノ　 ）　　 し'
　　　　　　　　　　　　　　　　　　　　　(＿／

http://www.cc.rim.or.jp/~devilman/3dCoding/3dCoding.html
0004デフォルトの名無しさんNGNG
あなたひょっとして伝説のプログラマー小熊ちゃん？
0005OPPNGNG
>>2

かかれている条件式の3つ目まではわかるのですが、
下の2つがはっきりわかりません。

始点と終点の微分係数が曲線の方程式の微分値に
それぞれの値を代入したものと等しいというのは
わかるのですが、始点と終点の微分係数って
どのように求めるのでしょうか。

p'[a]やp'[c]のことです。
0006デフォルトの名無しさんNGNG
ほらよ
http://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm#SPL1
0007OPPNGNG
>>3
宇治社中もみましたが、もう少し理論的に踏み込んだところまで
見てみたかったのです。

あと、八頭身キモイです。
0008デフォルトの名無しさんNGNG
――――――――――――――――――――――――
こんなのどうよ
http://infoshako.sk.tsukuba.ac.jp/~tohyama/graph/bspl.html！
＿＿　 ＿＿ .ｒ――――――――――――――――――
　 　 ∨　　　｜　そんなことより>>1は進行方向が逆だもな
日　凸　Ⅱ　｜　＿＿＿＿＿＿
≡≡≡≡≡｜ /〃∧＿∧　　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　Ⅱ　∩　［］ ∨％（´∀｀　） ＜　　滑らかな曲線的移動のために制動
＿_ ∧ ∧＿_∧＿∧＿＿_）_　＼　をかけているんでしょう。
　　( 　　,,)日（　 　　.）□　　　　　＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿
― / 　 | ― （　 　　 ）―――
＼(＿_.ﾉ　 　 ━┳━)
　━┳━ 　 └ ┃―･゛
￣　┻ ￣￣￣ ┻￣￣￣
0009デフォルトの名無しさんNGNG
>>1
細かい資料が見つからん? ウソつけ。
googleで "spline curve fitting" を検索するだけでも
山のように見つかるだろうが。
プログラムの前に英語を勉強しろ。ヴォケが。
0010デフォルトの名無しさんNGNG
というか

＞任意の３点をすべて通過する曲線

平面上で３点を通る、もっとも滑らかなのは円じゃ　ボケ！
0011デフォルトの名無しさんNGNG
結論　１は円を描け

------------------- 終了 -----------------
0012　NGNG
------------------- 再開 -----------------

>>1は連続した点のうちの任意の3点を滑らかに繋ぎたいのでは？
円だと他の点に滑らかに繋げられないと思われ。
0013デフォルトの名無しさんNGNG
連続した任意の３点から滑らかに接続するのは無理でしょう
連続した任意の４点を与えるならば
>>2 >>6 およびリンク先の混合スプラインや雲形定規スプラインが使えます

という事でやはり無理

-------------------　終了 ---------------------
0014デフォルトの名無しさんNGNG
10ｶｯｺｲｲ！
0015デフォルトの名無しさんNGNG
>>平面上で３点を通る、もっとも滑らかなのは円じゃ　ボケ！
円になるとは限りませんが。
0016デフォルトの名無しさんNGNG
>>15 Are you 厨?
0017デフォルトの名無しさんNGNG
>>10
じゃ、直線上にある3点をとおる円を描いてみろ。
0018デフォルトの名無しさんNGNG
直線は半径無限大の円じゃ　ボケ
0019デフォルトの名無しさんNGNG
>>18
じゃ、まずその仮定を説明してからいわんかい ボケ
0020デフォルトの名無しさんNGNG
そういうのは暗黙の了解ちゅうんじゃ
　しょうもない事で　ごちゃごちゃヌカスなボケ
0021デフォルトの名無しさんNGNG
設問１：　３点を通る最低曲率が最大になる曲線は曲率半径が一定となるや否や
設問２：　曲率半径が一定の曲線は円の一部であるや否や
0022デフォルトの名無しさんNGNG
>>1
NURBSで検索してごらん
0023デフォルトの名無しさんNGNG
>>20
ﾔｯﾊﾟ ｶｯｺﾜﾙｲ
0024デフォルトの名無しさんNGNG
>>22 検索したって３点を通る最も滑らかな直線は円しなないんじゃ　ボケ

滑らかというのが曲率が連続しているという定義なら
　連続点中の任意の３点だけから滑らかに描く方法も無いんじゃ　ボケ
　曲率を接続するなら最低４点が条件じゃ　ボケ
0025デフォルトの名無しさんNGNG
君らオモロイ
0026デフォルトの名無しさんNGNG
>>25　ボケをつけいや　ボケ
002724NGNG
俺も間違うたわ　ボケ
最も滑らかな直線ってなんじゃいボケ
0028デフォルトの名無しさんNGNG
始点の曲率が既知であるという条件で３点
002924NGNG
４点の場合も４点を与えて、真中の２点間の曲線を１本描くだけですから
３点と始点の曲率を与えて始点から真中までの曲線を描く方式なら”同じ”です
0030デフォルトの名無しさんNGNG
曲率はどのように定義されますか。

｜始点の微分値－終点の微分値｜／線の長さ　ですか。
＝線が短く、始点と終点の傾きが違うほど　大きくなる
003124NGNG
ああ　またまちごうたわ・・・ほんまボケやじぶん

　曲率やのうて傾斜の場合は”同じ”やな

曲率だけやと方向がわからんから解けんのとチャウか？
0032デフォルトの名無しさんNGNG
とりあえず、関西弁きしょい ボケ
0033デフォルトの名無しさんNGNG
>32 そがーにいちだってあげるなや　ぼけ
0034デフォルトの名無しさんNGNG
ここが噂の漫才スレですか。
0035デフォルトの名無しさんNGNG
まあまあやね～。
0036召喚士NGNG
1が何をやりたいのか、いまいち分からないんだけど。
とりあえず、一番簡単なラグランジェ補間を書いてみたよ。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define DIM 2
#define NPOINT 3

void add(int rank_f, double *f, int rank_g, double *g, int *rank_fg, double *fg) {
int gtr = rank_f > rank_g ? rank_f : rank_g, lss = rank_f + rank_g - gtr, i;
double *gtr_p = rank_f == gtr ? f : g, *lss_p = gtr_p == f ? g : f;
for (i = 0; i < gtr; i++) fg[i] = gtr_p[i];
for (i = 0; i < lss; i++) fg[i] += lss_p[i];
*rank_fg = gtr;
}

void multiply(int rank_f, double *f, int rank_g, double *g, int *rank_fg, double *fg) {
int i, j; *rank_fg = rank_f + rank_g - 1; for (i = 0; i < *rank_fg; i++) fg[i] = 0;
for (i = 0; i < rank_f; i++) for (j = 0; j < rank_g; j++) fg[i + j] += f[i] * g[j];
}
0037召喚士NGNG
void lagrangian_interporation(int dim, int npoint, double *param, double *points, double *coef) {
int i, j, k, rank, npointsize = npoint * sizeof(double);
double basis[2], *a = malloc(npointsize), *b = malloc(npointsize), *c = malloc(npointsize);
double *lagrangian_basis = malloc(npoint * npointsize);
for (i = 0; i < npoint; i++) {
for (rank = 1, a[0] = 1, j = 0; j < npoint; j++) if (i != j) {
double xi = param[i], xj = param[j];
basis[1] = 1 / (xi - xj); basis[0] = -xj * basis[1];
multiply(2, basis, rank, rank % 2 ? a : b, &rank, rank % 2 ? b : a);
}
memcpy(lagrangian_basis + npoint * i, rank % 2 ? a : b, npointsize);
}
for (i = 0; i < dim; i++) {
for (rank = 0, j = 1; j < npoint; j++) {
for (k = 0; k < npoint; k++) a[k] = points[j * dim + i] * lagrangian_basis[j * npoint + k];
add(npoint, a, rank, b, &rank, c);
memcpy(b, c, npointsize);
}
for (j = 0; j < npoint; j++) coef[j * dim + i] = c[j];
}
free(a); free(b); free(c); free(lagrangian_basis);
}
0038召喚士NGNG
void interporate(int dim, int npoint, double *points, double *param, double *coef) {
int i, j; for (param[0] = 0, i = 1; i < npoint; i++) {
double distance = 0; for (j = 0; j < dim; j++) distance += points[i * dim + j] - points[i * dim - dim + j];
param[i] = param[i - 1] + sqrt(distance);
}
lagrangian_interporation(dim, npoint, param, points, coef);
}

void evaluate(double param, int dim, int rank, double *coef, double *value) {
int i, j; for (i = 0; i < dim; i++) {
for (value[i] = coef[(rank - 1) * dim + i], j = 1; j < rank; j++) {
value[i] = value[i] * param + coef[(rank - 1 - j) * dim + i];
}}}

main() {int i, j;
double points[NPOINT][DIM] = {{1,0},{3,1},{5,7}}, param[NPOINT], coef[NPOINT][DIM], value[DIM];
interporate(DIM, NPOINT, *points, param, *coef);
for (i = 0; i < NPOINT; i++) {
printf("%d : f(%g) = (", i, param[i]);
evaluate(param[i], DIM, NPOINT, *coef, value);
for (j = 0; j < DIM; j++) printf(" %g,", value[j]); printf(" )\n");
}
return 0;
}

次元と補間点の個数は、適当に変えてみてね。
0039OPPNGNG
1です。具値的にやりたいことは、３点P0,P1,P2を曲線でつなぐことです。
このときP0-P1およびP1-P2をそれぞれ曲線で結んだ場合、点P1において
曲線の連続性が保てないため、Hermite曲線やスプライン曲線を使用したいと
思ったのです。
そのとき与えられた点を通過するように描きたいため、B-SplineやNURBSもしくは
ベジェ等を用いることができなかったのです。
なぜなら、B-SplineやNURBSもしくはベジェ曲線はコントロールポイントを
通過しないためです。
0040召喚士NGNG
じゃあ、とりあえず上のプログラムで要件は満たしてますよ。
ラグランジェ曲線はコントロールポイント（？）を必ず通過しますから。
0041OPPNGNG
>>40
早速、ためしてみます。ありがとうございました。
0042召喚士NGNG
多項式ひとつで作った曲線なので、連続性は問題ないですし。
0043デフォルトの名無しさんNGNG
召喚士さんｶｺｲｲ
でもinterporateはinterpolate
0044召喚士NGNG
ちなみに、エルミート曲線やベジエ曲線でがんばってほしい曲線を作っても、
結局得られるものは、ラグランジェ曲線と同じです。
表現形式が違うだけで、数学的には同じものですから。
B-splineやNURBSだと、もっといい曲線が得られるものが作れるでしょうけど、
ゼロから作るのは、かなりとしんどい。一週間とかかかりそうで。
0045召喚士NGNG
>>43
手元に辞書がなかったの・・・
ｶｺﾜﾙｲ
0046デフォルトの名無しさんNGNG
とりあえず、以下の仕様で皆腕によりをかけてくれ。

{ Source で指定された画像を Scale 倍したものを
Dest に描画する。Dest のサイズも同時に設定される。
拡大縮小時には線形補完を用いて、そこそこ高画質にする。
Source は 24Bit カラーである事を前提とする }

function Zoom(Source,Dest:TBItmap; Scale:Extended);begin
　if Scale = 1 then
　　Dest.Assign( Source );
　　Exit;
　end;

　Dest.Width := Floor( Source.Width * Scale );
　Dest.Height := Floor( Source.Height * Scale );

　{ なんたらかんたら }

end;

もしくは、Cなどで記述してDLL化してくれてもOK
0047デフォルトの名無しさんNGNG
とりあえず、以下の仕様で皆腕によりをかけてくれ。

{ Source で指定された画像を Scale 倍したものを
Dest に描画する。Dest のサイズも同時に設定される。
拡大縮小時には線形補完を用いて、そこそこ高画質にする。
Source は 24Bit カラーである事を前提とする }

function Zoom(Source,Dest:TBItmap; Scale:Extended);begin
　if Scale = 1 then
　　Dest.Assign( Source );
　　Exit;
　end;

　Dest.Width := Floor( Source.Width * Scale );
　Dest.Height := Floor( Source.Height * Scale );

　{ なんたらかんたら }

end;

もしくは、Cなどで記述してDLL化してくれてもOK
0048召喚士NGNG
ラグランジェ補間の簡単な解説をば

パラメタ a, b, c について、以下のような変数 t の多項式 la(t) を考える。

　la(t) = (t - b)(t - c) / (a - b)(a - c)

この多項式は、t = a で 1 になり、t = b または t = c の時に 0 になる。
同様に、t = b で 1 になり、t = a or c で0になる多項式 lb(t) と、
t = c で 1 になり、t = b or c で0になる多項式 lc(t) は、

　lb(t) = (t - a)(t - c) / (b - a)(b - c)
　lc(t) = (t - a)(t - b) / (c - a)(c - b)

となる。ここで、多項式 f(t) = A * la(t) + B * lb(t) + C * lc(t) を考えると。
　f(a) = A * 1 + B * 0 + C * 0 = A
　f(b) = A * 0 + B * 1 + C * 0 = B
　f(c) = A * 0 + B * 0 + C * 1 = C
となり、t = a, b, c にて、f(t) = A, B, C を確実に満たす。
というわけで、曲線 C(t) = P0 * la(t) + P1 * lb(t) + P2 * lc(t) を考えると、
C(t) は、P0, P1, P2 を確実に通過するわけです。いじょ。
0049召喚士NGNG
×パラメタ a, b, c について、以下のような変数 t の多項式 la(t) を考える。
○定数 a, b, c について、以下のような変数 t の多項式 la(t) を考える。
0050デフォルトの名無しさんNGNG
本当にこんな式で女性の尻が表現できるのかなぁ・・・
ちょっと実験するか。
0051デフォルトの名無しさんNGNG
コントロールポイントを膨大に取れば
0052召喚士NGNG
しまった、バグがあったの

void interporate(int dim, int npoint, double *points, double *param, double *coef) {
int i, j; for (param[0] = 0, i = 1; i < npoint; i++) {
double distance_square = 0; for (j = 0; j < dim; j++) {
double diff = points[i * dim + j] - points[i * dim - dim + j]; distance_square += diff * diff;
param[i] = param[i - 1] + sqrt(distance_square);
}
lagrangian_interporation(dim, npoint, param, points, coef);
}
0053召喚士NGNG
しまった、バグがあったの

void interporate(int dim, int npoint, double *points, double *param, double *coef) {
int i, j; for (param[0] = 0, i = 1; i < npoint; i++) {
double distance_square = 0; for (j = 0; j < dim; j++) {
double diff = points[i * dim + j] - points[i * dim - dim + j]; distance_square += diff * diff;
}
param[i] = param[i - 1] + sqrt(distance_square);
}
lagrangian_interporation(dim, npoint, param, points, coef);
}
0054召喚士NGNG
#include <stdlib.h>
#include <string.h>
#include <math.h>

void add(int rank_f, double *f, int rank_g, double *g, int *rank_fg, double *fg) {
int gtr = rank_f > rank_g ? rank_f : rank_g, lss = rank_f + rank_g - gtr, i;
double *gtr_p = rank_f == gtr ? f : g, *lss_p = gtr_p == f ? g : f;
for (i = 0; i < gtr; i++) fg[i] = gtr_p[i];
for (i = 0; i < lss; i++) fg[i] += lss_p[i];
*rank_fg = gtr;
}

void mul(int rank_f, double *f, int rank_g, double *g, int *rank_fg, double *fg) {
int i, j;
*rank_fg = rank_f + rank_g - 1;
for (i = 0; i < *rank_fg; i++) fg[i] = 0;
for (i = 0; i < rank_f; i++) {
for (j = 0; j < rank_g; j++) fg[i + j] += f[i] * g[j];
}
}
0055召喚士NGNG
void lagrangian_interpolation(int dim, int npoint, double *param, double *points, double *coef) {
int i, j, k, rank, npsize = npoint * sizeof(double);
double basis[2], *a = malloc(npsize), *b = malloc(npsize), *c = malloc(npsize);
double *lagrangian_basis = malloc(npoint * npsize);
for (i = 0; i < npoint; i++) {
for (rank = 1, a[0] = 1, j = 0; j < npoint; j++) if (i != j) {
double xi = param[i], xj = param[j];
basis[1] = 1 / (xi - xj); basis[0] = -xj * basis[1];
mul(2, basis, rank, rank % 2 ? a : b, &rank, rank % 2 ? b : a);
}
memcpy(lagrangian_basis + npoint * i, rank % 2 ? a : b, npsize);
}
for (i = 0; i < dim; i++) {
for (rank = 0, j = 0; j < npoint; j++) {
for (k = 0; k < npoint; k++) {
a[k] = points[j * dim + i] * lagrangian_basis[j * npoint + k];
}
add(npoint, a, rank, b, &rank, c);
memcpy(b, c, npsize);
}
for (j = 0; j < npoint; j++) coef[j * dim + i] = c[j];
}
free(a); free(b); free(c); free(lagrangian_basis);
}
0056召喚士NGNG
void interpolate(int dim, int npoint, double *points, double *param, double *coef) {
int i, j;
for (param[0] = 0, i = 1; i < npoint; i++) {
double distance_square = 0;
for (j = 0; j < dim; j++) {
double diff = points[i * dim + j] - points[i * dim - dim + j];
distance_square += diff * diff;
}
param[i] = param[i - 1] + sqrt(distance_square);
}
lagrangian_interpolation(dim, npoint, param, points, coef);
}

void evaluate(double param, int dim, int rank, double *coef, double *value) {
int i, j;
for (i = 0; i < dim; i++) {
for (value[i] = coef[(rank - 1) * dim + i], j = 1; j < rank; j++) {
value[i] = value[i] * param + coef[(rank - 1 - j) * dim + i];
}
}
}
0057召喚士NGNG
#include <stdio.h>
#define DIM 2
#define NPOINT (sizeof points / sizeof *points)

double points[][DIM] = {
{1, 1}, {3, 1}, {5, 7},
{9, 1}, {4, 9}, {3, 6}
};

int main(void) {
int i, j;
double param[NPOINT], coef[NPOINT][DIM], value[DIM];
interpolate(DIM, NPOINT, *points, param, *coef);
for (i = 0; i < NPOINT; i++) {
printf(" (");
for (j = 0; j < DIM; j++) {
printf("%f%s", points[i][j], j - DIM + 1 ? ", " : ")\n");
}
}
for (i = 0; i < NPOINT; i++) {
printf("%d : f(%f) = (", i, param[i]);
evaluate(param[i], DIM, NPOINT, *coef, value);
for (j = 0; j < DIM; j++) {
printf("%f%s", value[j], j - DIM + 1 ? ", " : ")\n");
}
}
return 0;
}

これで動くかなあ。
0058デフォルトの名無しさんNGNG
通りすがりの者だけど、勉強になった。
ありがとぉー
0059デフォルトの名無しさんNGNG
スプライン曲線のソース。
ftp://ftp.matsusaka-u.ac.jp/pub/algorithms/src/spline.c
ftp://ftp.matsusaka-u.ac.jp/pub/algorithms/src/spline2.c

ベジエ曲線のアルゴリズム
float x1, y1, x2, y2, x3, y3; // 任意の座標点
float pos = 0; // 0～1 の区間
float p1 = ( 1 - pos ) * ( 1 - pos );
float p2 = ( 1 - pos ) * pos;
float p3 = pos * pos;
float x = p1 * x1 +p2 * x2 + p3 * x3;
float y = p1 * y1 +p2 * y2 + p3 * y3;
// ( x, y ) をプロット
0060デフォルトの名無しさんNGNG
平均移動法はどうよ？
0061デフォルトの名無しさんNGNG
なんか手で曲線描いたほうが速いや。
胸とか。
■ このスレッドは過去ログ倉庫に格納されています