- 締切済み
3DCGの面の和集合の計算方法
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- rabbit_cat
- ベストアンサー率40% (829/2062)
- noocyte
- ベストアンサー率58% (171/291)
凸Ｍ角形と凸Ｎ角形の共通部分を求めるアルゴリズムは， ↓この本に書かれています．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
お礼
ご返答ありがとうございます．現在，自分なりに考えたアルゴリズムで奮闘中です・・・ 一応計算は出来るようになったのですが，計算量が多かったりしていつかアルゴリズムが破綻しそうな予感です． 回答いただいた参考書を見て考え直したいと思います．
関連するQ&A
- 二重和をExcelで計算する方法
初めまして。 二重和をExcelで計算したいのですが、専用の関数・あるいは効率的な計算方法はありますでしょうか？ Excelに関するサイトもいくつも調べたりしたのですが、わかりませんでした。 研究室で与えられた方法は、恐ろしく手間がかかるもので、効率的な方法がないか探しています。 よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 平面度の計算方法を教えて下さい。
会社で使用する測定機器に平面度を算出するプログラムを導入することになったのですが、平面度の計算方法がわかりません。 自分でも調べたのですが、最小二乗法という方法があるのはわかったのですが、その他にもあるかもしれないと聞きました。 どのような方法があるのか、大まかに方法を教えていただけませんでしょうか。よろしくお願いします。
- ベストアンサー
- 測定・分析
- ダンボールの強度計算式んついて
お世話になります。 ダンボールの積段数算出をエクセル内で、自動計算させたいのですが、 積段数を算出するための強度計算式を教えて欲しいと思っております。 ネットで探したところ、入力すると答えが出てくる、プログラムソフト は見つかるのですが、原理となる計算式が分かりません。 よろしくお願いします。
- 締切済み
- その他（開発・設計）
- ３ＤＣＧソフトメタセコイアについての質問です。
３ＤＣＧソフトメタセコイアについての質問です。 メタセコイアでキャラクターの顔を作って顔にテクスチャーを貼ったのですが、なぜが目の部分のテクスチャーがいびつになってしまいます。 顔ポリゴンはまず平面で目や口を作り、平面で顔を作ってからＺ軸を移動させてやる方法です。目の部分は８角形で中心の頂点をくっつけています。この状態で目の部分にテクスチャーを貼ると、割れた鏡のように画像が面と面の境目でずれてしまいます。 どうすればきれいにテクスチャーを貼ることができるのでしょうか？ テクスチャーは参考書などでよくあるようにグリッド画像を貼り付けて、グリッドのゆがみがないようにしてやる方法なのですが、顔ポリゴンの正面でＵＶ展開しているのに、目の部分で上記のように画像にずれがでてしまいます。 どなたか解決法をご存知でしたらご教授ください。 よろしくお願いいたします。
- ベストアンサー
- その他（ホビー・玩具）
- 三角関数 和積・積和のスマートな導き方は？
和積・積和は暗記したくないので、今は導いて使用しています。 思考過程に無駄な箇所が無いか教えてください。 【１】 sinα＋sinβ ＝sin(A+B)＋sin(A-B) ＝sinAcosB＋cosAsinB＋sinAcosB－cosAsinB ＝2sinAcosB -----上記4行の思考過程------------------------------------ まず、sinα＋sinβを処理しなければならないとき、 ＝sin(A+B)＋sin(A-B)とします。理由はこれを省くとAとBって なんだったっけ？となってしまうので。そして、次に ＝sinAcosB＋cosAsinB＋sinAcosB－cosAsinB を書きます （実際は書いている最中に頭の中で答えが見えてくるのでこの 行は実際は半分くらい書いて次に進みます）。そして、 ＝2sinAcosB と書き、α＝A+B、β＝A-B から、A＝（α+β）/2、 B＝（α-β）/2を計算し、代入して、答えとします。 sinα±sinβ、cosα±cosβの４つはこの方法でやります。 【２】 また逆の作業である、積を和にするのを実際にやってみたのですが、 計算が煩雑になり、簡単な方法を見つけられませんでした。 積和において簡単な変換方法は無いのでしょうか？ありましたら 教えてください。 少しわかりにくいですが、質問は2点です。 【１】上記 sinα＋sinβ の変換方法に無駄が無いか、あるいは もっと良い方法があるか 【２】積を和にする良い変換方法が無いか、あるいは もっと良い方法があるか です。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 1,2,3,…,nからk個とったものの積を考え、それらの全部の和
1,2,3,…,nからk個とったものの積を考え、それらの全部の和を求めたいのです。 たとえば、1,2,3から2個とったものの積は、 1・2、1・3、2・3 ですが、それらの全部の和は11になります。 1,2,3,…,nから1個とったものの積を考え、それらの全部の和は、 n(n+1)/2 です。 1,2,3,…,nから2個とったものの積を考え、それらの全部の和は、腕力で計算して、 (n-1)n(n+1)(3n+2)/24 となりました。 1,2,3,…,nからn-1個とったものの積を考え、それらの全部の和は、 n!(1 + 1/2 + 1/3 + … + 1/n) と、階乗数と調和数列の積になることは分かると思います。 1,2,3,…,nからn個とったものの積を考え、それらの全部の和は、 n! です。 一般に、1,2,3,…,nからk個とったものの積を考え、それらの全部の和を求める方法はあるのでしょうか？ (1+x)(1+2x)…(1+nx)の展開式におけるx^kの係数を求めると考えてもいいです。
- 締切済み
- 数学・算数
- 部分和問題がわかりません。
部分和問題がわかりません。 [問題] n個の整数が配列Aに格納されていて、整数xの値を与えたときに、 A[i] + A[j] = x となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズムを示せ。 この問題は部分和問題のため、NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思うのですが、もっと効率のよい方法が存在するのでしょうか？
- ベストアンサー
- その他（プログラミング・開発）
お礼
ありがとうございます．参考にさせていただきます！