こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

2多角形を重ねた際の重ならない部分の座標取得方法

OS:XP
開発環境:VS2005

長方形の図形に三角形の図形をちょうど中心ぐらいが一致するように重ねると、
重ならない部分で多角形4つができますが、これらの個々の多角形座標を順番に(時計回り)求めたいのです。

http://dobon.net/vb/dotnet/graphics/fillregion.html
こちらのHPを引用させて頂きますと、ちょうどXORで求めた領域の座標です。

辺同士の交点やXOR領域内等の判定で重なる点座標自体は求められるのですが、多角形を構成する為に
順番に並び替える必要があります。これがうまく出来ず困っております…。
XORで求めた領域はRegionで、このRegionDataから取得するのも困難なようで…。

なにかよい方法は無いものでしょうか。

投稿日時 - 2011-03-10 15:47:26

QNo.6584080

困ってます

質問者が選んだベストアンサー

最初の質問に時計回りで求めたいとありましたが、座標計算は反時計回りが一般的ですし、画像にふられた番号も反時計回りになっているので、反時計回りとして説明します。


画像の横長の長方形をPとし、各頂点を、
Pa(-50,50)、Pb(-50,-50)、Pc(75,-50)、Pd(75,50)
縦長の四角形をQとし、各頂点を、
Qa(0,65)、Qb(-24,-58)、Qc(55,-60)、Qd(38,62)
とする。(縦長の四角形の座標が書かれていないので、目測で適当な値にしています)

線分のベクトルを、A→Bというように表現し、
ベクトルの左側が図形Rの内部、右側が図形Sの内部のとき、(A→B,R,S)と表現すると、
多角形を構成する辺のベクトルは次のようになる。
(Pa→Pb,P,N)、(Pb→Pc,P,N)、(Pc→Pd,P,N)、(Pd→Pa,P,N)、
(Qa→Qb,Q,N)、(Qb→Qc,Q,N)、(Qc→Qd,Q,N)、(Qd→Qa,Q,N)
(Nはどこの内部でもない場合の記号です)

ベクトルS→TとベクトルU→Vが交差するとき、
ベクトルS→Tからみれば、点Uと点Vは、片方が左側、もう一方が右側にあることになる。
どちらが左側かは、外積の考えを利用できる。
S(Sx,Sy)、T(Tx,Ty)、U(Ux,Uy)として、これを3次元に拡張して、
S(Sx,Sy,0)、T(Tx,Ty,0)、U(Ux,Uy,0)
ベクトルS→T、S→Uの外積を計算すると、
(S→T)×(S→U)=(Tx-Sx,Ty-Sy,0)×(Ux-Sx,Uy-Sy,0)=(0,0,(Tx-Sx)(Uy-Sy)-(Ty-Sy)(Ux-Sx))
このときz座標が正なら左側、負なら右側にあることになる。
(z座標が0のときは点Uは直線ST上にあることになるが、これを考えるとさらに難しくなるので0にならないものと仮定する)

Pa→Pbと交差するベクトルはないので無視。
Pb→Pcと交差するベクトルは、Qa→Qb。
Pc→PcとQa→Qbの交点をRaとすると、
Qaは上述の計算でPb→Pcの左側にあることが分かる。
(Pcx-Pbx)(Qay-Pby)-(Pcy-Pby)(Qax-Pbx)=(75+50)(65+50)-(-50+50)(0+50)>0

Pb→Pcは、Pb→RaとRa→Pcに、
Qa→Qbは、Qa→RaとRa→Qbに分割されるが、
QaがPb→Pcの左側にあることから、それぞれのベクトルは、
(Pb→Ra,P,N)
(Ra→Pc,PQ,Q)
(Qa→Ra,PQ,P)
(Ra→Qb,Q,N)
と表現できる。

分割されたPb→Raと交差するベクトルはないので無視。
Ra→Pcと交差するベクトルは、Qc→Qd。
その交点をRbとすると、それぞれのベクトルは、Ra→RbとRb→Pc、Qc→RbとRb→Qdに分割される。
QcがRa→Pcの右側にあることから、それぞれのベクトルは、
(Ra→Rb,PQ,Q)
(Rb→Pc,P,N)
(Qc→Rb,Q,N)
(Rb→Qd,PQ,P)
と表現できる。

同様にして、Pd→PaとQa→Raとの交点をRcとすれば、
それぞれのベクトルは、
(Pd→Rc,PQ,Q)
(Rc→Pa,P,N)
(Qa→Rc,Q,N)
(Rc→Ra,PQ,P)
に分割される。

Pd→RcとRb→Qdとの交点をRdとすれば、
それぞれのベクトルは、
(Pd→Rd,P,N)
(Rd→Rc,PQ,Q)
(Rb→Rd,PQ,P)
(Rd→Qd,Q,N)
に分割される。


2000文字しか入力できないので続きは次の回答で。

投稿日時 - 2011-03-12 20:24:09

お礼

非常に長文で丁寧に書いて頂き恐縮です…。

すぐには理解できませんので、少しづつ進めて参ろうかと思います。
絶対条件として2つの多角形は必ず反時計回りということでよろしいでしょうか。

結果はまた追ってご報告させて頂きたいと思います。

投稿日時 - 2011-03-12 21:25:34

ANo.7

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(9)

ANo.9

>絶対条件として2つの多角形は必ず反時計回りということでよろしいでしょうか。

そういうことです。と言っても単に反時計回りの方向にベクトルを取っていくだけですが。


#7,8のロジックにもれがありました。

多角形の1つの辺が別の多角形の内部に完全に入っていてどことも交差していない場合はうまくいきませんので、もう少し改良する必要があります。


このロジックはあくまで考え方を説明しただけですので、プログラミングはもっと簡潔にできるはずです。
例えば、四角形ABCDと四角形EFGHが重なって交点STUVができたとします。
そして、四角形ABCDの辺が分割されて、ASTBCUVとなったとします。
多角形ASTBCUVの辺を進んでいくと、交点している点STUVを通るごとに四角形EFGHの内部に入ったか、外部に出たかが交互に繰り返されることになります。
それを利用すれば一回だけ四角形EFGHの内部か外部かを判定するだけで、あとはいちいち判定する必要はなくなります。
そうすれば、上記の不備も解決できるでしょう。

投稿日時 - 2011-03-12 22:17:00

お礼

ご報告遅くなりました。

線上に始点終点を持つ場合の対応をしていた為、時間が掛かっておりました。
しかし、無事、求めていた結果の物が完成致しました。

有難うございました。本当に感謝しております。

投稿日時 - 2011-03-16 21:16:43

ANo.8

続きです。


以上から、分割されたベクトルをすべて挙げると、
(Pa→Pb,P,N)、(Pb→Ra,P,N)、(Ra→Rb,PQ,Q)、(Rb→Pc,P,N)、(Pc→Pd,P,N)、(Pd→Rd,P,N)、(Rd→Rc,PQ,Q)、(Rc→Pa,P,N)、
(Qa→Rc,Q,N)、(Rc→Ra,PQ,P)、(Ra→Qb,Q,N)、(Qb→Qc,Q,N)、(Qc→Rb,Q,N)、(Rb→Rd,PQ,P)、(Rd→Qd,Q,N)、(Qd→Qa,Q,N)

(Ra→Rb,PQ,Q)、(Rd→Rc,PQ,Q)、(Rc→Ra,PQ,P)、(Rb→Rd,PQ,P)
は、逆方向のベクトルにすると、
(Rb→Ra,Q,PQ)、(Rc→Rd,Q,PQ)、(Ra→Rc,P,PQ)、(Rd→Rb,P,PQ)
になるのでこれに替えて、以上16ベクトルを分類すると、

左側が多角形Pになるベクトルは、
(Pa→Pb)、(Pb→Ra)、(Rb→Pc)、(Pc→Pd)、(Pd→Rd)、(Rc→Pa)、(Ra→Rc)、(Rd→Rb)
左側が多角形Qになるベクトルは、
(Qa→Rc)、(Ra→Qb)、(Qb→Qc)、(Qc→Rb)、(Rd→Qd)、(Qd→Qa)、(Rb→Ra)、(Rc→Rd)
に分かれる。

あとはこれを終点=始点になるようにつなげていけば、
Pa→Pb→Ra→Rc→Pa
Rb→Pc→Pd→Rd→Rb
Qa→Rc→Rd→Qd→Qa
Ra→Qb→Qc→Rb→Ra
の4つの図形に分かれます。



以上ざっと簡単な流れだけ説明しましたが、これをプログラミングするのはちょっと大変かもしれません。

投稿日時 - 2011-03-12 20:27:38

ANo.6

>図では4領域分が表示されておりますが、実際には四角形の三角形が重ならな
い領域と、三角形の四角形が重ならない領域2つの領域しか求められません。(XORにて)

(XORにて)とは、画面上のビットをXORで求めたということでしょうか。
もしそうなら、三角形と四角形を別々の色で塗ってXORを求めれば4つの領域を判断できませんか。


#5で説明したのは、座標計算で求める方法です。

座標計算で求める方法具体的な計算式が知りたいなら、もう少し詳しく説明できますが、計算式よりも実例で説明したほうが分かりやすいと思いますので、三角形、四角形の頂点の座標、交点の座標を提示してくれれば、それを使って計算手順を示すことができます。

投稿日時 - 2011-03-12 15:33:29

お礼

ご回答ありがとうございます。頭がはじけそうです。

>画面上のビットをXORで求めたということでしょうか。
すみません、紛らわしかったですね。あくまで座標が知りたいのです。

>座標計算で求める方法具体的な計算式が知りたいなら…
是非、座標計算でお教え願えないでしょうか。
画像の更新や貼付けが行えませんでしたので、MSNのSkyDriveに画像を別途用意致しました。

http://cid-b44d20afd41e7032.office.live.com/self.aspx/%E5%85%AC%E9%96%8B/%E7%84%A1%E9%A1%8C.png

投稿日時 - 2011-03-12 17:14:38

ANo.5

任意に配置した多角形の上に別の多角形を任意に配置したとき、重ならない部分の多角形を求めたいということでしょうか。

その場合は、の点の座標で考えるより、線分(ベクトル)で考えたほうが分かりやすいでしょう。

n角形とm角形はそれぞれn本,m本の線分でできています。
この2つの多角形を重ねたとき、交点がp個できたとしたら、線分はn+m+2p個に分割されます。

線分をベクトルと考えれば、ベクトル方向に対して右側・左側が、2つの多角形の共通部分か、2つの多角形の外部か、それとも片方の多角形の内部かが分かります。

あとは、同一方向が片方の多角形の内部になるようにベクトルをつなげていけば、求める多角形になります。

投稿日時 - 2011-03-11 18:31:19

お礼

ご回答有難うございます。地震で大変ですが…。

未だ悩んでおります。引き続きご教授頂けないでしょうか。
お教えいただいた方法で、現在試しております。
 (1)交点を求める。
 (2)多角形を交点で線分に分ける
まで行いました。しかし、欲しい多角形になるように線分を繋ぐ所でつまづいてしまいました。

>ベクトル方向に対して右側・左側が、2つの多角形の共通部分か、2つの多角形の外部か、それとも片方の多角形の内部かが分かります。
 図では4領域分が表示されておりますが、実際には四角形の三角形が重ならない領域と、三角形の四角形が重ならない領域2つの領域しか求められません。(XORにて)
ベクトルの左右判定とは何に対しての判定になるのでしょうか。

>あとは、同一方向が片方の多角形の内部になるようにベクトルをつなげていけば、求める多角形になります。
 交点の順番も考慮し、取得していかなければならないのでしょうか。

投稿日時 - 2011-03-12 14:10:52

ANo.4

かなり限定された条件があること前提で質問だと捉えたのですが、
違うのでしょうか?

> 三角形がどの位置に配置されるかは定まっておりません。端っこの方で
> 少しだけ重なる場合や、三角形ではなく四角形の場合もあります…。
位置よりも大きさが重要で、三角形が十分に小さければ辺の交点は0個で
完全に内包されてしまいますし、直角三角形に近い三角形を用意すれば、
辺を重ねる事も可能でしょう?

> 重ならない部分で多角形4つができますが、
この時点でかなりの限定条件が適用されており、4つできること前提なら
長方形を2つ重ねて十字にした図形の座標を求めるくらい簡単になって
いるのでは?
要するに、必ず四角形の頂点の間に交点が2つあるという。
そうなると話は簡単だと思い、先のアドバイスをしました。

逆に本当に一般的に考えるなら、重ならない部分の図形は、1つである時も、
2つである時も、・・・6つくらいまでは簡単に作れると思います。

投稿日時 - 2011-03-11 10:38:52

お礼

ご回答ありがとうございます。タイトルや前提条件が明確でなく申し訳ありませんでした。

任意に配置した多角形上に、同じく任意に多角形を配置した際に、重ならない部分の多角形を
新たに作成するという処理が必要でした。完全に内包される場合は何も行わなくて構いません。

投稿日時 - 2011-03-11 11:40:01

ANo.3

三角形や四角形の大きさや重ねる角度によっては、添付図のようになるとは限りませんが、それでも添付図のような位置関係になると限定していいのでしょうか?

また、多角形を構成する個々の座標は分かっているが、その順番が分からないという質問でいいのでしょうか?

もしそうなら、
三角形の中心点とそれを通る基準線を定めておき、中心点から見た各座標の方向の角度を求めて、その角度の大きさ順に並べれば、各座標は順番に並びます。
あとは、各座標の属性(三角形、四角形の頂点か、重ねたときの交点か)によって分割すれば望みの順番になるはずです。

座標の方向の角度は、座標の内積や外積を使えば求めることができます。

投稿日時 - 2011-03-11 00:04:33

お礼

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

三角形がどの位置に配置されるかは定まっておりません。端っこの方で少しだけ重なる場合や、三角形ではなく四角形の場合もあります…。ご指摘頂いた内容は凸包やグラハムスキャンの事かと思われ、試してみましたが、入り組んだ多角形ではうまく順番を取得できませんでした。

求めた交点同士を重なる領域の輪郭となるように結び、更に図の四角形上の線を交点で分断し、線を繋ぎあわせ、座標を順番に取得する方法でいこうかと思っております。

少々ゴリ押しな感じですが、他に良い方法が思い浮かびませんでした。

投稿日時 - 2011-03-11 10:15:39

ANo.2

ああ、質問のタイトルが座標取得方法だから
座標の取得方法で回答しちゃったよ。

X,Y座標が2図形の頂点の範囲内かどうかで
判定してみたら?

投稿日時 - 2011-03-10 16:29:38

お礼

ご回答ありがとうございます。返信遅くなりました。
すみません、2図形の頂点の範囲内かどうかを判定するとはどういう事なのでしょうか。

投稿日時 - 2011-03-10 22:01:43

ANo.1

頂点の座標が分かってて、それを結ぶ直線しかないのだから、
2直線の交点を順に全部計算すればいいのでは?

投稿日時 - 2011-03-10 16:23:59

あなたにオススメの質問