0

私はしばらくの間この問題に取り組んできましたが、これまでのところ良い解決策を思い付くことができませんでした。

問題:3つ(またはそれ以上)の2Dポイントの順序付きリストがあり、「見栄えがする」ように、3次ベジェ曲線でこれらをストロークしたいと思います。「見栄えが良い」部分は非常に単純です。2番目のポイントのウェッジを滑らかにしたいだけです(たとえば、カーブがそれ自体でダブルバックしないようにします)。したがって、3つのポイントが与えられた場合、曲線を描くときにトリプレットの2番目のポイントを囲む2つのコントロールポイントをどこに配置する必要があります。

これまでの私の解決策は次のとおりですが、不完全です。このアイデアは、私が求めている外観を伝えるのにも役立つかもしれません。

(x1、y1)、(x2、y2)、(x3、y3)の3つのポイントが与えられます。ポイントの各トリプレットによって内接する円を取ります(それらが同一線上にある場合は、それらの間に直線を引いて先に進みます)。点(x2、y2)でこの円に接する線を取ります-この接線上に(x2、y2)を囲む制御点を配置します。

それは私が立ち往生している最後の部分です。私が抱えている問題は、この接線上に2つの制御点を配置する方法を見つけることです。この線上の(x2、y2)からどれだけ離れているかについては、十分なヒューリスティックがありますが、もちろん、その距離にあるこの線上の2つのポイント。「間違った」方向のものを計算すると、曲線はそれ自体でループします。

3つのポイントで表される円の中心を見つけるには(いずれかのポイントのx値が同じ場合は、以下の計算でポイントを並べ替えるだけです)。

double ma = (point2.y - point1.y) / (point2.x - point1.x);
double mb = (point3.y - point2.y) / (point3.x - point2.x);
CGPoint c; // Center of a circle passing through all three points.
c.x = (((ma * mb * (point1.y - point3.y)) + (mb * (point1.x + point2.x)) - (ma * (point2.x + point3.x))) / (2 * (mb - ma)));
c.y = (((-1 / ma) * (c.x - ((point1.x + point2.x) / 2))) + ((point1.y + point2.y) / 2));

次に、接線上の点を見つけるために、この場合は、point2からpoint3に向かう曲線の制御点を見つけます。

double d = ...; // distance we want the point. Based on the distance between
                // point2 and point3.
// mc: Slope of the line perpendicular to the line between
// point2 and c.
double mc = - (c.x - point2.x) / (c.y - point2.y);
CGPoint tp; // point on the tangent line
double c = point2.y - mc * point2.x; // c == y intercept
tp.x = ???; // can't figure this out, the question is whether it should be
            // less than point2.x, or greater than?
tp.y = mc * tp.x + c;
// then, compute a point cp that is distance d from point2 going in the direction
// of tp.
4

2 に答える 2

0

ポイントが接線に沿ってどれだけ離れているかを選択する良い方法があり、それぞれを配置する側を決定するだけでよいと本当に確信している場合は、もう一度それを確認することをお勧めします線が接する円。円上にz1、z2、z3の順序であります。z2からz1に向かって円を一周することを想像しますが、代わりに接線に沿って進みます。これが、「z2の前」のコントロールポイントのどちら側にあるべきかです。「z2の後」のコントロールポイントは反対側にある必要があります。

これにより、常に2つのコントロールポイントがz2の反対側に配置されることが保証されます。これは重要です。(また、おそらくz2から同じ距離にする必要があります。そうしないと、曲線の2次導関数であるz2で不連続性が発生し、少し最適ではないように見える可能性があります。)まだ病的なケースです。

コードの複雑さをかなり気にしない場合は、Don KnuthのMETAFONTプログラム(主な目的はフォントの描画)に、問題(およびそれ以上)に対応する洗練された非常に効果的なアルゴリズムがあります。アルゴリズムはジョンホビーによるものです。詳細な説明と動作するコードは、METAFONT、またはおそらくより適切に関連するMETAPOST(巨大なビットマップの代わりにPostScript出力を生成する)にあります。

ただし、METAFONTとMETAPOSTは「リテラシープログラム」であるため、少し注意が必要です。つまり、それらのソースコードとドキュメントは、Pascalコード(METAFONTの場合)またはCコード(METAPOSTの場合)とTeXマークアップ。これを美しく植字された文書に変えるプログラムがありますが、私が知る限り、誰もその結果をWebのどこにも掲載していません。したがって、ソースコードへのリンクは次のとおりです。完全に理解できない場合もあれば、そうでない場合もあります。http: //foundry.supelec.fr/gf/project/metapost/scmsvn/? action=browse&path=%2Ftrunk%2Fsource%2Ftexk%2Fweb2c %2Fmplibdir%2Fmp.w&view=markup-ここで「コントロールポイントの選択」を検索する必要があります。

(METAFONTの美しく植字されたドキュメントは、「METAFONT:the program」というタイトルで適切に製本された本として入手できます。ただし、実際の費用がかかり、コードはPascalにあります。)

于 2011-02-06T02:21:24.190 に答える
0

曲線が二重に戻らないように接点を設定するには、曲線が進む方向を把握する必要があるようです。私が理解していることから、それは単純にから(x1, y1)への方向を見つけ(x2, y2)、次にその方向に最も近い方向にヒューリスティックな距離を接線上を移動し、(x1, y1) -> (x2, y2)そこに接点を配置することです。

于 2010-09-22T17:22:32.577 に答える