3角形をくりぬく処理に関して

[名無三]

ques.png (22.2 KiB) 閲覧数: 3301 回

初質問失礼します。
現在r6sなどの壁表現に感銘を受け、3D演算にてポリゴンの再分割を手前実装してみようとしています。
仕様として　三角ポリゴンから任意の場所に正多角形の穴をあけた三角ポリゴンの集合体を再生成する　ことを目標とします。
手順として
①開ける中心の場所を指定
②中心から多角形分の点を取得
③多角形の辺と三角形の辺の交点及び三角形に入っている多角形の点が出したい結果の点になる
④元の3角形の点のうち多角形に入っているものは結果の点にならないので排除する
⑤くりぬいた多角形になるように点をつなぐ
⑥できた多角形を3角形に分割する
としようと考えています。

ここで質問なのですが、現在⑤の部分で詰まっています。多角形の偏角ソートでできるかと思いましたが見当違いでした…
⑤を行う方法をご存じの方、いやそもそも方法が変だろとお教えいただける方を探しています。よろしくお願いいたします。

[usao]

すぐに（三角形に）分割するのなら，そこで一旦つなぐ意味って何になりますか？

（【ばらばらの点群　→　何故かつなぐ　→　すぐにまたばらばらにする】という話だとしたら中間のステップって要るんですか？　という素朴な疑問．）

[usao]

言い換えれば，「その図の(3)の赤い点群から出発して(6)の処理がやれないのだろうか？　という疑問」…になるのかな？

---

それはそれとして（点群を「つないで」外周みたいなデータを作る必要があるのだとして），
「交点」を求めているときに，それは「どの辺とどの辺との交点なのか」というのが分かっているハズだから，
そこから，「その求めた交点と隣接する点というのはこいつとこいつだよね」っていう話が既知だと言えるのではないかな．

例えば，
三角形が A→B→C(→A) っていうグラフで
四角形が a→b→c→d(→a) っていうグラフである
とわかっているところから出発したのだとして，
あるとき（その重なり具合から？）
「この場合は，辺 A-B と b-c との交点を求めなきゃならないね」っていう判断ができているならば，その時点で上記の事柄は明確なのであり，そしたらグラフを連結できるように思える．

[usao]

まぁ具体的アルゴリズムとかまでは示せないけども，
例えば，その図で

三角形の左側の辺　と　四角形の上側の辺　との交点を求めたとき…

その交点というのは，三角形の左側の辺の両端の頂点のうちのどっちと繋がるのか？　というのは判断できるハズ．
（例えば，図形の各辺に「図形の外側」を向くような法線でも与えておけば良いんじゃないかな．この例だと四角形の上辺の法線が向く方向にある側の頂点：「四角形の内側に切り取られない側」にある頂点　を選ぶ感じか．）
同様に，この頂点が四角形の上側の辺の両端の頂点のうちのどっちと繋がるのか？　もわかる．

…んじゃないかな？　という話．
（つまり，この交点は，三角形の上側の頂点と四角形の右上の頂点に繋がる，っていうのがわかる）
各交点に関してそういう情報が得られていれば，それらを総合して用いればいけるちゃう？　っていう．（漠然）

[usao]

オフトピック

一方が完全に他方の内側に入っている場合とか
四角形が三角形の頂点をいくつか含む場合とか
四角形が三角形を複数個の図形に分断するような場合とか

…も扱わないとならないだろうし，
「ちょうど接する」みたいな状態でバグらないように気を付けないといけないかもしれないし…
有り得る様々な状態にちゃんと対応できるような実装を用意するのは大変そうだなぁ．

[usao]

> その図の(3)の赤い点群から出発して(6)の処理がやれないのだろうか？

の側を考えた方が話としては楽なのかもしれないなぁ．
例えば，とりあえず適当にドロネーか何かで三角形分割した後，要らない三角形を捨ててしまえば良いのでは的な方向とかで．
（話としては楽だったとしても，現実的には処理速度とかの面でNGになり得る？）

[名無三]

usaoさん、ありがとうございます。
⑥を正確に出すためにはきちんと多角形の辺が出ている必要がある、と早合点してしまっていました。確かに⑤をスルーするべきですね。
外から中への交点かどうかなどで判断できそうですので一度辺でできる三角形から要らない物を捨てるよう実装してみます。

[名無三]

とりあえず点に
・三角
・四角
・中から外への交点
・外から中への交点
の属性を付けて分割後の辺を含めてつなぐ線の候補をきめるという方式を試しています。
そのうえで四角の中を通る辺は排除する形でなんとかなりそうです

[名無三]

現状

https://qiita.com/edo_m18/items/7b3c70ed97bac52b2203

こちらの方のものを基に分割作成
↓
出来た3角形の中から
・細いものを除去
・3点すべてが重なるものを削除
・三点すべてが三角の辺属性のものを削除
・三点すべてが多角か交点属性のものを削除
・辺に多角形の対角線が含まれているものを削除
・辺に多角形の辺が含まれておりもう一つの点が多角形に向いているものを削除

としていってなんとか近いものができてきました…

が、重なっている三角を排除できていないのでその部分を検討中です。