3DCGの面の和集合の計算方法

質問

現在OpenGLを使って3DCGプログラムを作成しています．
何枚も重なるポリゴン，つまり同じ平面にある複数のポリゴンに対して，それらの和集合となるポリゴンの算出が必要となり困っています・・・
そこで質問なのですが，

同じ平面に存在する2つの多角形の和集合・積集合となる多角形を計算する方法って難しいのでしょうか？

いろいろ考えて見たのですが，なかなか良い案が出ませんでした．
効率の良い方法は無いでしょうか？
よろしくお願いします．

回答No.2

rabbit_cat

http://www.cs.man.ac.uk/~toby/alan/software/
http://www.complex-a5.ru/polyboolean/comp.html
など

お礼

ありがとうございます．参考にさせていただきます！

回答No.1

noocyte

凸Ｍ角形と凸Ｎ角形の共通部分を求めるアルゴリズムは，
↓この本に書かれています．O(M＋N) で計算できるそうです．

プレパラータ/シェーモス著，計算幾何学入門，総研出版．
http://www.amazon.co.jp/gp/product/4795263213?ie=UTF8&tag=noocytesprogr-22&linkCode=as2&camp=247&creative=1211&creativeASIN=4795263213

しかし非凸多角形の場合は，結局すべての辺の組合せについて
交差判定をしなければならないようです．(ちゃんと読んでませんが．)
(上の本は多数の線分の効率的な交差判定アルゴリズムも載せています．)

ただ，計算幾何学に出てくるアルゴリズムの多くは数値計算誤差に弱いらしく，
その点にも配慮しないとアルゴリズムが破綻 (途中で矛盾を検出して無限ループ
に陥ったり，暴走したり) することがあるそうです．

参考：杉原厚吉著，計算幾何工学，培風館．
http://www.amazon.co.jp/gp/product/4563036420?ie=UTF8&tag=noocytesprogr-22&linkCode=as2&camp=247&creative=1211&creativeASIN=4563036420

参考URL：

http://www.mm.ics.saitama-u.ac.jp/~ohsawa/Lect/sl-datastr2007.html

お礼

ご返答ありがとうございます．現在，自分なりに考えたアルゴリズムで奮闘中です・・・
一応計算は出来るようになったのですが，計算量が多かったりしていつかアルゴリズムが破綻しそうな予感です．
回答いただいた参考書を見て考え直したいと思います．