OpenGLで図形をマウスで引いた直線で切断するようなプログラムを実装したいと考えています。  
OpenGLのversionは4.6ですが、こちら(<http://wisdom.sakura.ne.jp/system/opengl/>)のver1.1に基づいたチュートリアルを勉強しています。

ユーザーが何も手を加えていない初期状況は、黒い背景の中に描画された白い図形がただ一つあるような状況と想定しています。これをユーザーがマウスによって引いた線分にて、繰り返し切断していき、各図形は見やすいように少し距離をとって、重ならないようにする。というものを実装したいものです。

自分は以下のような手順にしたがって、これを実装しようと考えています。

1.まず、左クリックを押したポイントを線分の始点として取得し、そして左クリックを放したポイントを線分の終点として取得する。  
2.もし、線分の始点と終点が図形の外側にあり、かつ線分が図形と交わっており、かつ線分による切断によってその数が増えるようなときに限り、図形を切断する。複数一挙に切断される場合があってもよい。図において、ドーナツの方は図形の数が増えるという条件をみたしていない。  
[![ドーナツの方は図形の数が増えるという条件をみたしていない](https://i.stack.imgur.com/VU418.jpg)](https://i.stack.imgur.com/VU418.jpg)  
3.どの二つの図形も最も近い部分の距離が定数c以上になるようにしておく（より形式的な言い方をすれば、閉である図形Aの点pと図形Bの点qに対してmin
d(p,q)>=c が成り立つ）

これを実現するアルゴリズムを実装しようとしたのですが、適切なアルゴリズムが思いつきませんでした。  
手順2では線分によって図形を分割するという部分と図形が増えないという判定のアルゴリズムが分かりません。（ただ線分が図形を横切っているのに図形が増えないというのは図形が単連結でない場合のみに発生し、単連結な図形を線分で切断すると、単連結なものが出るはずなので、図形が増えない場合が出ないように、最初の図形を単連結と仮定すればよいだけかもしれない）  
手順3では二つの図形の最も近い部分の距離の求め方が分からないのと、素朴な実装ではすべての二対の図形の距離を求めなければならないので無駄に感じます。また、もし二対の図形の距離を適切に放しても、他の図形とは動いた先で距離がc以内になってしまうことが考えられます。

これらを適切に実装できるアルゴリズムを教えていだたければ幸いです。

手順3については「図形が重複しておらず、切断されて図形が分かれている」ということさえ分かれば、距離をc以上にする
という方針は取る必要がないように思われます。

手順3は特に方針を変えたいですが、他の手順についても、何かよりよい方針が分かる方がいたら、そちらも教えていただければ幸いです。
CC BY-SA 4.0
2021-03-19T18:20:49.830
74772
2021-03-29T01:44:39.907
2021-03-20T11:36:22.930
19110
44365
question
アルゴリズム opengl
OpenGLにて、図形をマウスで引いた直線で切断したいがアルゴリズムが分からない。
**手順2（分割の有無）について：**  
最も単純に，画像処理的に考えてみれば，線を引いた後でラベリング処理をしてみれば判断がつく話．  
ここでは図形の内側には興味がないであろうから「輪郭を辿る」ような処理で同様の判定が行えるように思える．  
（図形が分割される ＝ 図形の輪郭がいくつかのループに分割される）

**手順3（図形の配置）について：**  
処理が簡単そうなアイデアとしては，各図形の外接円群を考えておしくらまんじゅう的に調整するとかでしょうか．  
（図形間の空間確保には，例えば各円の半径を c/2 程度余計に大きくとればよい）
CC BY-SA 4.0
2021-03-29T01:44:39.907
74956
2021-03-29T01:44:39.907
44553
74772
answer