閉曲線の凹みの判定法

質問

座標の列(x1,y1),(x2,y2),...,(xn,yn)で与えられる、各点が次の点と接続する閉曲線があります（(xn,yn)は(x1,y1)に接続します）。

この曲線のどこかに凹みがあるかどうかを判定するにはどうしたらよいのでしょうか？

回答No.2

springside · ベストアンサー

ちょっと面倒ですが、「ベクトルの回転」を考え、その「回転角」から判定できるのではないでしょうか。

今、点(xk,yk)を点Pkとします。
PkからPk+1へ行く矢印をベクトルakとします。
（ただし、ベクトルanは、PnからP1へ行くベクトル）

ベクトルa1,a2,a3,・・・は長さが違うので、同じ長さにするために、各ベクトルのx成分とy成分を、そのベクトルの大きさ√(xk^2+yk^2)で割って、長さを１に揃えます。
そのようにして長さが１に揃ったベクトルをbkとします。

bk+1は「bkを角度θ回転させたもの」とすれば、原点中心のθk回転（１次変換）を表す行列Akを用いて、

bk+1 = Ak・bk・・・※

と書けます。

ただし、
　　cosθk　　-sinθk
A =
　　sinθk　　cosθk
です（行列を表す括弧は省略しました）。

さて、※を成分に分解すると、sinθk、cosθkを変数とする連立方程式になりますので、これを解いてsinθkを求めます。
以上により、sinθ1、sinθ2、sinθ3、・・・というふうにn個のsinが求まりますが、
　・その符号が全部同じであれば、凹みなし
　・符号の中にプラスとマイナスが混在すれば凹みあり
ということになると考えられます。

以上は、常に同じ方向に回転しているか、逆回転が混在しているか、ということから判定しています。

計算は面倒ですが、コンピュータでやればすぐにできると思います。

お礼

ご回答ありがとうございます。

方針はだいたい分かるような気がするのですが、連立方程式を解かなくてはならないでしょうか。

ベクトルakに対し、Pk+2がその右側か左側かを判定するという操作をk=1,2,3...について行い、符合が混在すれば凹みが存在すると考えていいわけですね。

ベクトルakのX成分をxak、Y成分をyakで表すと、Pk+2の右側、左側は xak * yak+1 - xak+1 * yak で判定できそうな気がしますが、これでいいのでしょうか…。

回答No.5

stomachman

三角関数を使いたくない、なるべく速く計算したい、頂点の数は多い、という条件を入れるんですね。
No.4の第一の方法は、実際に回転を計算しないでも、一次不等式として扱えばできそうです。ただ、この方法は頂点の個数の二乗に比例する手間が掛かるのが難点です。

No.4の第二の方法も実際に回転を計算しないで、二つのベクトル(p→qとq→r）の外積の符号を見れば良いでしょう。（三点が直線上に並ぶという場合の扱いをきちんと検討する必要がありそうですが。）この方法の手間はnに比例するから速い。
ただ、ひとつ問題があって、多角形Aの辺が自分自身と交差している場合（NTTのロゴマークのような形のとき）に、Aを凸多角形だと判定してしまう可能性があります。

●さらに別の方法として、
隣り合っていない頂点の中点をひとつ選んでｍとします。mと各頂点を結ぶ補助線を引いて、多角形Aを三角形に分割して、それぞれの面積を計算するんです。（面積は外積で計算します。）
隣り合う頂点p,q,rについて、
｜(三角形pmqの面積)｜+｜(三角形qmrの面積)｜<｜(三角形pmrの面積)｜
であれば、頂点qは凹んでいる、と分かります。
同時に、面積の符号をチェックします。面積の符号が三角形によって異なる場合があれば、それは多角形Aの辺が自分自身と交差しているか、あるいはmがAの外にあることを意味します。
多角形Aの辺が自分自身と交差していれば、これは凸多角形ではない。
２頂点の中点であるmがAの外にあるなら、やはりこれは凸多角形ではない。
手間はnに比例です。

外積については、たとえばhttp://yosshy.sansu.org/gaiseki.htm

お礼

ほぼ解決したと思います。ありがとうございました。

回答No.4

stomachman

頂点の列が与えられたとき、それが凸多角形(convex)であるかどうかを判定する、という問題のようです。
　「Aが凸多角形である」とは「Aに含まれる任意の２点p,qについて、pとqの全ての内分点がAに含まれる（ただし、Aの辺上にある点も、Aに含まれるものとします。）」ということで、つまり「Aに含まれる任意の２点p,qを結ぶ線分はAからはみ出さない」という意味です。この条件は「Aに含まれる任意の２頂点p,qについて、pとqの全ての内分点がAに含まれる」と言い換えることができ、さらに「Aに含まれる任意の隣り合う２頂点p,qについて、pとqの外挿点(「p,qを結ぶ直線からp,qを結ぶ線分を除いたもの」の上にある点）はAに含まれない」と言い換えても構いません。

　あらすじとしては、点列a={(x[i],y[i])| i=1,2,...,n}の部分集合b={(x[i],y[i])| i=1,2,...,m}を頂点とする凸多角形の領域Bを作り、aの点が全てBに含まれるようにする。すると、a=bならば凹みはなく、a⊂b(a≠b)ならばaの要素のうちbに含まれない要素が、凹んでいる部分に相当します。

aからbを構成するアルゴリズムを構成すれば良いですね。たとえば
●aの隣り合う2点p=(x[i-1],y[i-1]),q=(x[i],y[i])を結ぶ直線に対して、aの全ての点がその直線の一方の側（たとえばqに立ってpを見たとき右側か左側）に含まれるなら、pかqはbの要素であり、さもなければpかqはbの要素ではない。このテストでbに含めない点を選び出せます。
具体的には、
p=(x[i-1],y[i-1]),q=(x[i],y[i])について、x,ｙ座標からX,Y座標へ平行移動と回転による座標変換を行い、qを原点としpがX軸のX>0の部分に来るようにしてやります。
すなわち
X=(x[i-1]-x[i]) cosθ - (y[i-1]-y[i]) sinθ＞0
Y=(x[i-1]-x[i]) sinθ + (y[i-1]-y[i]) cosθ=0
となるようなcosθ,sinθを求めます。
tanθ =- (y[i-1]-y[i])/(x[i-1]-x[i])
であるから、
θ=Arctan(- (y[i-1]-y[i])/(x[i-1]-x[i]) )
または
θ=π+Arctan(- (y[i-1]-y[i])/(x[i-1]-x[i]) )
であり、
(x[i-1]-x[i]) cosθ - (y[i-1]-y[i]) sinθ＞0
を満たす方のθを選べば良い。
座標変換が決まったので、他の点(x,y)について、
Y=(x-x[i]) sinθ + (y-y[i]) cosθ
を計算します。aの全部の点について、全部Y≧0であるか、全部Y≦0であるならば、pとqを結ぶ直線（辺）は多角形Bの辺であることが分かります。Y＞0となる点とY＜0となる点が混在するようなら、pとqを結ぶ直線（辺）は多角形Bの辺ではない。このときは（つまり、多角形Aの辺のうち、Bの辺ではないものがあるのだから、Aは凸多角形Bとは異なり、ゆえに）Aは凹みがある。

別の方法として（こっちはspringsideさんやranxさんの回答とほとんど同じじゃないかな？）、
●aの点列が反時計回りに並んでいるものとします。aの隣り合う3点p=(x[i-1],y[i-1]),q=(x[i],y[i]),r=(x[i+1],y[i+1])について、x,ｙ座標からX,Y座標へ平行移動と回転による座標変換を行い、qを原点としpがX軸のX>0の部分に来るようにしてやります。
さて、このときｒの座標は
X=(x[i+1]-x[i]) cosθ - (y[i+1]-y[i]) sinθ
Y=(x[i+1]-x[i]) sinθ + (y[i+1]-y[i]) cosθ
に来ます。
で、点qを二つのグループのどちらに入れるかを決めます。
Y＞0であるなら、点qを「グループ正」に分類します。
Y＜0であるなら、点qを「グループ負」に分類します。
Y=X=0なら、q=r。qはどちらのグループにも入れません。
Y=0, X＜0ならpとrを結ぶ線分上にqがある。qはどちらのグループにも入れません。
Y=0, X＞0なら、pとqを結ぶ線分上にrがある。つまりqは突きだしているか引っ込んでいるわけで、全ての点が同じ線分上にあるのでない限り、aは凸多角形ではない。（こいつは例外扱いしましょう。）
以上の分類をaの全ての点についてやります。「グループ正」か「グループ負」、どちらか一方のグループが空集合になったら、aは凸多角形である。

お礼

詳しいご回答ありがとうございます。

>頂点の列が与えられたとき、それが凸多角形(convex)であるかどうかを判定する、という問題のようです。

その通りです。実データが閉曲線のサンプリング値なもので、つい分かりにくいタイトルにしてしまいました。

>●aの隣り合う2点p=(x[i-1],y[i-1]),q=(x[i],y[i])を結ぶ直線に対して、aの全ての点がその直線の一方の側（たとえばqに立ってpを見たとき右側か左側）に含まれるなら、pかqはbの要素であり、さもなければpかqはbの要素ではない。

これはよく分かりますし、比較的簡単に計算できそうです。

第２の方法なんですが、私が#2のお礼に書いた判定法ではだめでしょうか。点がたくさんあるため、三角関数計算が避けられればそれに越したことはないので。

どの部分が凹といった情報は不要で、全体として凹部の有無が判定できればいいのですが。

回答No.3

springside

#2のspringsideです。

私が書いたやり方だと、「凹」の場合だけでなく、「凸（出っ張り）」の場合も判定されてしまうことに気が付きました。
閉曲線（と言うか、正確には多角形）の各辺をベクトルと見たときに、その方向（全体として右回りか左回りか）も含めて考慮しなければならないようです。
という訳で、私の解答ではマズイです。

なお、
>>ベクトルakに対し、Pk+2がその右側か左側かを判定するという操作をk=1,2,3...について行い、符合が混在すれば凹みが存在すると考えていいわけですね。
→そういう考え方です。

>>連立方程式を解かなくてはならないでしょうか。
→連立方程式の組の数は多いでしょうが、それぞれがたった２変数（２元連立方程式）なので、手間はかからないと思いますが。

お礼

再度ご回答ありがとうございます。

>私が書いたやり方だと、「凹」の場合だけでなく、「凸（出っ張り）」の場合も判定されてしまうことに気が付きました。

すみません、これがよく分かりません…。凸（出っ張り）しかないのに、符号が混在することがあるでしょうか（この問題では「凸」という字の形にも凹部があります）。

シンプルで良い方法に思えたのですが。

回答No.1

ranx

参考URLは以前私がした質問で、もちろん今回の質問とは異なります。
ただ、No.10の回答に対するお礼を見て頂きたいのですが、
「回転の中心」を判断の基準にしようという回答に対し、
私は「閉曲線の内側」で判断した方が良いと考えました。
この違いの生ずるところが、まさに凹みの部分です。
ちなみに曲線が右回りか左回りかということは、面積が
正か負かということに置き換えることができます。
考えてみて下さい。

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=289549

お礼

参考質問をどう応用したらよいかよく分からなかったのですが、#2のspringsideさんの回答と合わせて考えてみます。

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