3D BIM

2011年9月18日 (日)

流体 メッシュ コツ (1) CFDの悪用に注意 バタフライ効果 カオス 非線形

このブログの検索フレーズランキングの10位に「流体 メッシュ コツ」というのが出てきた。 私は決して、流体数値解析技術を世の中に役立てようとする努力を否定するものではないのだが、現時点で作為的にも怠慢も含めて無作為的にも、それを悪用すること、期せずして悪用・弊害になってしまうことの方に、現時点では警鐘を送る姿勢だ。

これは、これからも、研究してみたいとは思っている。このブログ、あまり人気がないので、「流体 メッシュ コツ」で検索してヒットしてくれた人、1人ぐらいかも知れない。後で確認しておこうかと思う。

ただ、何に興味があって、「流体 メッシュ コツ」で検索したのだうか? 勿論というか、このブログに書かれているようなことが目当てではないとは思う。

正確な論考ではないが、流体解析ソフトが、流体解析のメッシュ切りの良いコツを、恣意的にでなく、自動生成してくれて、すなわち、そこに一貫・普遍的な理論があって、どんな流体問題にも、適切であるならまだしも、そうではなくて、流体解析にメッシュ生成の恣意的なコツというのが存在するならば、ナビアストークス方程式等を様々な境界条件で安心して数値解析できるというには至っていないという証左でもあるかと思う。我々はこれを肝に銘じて、真実を得る為の投資を考える必要があると思うのだ。この曖昧さは、CFD結果の悪用の余地になってしまい続けかねない。

そもそも、ナビアストークス方程式等で良いのかは、ともかくとして、境界条件に対して、真の解が一意に存在するのかどうかと言う数学的背景や数値演算の限界が、いわいる、バタフライ効果の一因にならざるを得ないかの数学的考察を充分に吟味しないで、スパコンで解析して現象が判った、証明したとはしゃぐのも、いかがなものかと思うのである。

CFD等、使い方、使われ方には、今後も充分な注意が必要だと思う。信じすぎるとスパコンを使える大資本のいいなり都合で、騙され続けることにもなる。事前の安心。安全保証が破綻したときの、責任所在のうやむの道具に使われ続けかねない。スパンでCFDしたこと、それにどんなに金がかかっていたにしても、決して精一杯の誠実な努力だっと簡単に納得してはいけない。まして、今まではやってなかったけど、今後はスパコンでCFDするから、信頼してちょ、なんて言葉にもたやすく乗るのはいかがなものかと思う。

| | コメント (0) | トラックバック (0)

2011年9月10日 (土)

大きな逆行列 数値シミュレーション 数値シミュレーション神話

「大きな逆行列」でググると、産業連関表に関するものなんかがヒットする。 確か日本の産業連関表なんかだと400×400次元の行列になるかだったかと思う。産業連関表の研究だと、この逆行列を求めることが必要不可欠になる。

日常の必要性だと、これでも充分に大きいが、本格的な数値解析、数値シミュレーションの世界では、この程度では、まだまだ小さい。

コンピューターのお勉強、数値解析のお勉強で、逆行列の求め方を、勉強するにしても、有限要素法とかをやらないと、具体的には、大きな逆行列を扱うことは少ないと思う。

まんず、解くべき行列を用意、入力するのが面倒くさい。もし産業連関表のデジタル・データが入手できるのなら、少し大きい行列を扱う、良い機会でもあろう。(ただこれ、入手するのに数万円だか、かかる見たいで、とても良くないことだと思っている)

有限要素法でなくても、そこそこの柱、梁の数のラーメン構造を、モデル化して、弾性変形の範囲内で、線形変形の範囲内で、すなわち可塑変形前の範囲内で、構造の静的変形を解析するのなら、マトッリクス構造解析の理論で数百次元の逆行列計算をプログラム経験するのも、そう難しくはないだろう。確か、この前提なら振動性状、固有値、共振周波数特性なども計算できたかと思う。非線形問題でも、瞬時瞬時を線形近似するのであれば、後退差分、陰解法等が有益なら、逆行列は必要になったかと思う。

逆行列を求めるというだけなら、今はexcelの組み込みでもできてしまう。手作りのベタなプログラムで計算するよりは、早いかも知れない。

ただ私は、このようなことに関してはどうもexcelなどは好きになれない。プログラミング環境としてエレガントでないし、発展性に乏しく感じる。次元の大きさにも制限があったかと思う。

JrubyとJavaを愛好しつつあるので、まんず、Javaなどで、逆行列をもとめるフリーの逆行列計算のルーチン、ライブラリを利用したいと考えている。

ネットで少し調べてみたが、今は、「Apach Comons」「Jakarta」あたりをキーワードに探っている。

実は400×400次元程度だったら、Mathematicaで計算したことはある。しかし、みんなが、高価な、Mathematicaを所有している訳でもなく、そこに不満が残る訳だ。疑いもなくMathematicaを使ってしまった訳だが、Mathematicaの逆行列計算は、極めて高性能だという評判である。

高性能だと言うのは、計算が早いという他に、精度が高いということらしい。これは実際には、複数の逆行列計算ルーチンを持っていて、解くべき行列を適切に分析して、最適なルーチンを適用してくれているからでもあるらしい。まあこれが、Mathematicaの商品価値の一部ではあるのだろう。

この辺をにらみながら、、「Apach Comons」「Jakarta」の利用を図っていく必要もあるかと思う。

問題によっては、バンドマトリックスの性質、ピボットとかいう概念も、復習する必要がありそうだ。

ちなみに、有限要素とかマトリックス構造計算では、物理モデルが直接的?には隣あった要素でしか、接触していないので、方程式は疎な行列になりがちかと記憶している。バンドマトリックスに変形しやすかったというところだろうか? 産業連関表はやや疎ではあるが、バンド系ではない例と記憶している。

ちなみに、構造系で剛比バランスが悪いと、精度良く計算しがたい場合もあったかと記憶する。もしなんとか計算できたとしても、それが健全でないのなら、反省されるべきだろう。アクロバチックな構造計算・構造デザインができたと喜んでもいられない。建築構造関連の技術資格授与なども、その辺のところ、しかっりチェックして欲しいところだ。

逆行列というのは、元の行列と乗すれば単位行列になるのだから、乱暴に言えば検算はしやすい。元の行列が倍精度でモデルとして真の値だとしても、真の逆行列が倍精度で表せるのは一般的でないから、検算で数値計算で正確な逆行列が得られるのも一般的ではない。必ず妥協の必要性が生じる。これを忘れてはならないだろう。また数値計算の反復アルゴリズムだったりするから、計算過程のあふれ誤差の集積等で、気をつけないと、とんでもない逆行列を算出してしまうこともあるだろう。

逆行列の数値算出を利用するときには、検算の重要性に留意したい。

逆行列計算を含んでいる高価な解析ソフトの計算をやみくもに、ブラックボックスで信頼するのも、常に危険が伴うことに留意したい。まあ、長年こうした評価に耐えているから、高価であると信じたくもあるのだが、正義の為にも、多くの科学愛好家達がある程度安心して使えるフリーでオープンなツールを手にしたいというのが他力本願でもあるが私の願いでもある。

静的な構造物の応力解析なら、使ったワンショットの逆行列の検算も、さほど困難ではないが、時系列非線形問題の動的シミュレーションで、毎瞬時、近似線形の逆行列を計算し直している場合は、検算が容易ではないので、ゆめゆめ、注意が必要かと思う。

兵器の輸出に関してココム規制というのがあったかと思う。もし高度なシミュレーション技術が兵器開発に有効なら、高性能な逆行列算出ライブラリーというのも、ココム規制になってしまわないのだろうかとも考える。本当はそうなのだが、実は心配するほどの、高性能のライブラリーなどは存在していなくて、ペンタゴンなども、騙されて、結構いい加減なシミュレーション・ソフトを米国のITゼネコンから掴まされているのかも知れない。

精密高度な数値解析神話というのがあるのかも知れない。本当に信頼できるのは、適切にロバストなモデル化自体の方なのかも知れない。NASAの有人ロケットも実は相当な部分それに基づいて安全に打ち上げられてきていたのではなんて思う。

今信頼がゆらいでいるのは、原子力ムラのエセ技術力、ハッタリ安全性である訳だ。

実は私が、逆行列を伴った、技術計算を皆でフリーで共有したいと願うのは、省エネの為の様々なシステムのシミュレーションの為である。実際の自動制御の挙動も含む、非線形のシミュレーションを共有したい。陰解法もできるようにしたいと思っている。

この方面、Simulinkという、結構有名なソフトもあるようだが、こうしたものを、省エネの為に、中身も含めて、国民みんなのもとに、という考えである。

なんにしても、傲慢というのはいけない。オープンソースで全ての国民・人類の評価にさらされているプロジェクトでなければ、信頼できない。

まつもとゆきひろ氏のRuby開発が手本・理想の1つだ。

| | コメント (0) | トラックバック (0)

2011年5月11日 (水)

単調な多角形の三角形分割 穴のある必ずしも凸でない凹ポリゴンの三角形分割

A:コンピュター・ジオメトリ 計算幾何学:アルゴリズムと応用

近代科学社 浅野哲夫 訳 2001年9月30日 初版第2刷発行 から

複数の穴がある必ずしも凸でない多角形・非凸多角形・凹ポリゴンを単調な多角形に分割することについて感想と私の戦略を述べてきた。

人間の直観に頼らずに、コンピュータ-にシステマティックに破綻なく穴の処理ができるアルゴリズムを示している文献を、私はA以外に見つけていない。

こうした、穴の処理に、最大の関心がある私にとっては、上記のように、穴のある多角形を、(当然)穴のない単調な多角形に分割するアルゴリズムがまずは重要だ。

ここに、私にとっての、最大の山場があったと思う。その次工程の単調多角形を三角形分割するAのアルゴリズムについても、自己流の解釈、感想から始めてみよう。

単調な多角形であるから、おおむね、ただひとつの最上部の出発点と最低部の最終点を持つ。出発点と最終点以外では、水平の走査線上、必ず2本、2本だけの、辺が存在する。辺や頂点はおおむね、右側、左側に分類できる。辺や頂点に関して、対岸という言葉が使える。

基本的には、上の頂点から下の頂点に向かって、三角形分割していく。Aの69ページでは、これを貪欲と称している。Aの71ページでは、アルゴリズムは第1章の凸包に似ているとあるが、多分に逐次構成法的であるということか。

①:まず、最初、上から3つの頂点があれば、三角形が分離できる可能性がある。この分離によって、元の単調な多角形の2辺が、データ構造から取り除けられて、三角形分離に要した、対角線・分割線分・分割辺が新しく、元の単調な多角形のデータに加えられる。また1つの頂点のデータが取り除かれる。このことを、2重連結辺リストのデータ構造変化で表しても良いかも知れない。2重連結辺リストで、最終的にすべての部分三角形を抽出することが可能と思われるが、2重連結辺リストが良策、得であるかは、斟酌して見たい。

②:新しい、単調な多角形の上から3つの頂点で三角形が分離できるか考えてみる。三角形が分離できない場合がある。3つの頂点の中で、内角が180度以上あるものが、ある場合だ。このような頂点を{v1,v2,・・・・vn}とストックしておく。vnを最新のものとしておく。すなわちこのリストの左側ほど、大きなy座標を持つ、上にある頂点だ。

③:単調な多角形の左右、どちらかの辺の頂点で、②のような三角形分離できない頂点が続くと、その頂点を結んでできる複数の辺は、Aの69ページ表現によると、漏斗を逆さにしたようなシルエットを形成すると表現されている。日本人だったら富士山の稜線形と言ったら判りやすいだろうか?

④走査の新しい頂点によって、②③で止まっていた三角形分離が可能になった場合、②のリストの右側から処理して、この頂点を解消する方針として見よう。

単調な多角形の左右、どちらかの、未処理の富士山稜線を成す一連の頂点は、必ず下側(リストの左側)から、順次処理されて、途中で止まることがあるが、処理できなかった頂点群をスキップして、また処理が再開できることはない。ということが言えると都合が良いと思われる。

⑤:④の三角形分離が再開されて、富士山稜線が解消される場合は、三角形分離再開のきかっけとなる新しい下側の頂点が、富士山稜線側の頂点である場合aと、富士山稜線の対岸である場合bがある。

場合bのときは、この富士山稜線を成す頂点は全て処理できる。

もしそうでないとすると、富士山稜線が単調な多角形であることと矛盾するか、この新しい頂点が、この富士山稜線とは別のこれより下にある、対岸の別の富士山稜線に属する頂点だったことになり矛盾するからである。すなわち、仮にこの別の富士山稜線をなす、上の方の頂点で、何故、対岸の上にある富士山稜線の頂点を処理できなかったのかという矛盾が生じる。

場合aのときは、処理は途中で止まる場合もあるが、それなりに、いくつかの三角形分離ができて新しい単調多角形のデータが更新されるまでのことである。加えて言えば、残された富士山稜線がその後さらに成長する場合もある。

私は今のところ、おおむね、こんな風に理解している。これが間違っている、後で修正すること大である。

| | コメント (0) | トラックバック (0)

2011年5月 5日 (木)

穴のある必ずしも凸でない多角形・凹ポリゴンの三角形分割 2重連結辺リスト

A:コンピュータ・ジオメトリ 計算幾何学:アルゴリズムと応用 第3版

 浅野哲夫 訳 近代科学社 2010228日 初版1刷 発行 からのノート

穴のあるかならずしも凸でない多角形・凹ポリゴンを三角形分割する為に、単調な多角形に分割するアリゴリズムで、すでに述べたように、必要十分な対角線・分割線分・分割辺が1本づつ明らかにされるとき、2重連結辺リスト(A33ページから)がどう変化され、最終的にどう利用されて、部分単調多角形が抽出されるのか勉強してみよう。

はじめの穴のあるかならずしも凸でない多角形・凹ポリゴンの面レコードをf0として、部分単調多角形のリストを{f0} から始めてみよう。

部分単調多角形をf1,f2,f3・・・とすると

このリストは{f0, f1,f2,f3・・・}となる予定で、このf0と最初の{f0}とは異なる予定だ。f0は最後にしか、単調であることが確定しない予定としよう。おおむね最後まで、平面走査の下の方に残る部分多角形であると予定しよう。

としたが、これを変更する。穴のない場合はともかく、穴があると、必ずしも対角線の1つが確定したときに、かならず新しい部分単調多角形が生成されているとは限らないからだ。対角線が1本確定されたときに、新しい分割領域が生じているかいちいち検証しているより、どれだけの部分単調多角形に分割されたかは、最後に抽出した方が判りやすそうだ。

ただ、2重連結辺リストは、活用するので、最初の必ずしも凸でない多角形・凹ポリゴンをf0として、それとしておく必要はある。

最初のf0は穴のある多角形である予定だから、

f0.OuterConponentは、外側境界上の片辺のどれか1つを示す。片辺のリストである必要がないのは、そのただ一つの片辺から、後述するように、たどって外側境界上の全ての片辺にアクセスできる情報を持もっているからだ。

これは、多角形を分割して領域を増やしていくとき、元の情報を生かして、最小限の操作ですませる上で便利だ。

対角線1本を確定するたびという意味でないならば、最終的にはという意味ならば、上記は活きる。

f0.holeは、その内側の穴のリスト{ hole _1hole _2・・・}とする。

hall_1.InnerConponentsは、穴hole _1の穴の境界上にあるどれかの1つの片辺である。

最初、f0.OuterConponentの片辺は、外側境界上の片辺は双子辺を持たないものとしておこう

f0.OuterConponent.Originは片辺の始点(頂点)である。

この双子辺の始点は

f0.OuterConponent.TwinNullで存在しない。

f0.OuterConponentは反時計周りの外側境界上の片辺の1つで、進行方向の左側が多角形の内部だ。

この片辺が境界となっている面は

f0.OuterConponent[i].IncidentFace=f0 だ。

対角線が1本確定するとき、穴の存在も鑑みて新しい部分単調多角形が生成されるという前提ではないので、上記のf0.OuterConponent[i].IncidentFaceは、少なくとも初期的には必要ない。

この片辺の進行方向の次の片辺は

f0.OuterConponent[i].Next

この片辺の進行方向の前の片辺は

f0.OuterConponent[i].Prev

である。

i番目の穴のj番目の境界上の片辺の始点は、

f0.hole[i].InnerConponents[j]. Origin

穴の双子辺の始点は.

f0.hole[i].InnerConponents[j]. TwinNull

で存在しない。すなわち三角形分割の対象ではない。三角形が存在しないから向こう側が見通せる。

i番目の穴のj番目の境界上の片辺f0.hole[i].InnerConponents[j]

は時計周りで、左側が多角形の内部だ。

この穴の片辺が境界となっている面は

f0.hole[i].InnerConponent .IncidentFace=f0 だ。

このf0.hole[i].InnerConponent .IncidentFaceも必要ない。

Next,Prevも設定される。

始点などの頂点vxの座標は

vx.Coordinate

である。

頂点vxを始点とする片辺のリストは

vx.Incident

である。

重要なのは、最初のf0の穴も含めた、全、片辺のリストの保持・更新である。そして対角線・分割線・分割辺が、一本づつ確定したとき、その双子辺が、この片辺リストに追加される。

この片辺リストの片辺によてって参照される全頂点のリストも必要としておく。

今、走査線によって、単調な多角形への分割が進んでいて

{f0, f1,f2,・・fi}

だとする。

f1,f2,・・fiがおおむね走査線より下にあるとは考えられない。f1,f2,・・fiに、分離点、統合点がないのなら、これらは既に単調な多角形だ。f0はおおむね、初めのf0の走査線より下の部分であって、まだ単調でない可能性がある。

とくに、統合点と統合点で、対角線・分割線分、分割辺が引かれた場合は、上の統合点は解消されているが下部の多角形では、まだ片方の統合点の解消が残っている。すなわちまだ単調な多角形ではない。

最初の{f0}から初めてみよう。最初の対角線・分割線分、分割辺が確定したとしよう。この対角線の両側が、もはやともに領域f0ということはないから、新たにf1という分割領域が必要になる。この対角線のおおむね下は領域f0のまま、上を領域f1とするとして、2重連結辺リストを再構成する。

この対角線はf0と違って、双子辺を持つ。この対角線の双子辺の情報を適切にしておけば、最終的に全部分単調多角形の抽出が可能となる。

対角線の両端を始点とする辺の内、上向きの片辺をたどっていく。このたどっていく片々をei辺とするときei.IncidentFace=f1と変えていけば良い。

同時に分割領域・面のリストを{f0}から{f0、f1}にする。f1は、f1.OuterConponent、すなわち外側境界上の片辺のどれか1つでもかまわないだろう。分割領域のf1の全ての境界片辺はこれから、たどっていけるのだから。

これは{f0、f1}すなわち

f0.OuterConponent, f1.OuterConponent  をそれぞれ適切に対角線の双子辺のどちらかとする最小限の操作で可能だ。

対角線の両端をv1,v2としたとき、

v1. Incident, v2. Incidentという2つの片辺のリストの整備も留意したい。

目的の為には、あまり役立たないが、穴がないとした上で

単調でないかもしれないf0はともかく対角線によって生じたもう片方の分割領域f1は単調だろうか? そうかも知れないが今はそれにこだわらないことにしよう。

一般に、対角線・分割線分、分割辺が確定したとき、その対角線の両側は同じ領域fxだったはずだ。それはfx=f0かもしれないが、今はそれにこだわらない。重要なのは、おおむねこの対角線の上の新たな分割領域をfx以外にすることである。

それが既にある領域であることはないだろう。仮にすでにある領域fvであっても良いとすると、fxfvだったことになり、fxfv以外にしなければならないのに、fvにするという矛盾が生じる。さもなれば、fxfvでなかったとすると、すでにあるfvfxの境界を否定することになり矛盾するのである。

ここで、対角線の上下(左右)という概念を使っているが、対角線が垂直(水平)だったらどうするか、このときは対角線の左(上)を上(左)、右(下)を下(右)と考えてしまえば良い。

もし以上これらの考えが正しければ、Aには明示されていない次の命題が真となる。

すなわち

このアルゴリズムでは、穴がない場合n本の対角線によって、n+1個の単調な多角形に分割される。本当にそうだろうか。穴がある場合はこれよりも少ない。

これは、穴がない場合は、対角線が引かれるとき必ず新しい領域が生成されるということでもある。

これまでの自己流の議論に大きな誤りがなければ、おおむね複数の穴のある、かならずしも凸でない多角形・凹多角形の単調な多角形への分割のアルゴリズムはおおかた決まって、後は細かい点など実装で解決していけば良さそうだ。

| | コメント (0) | トラックバック (0)

2011年5月 3日 (火)

穴のある必ずしも凸でない多角形・ポリゴンの三角形分割

A:コンピュータ・ジオメトリ 計算幾何学:アルゴリズムと応用 第3版

 浅野哲夫 訳 近代科学社 2010228日 初版1刷 発行 からのノート

Aは、穴のあるかならずしも凸でない多角形・ポリゴンを三角形分割する為に、単調な多角形に分割するアリゴリズムを示す上で、それが大規模、複雑であっても、合理的に少ない時間で、それを為せるように、正確な記述がなされている。しかし、それがゆえに、とりあえず、穴のあるかならずしも凸でない多角形・ポリゴンを三角形分割する為に、単調な多角形に分割する方法が知りたい者にとっては、やや判りずらい記述でもある。合理的に少ない時間でが、不正確であっても、アルゴリズムのアイデアの基本のおおきな流れを、自分の言葉で、自分の流の表現にして、理解してしまうのも、目的達成の理解の第一歩でもあろう。これを、ある程度、自分でも合点のいく、自分の目的のための、必要十分にしていくのも、理解の1つのアプローチかと思う。こうした理解は、間違いである、後で訂正されること大である。しかし凡人の学習過程というのは、このほうが能率的であることが多い。

まずは、穴のあるかならずしも凸でない多角形・ポリゴンを三角形分割する為に、単調な多角形に分割するに、必要十分な、対角線・分割線分・分割辺を決めていくアルゴリズムの理解である。

Aでは、helper頂点というのが定義されている。役に立つかどうか判らないが、走査線が上から下に移動してく過程で遭遇する頂点に関してhelper辺というのも定義しておこう。

走査線が頂点vxに遭遇・到達したとき、vxのすぐ左側にある辺で、その辺とvxの間にある走査線が多角形の内部である辺を頂点vxhelper辺とする。

このとき、頂点vxは、このhelper辺の新しいhelper点候補でもある。

このすぐ左側の辺・helper辺を特定する為に、走査線上の辺を左側から並べた、

走査線上辺リスト={e_vx_1,e_vx_2,・・e_vx_m}

を保持するが、そこに、辺の右側が多角形の内部でないもの・穴である辺は必要ない。

(これが、A58ページの上段に記述されている「動的2分探索木τの葉節点に走査線と交差するρ(多角形)の辺を蓄えることにする」に対応する。

ただし、この辺リストは頂点のすぐ左の辺を見つけるものだから、右側が多角形の内部でないもの、あるいは右側が穴であるものは必要ないとA58ページ上段に記されている。)

helper辺が存在するのは、分離点(分離頂点)、統合点(統合頂点)、左側が多角形の内部である一般頂点である。

ゆえにhelper点(頂点)でありえるのは、分離点(分離頂点)、統合点(統合頂点)、左側が多角形の内部である一般頂点である。helper点(頂点)というとき、これを満たしていると言って良いだろう。ただし後述のように、分離点はhelper点として否定される。

多角形を単調な部分多角形に分けていくとは、分離点、統合点を、適切な他の頂点と対角線・分割線分・分割辺で結んで、分離点、統合点の存在を解消していくことである。

走査線が、分離点に遭遇・達したときは、その分離点のherper辺のherper点と、そのherper点がない場合は、helper辺の上端頂点が、この分離点を解消する為の、対角線・分割線分・分割辺の相手の頂点の候補で、分離点は即座に解消される。

helper辺の上端頂点を含めて広義のhelper点(頂点)と呼ぼう。

分離点と結ばれる可能性があるのは、統合点と一般頂点である。出発点、最終点、分離点が分離点と結ばれる候補となることはない。すなわち、これら出発点、最終点、分離点をhelper点として更新・登録するには及ばない。

一般頂点は、その右側が多角形の内部の場合は、helper辺の上端点、すなわと広義のhelper点として、その左側が多角形の内部の場合は、通常のhelper点の候補として、分離点と結ばれ、対角線・分割線分・分割辺を成す。

走査線が、統合点・統合頂点に遭遇・達したときは、分離点のようには、即座に、対角線・分割線分・分割辺を成して、これが解消できる訳ではない。この統合点をhelper点と結んで、対角線・分割線分・分割辺を生成しても、その統合点は解消されない、何故なら、そうすると、その対角線が、その統合点から上方に向かってしまうからだ。しかし、統合点はそのhelper辺のhelper点といつも結ばれていけない訳ではない、helper点が統合点の場合は対角線・分割線分・分割辺で結んで、その上方のhelper点である統合点が解消されるべきだからだ。この場合は、この走査線が遭遇・達した下の方の統合点が新しいhelper辺のhelper点として更新・登録され、その解消を待つことになる。このとき、helper点だった1つの統合点が解消されているのだから、新しく単調多角形が生成さていると思われる。新しくhelper点として更新・登録される、残された統合頂点は、残された、まだ単調多角形でない部分多角形の統合頂点と思われる。

 統合点であるhelper点が存在しない場合は、この統合点がhelper点として更新・登録され処理を待つことになる。

走査線が、一般頂点に遭遇・達したときは、そのhelper辺のhelper点が統合頂点だったら、これと対角線・分割線分・分割辺を成し、この統合点を解消する。

helper辺が存在しない場合は、この一般頂点を下端とする辺をhelper辺とし、このhelper辺のhelper点が統合点だったら、この一般頂点と対角線・分割線分・分割辺を成し、この統合点を解消する。

いずれにしても、helper辺が存在するならば、分離点に備えて、そのhelper辺のhelper点として更新・登録される。

はたして、以上は、おおむねAの考えと一致しているだろうか? 出来の悪い、気が短い、私は、A5860 ページの仮想アルゴリズムを熟読して、検証する気が、今は起きない。とりあえず、穴のあるかならずしも凸でない多角形・凹ポリゴンを三角形分割する為に、単調な多角形に分割する方法が知りたいAの読者の多くがそうかも知れない。私の記述だって読む気がしないだろう。

この手の問題は、いつもそんな気がする。

以前、記述した内容で、上記と矛盾しているところを修正しておく。

走査線がA57ページの図の頂点vx=helper(ej)に達するとき、

走査線vx辺リスト={ej, e_vx_2,e_vx_3,ek,e_vx_5,evx_6}

もしくは={ej, e_vx_2, e_vx_3,evx_4}

②そして、この走査線上、頂点vxの左が多角形の内部であった場合(vxが分離点、結合点統合点ならば、そうである)、頂点vxのすぐ左の辺が辺e_l_vxなら、辺e_l_vxの情報として、頂点vxが登録されるべきだ。これが、A58ページの上段に記述されている「また、τの各辺に対してそのハルパー(頂点vx)も蓄える」に相当する。このように辺に登録されることができるのは定義上、分離点と統合点で、くわえて一般頂点のうち左側が多角形の内部になっているものだ。ただし、分離点は後述の③のように、ただちに処理されてしまうので、実質、分離点がヘルパーとして登録されることはないと想像する。

     辺e_l_vx.helper=頂点vx

(A57ページの図でvxhelper(ej)のときは、辺ejhelper(ej)が登録される。)

     辺ej.helper= helper(ej)      =vx

③ 走査線が分離点viに達するとき、①の辺のリストは{ej,ek,e_vi_3,e_vi_4} もしくは{ej, e_vi_3} これから分離点viの走査線上、すぐ左側の辺がejと求まる。さらにこれから辺ejの②の手続きで登録・更新さている点が、A57ページの上段に記された、分離点viと結ばれるべきhelper(ej)点だ。

走査線の動きの性格上(上から下)、②の手続き上、辺ejに登録されている、ヘルパー頂点は、A57ページ上段の記述「形式的にhelper(ej)を定義すると、走査線より上にある最も下の頂点で、その頂点とejを結ぶ水平線分が(多角形)ρの内部にあるような頂点である」を満たしているはずだ。

もし辺ejに登録された頂点(helper)がなければ辺ejの上端点と分離点viが対角線・分割線分・分割辺で結ばれる。

走査線が分離点でも結合点統合点でもない頂点vxに達して、かつvxの左側が多角形の内部でない場合、この頂点vxを下端とする辺のhelper点と、このvx点が、対角線・分割線分・分割辺で結ばれる。このhelper点は統合点点とは限らない、一般頂点のうち左側が多角形の内部である頂点である場合もある。該当helper点が存在しないならば、なにも起こらない。

走査線が、一般頂点に遭遇・達したときは、そのhelper辺のhelper点が統合頂点だったら、これと対角線・分割線分・分割辺を成し、この統合点を解消する。

helper辺が存在しない場合は、この一般頂点を下端とする辺をhelper辺とし、そのhelper点が統合点だったら、この一般頂点と対角線・分割線分・分割辺を成し、この統合点を解消する。いずれにしても、helper辺が存在するならば、分離点に備えて、そのhelper辺のhelper点として更新・登録される。

⑤多角形を単調な多角形に分割することとは、分離点、結合統合点を、そこから、対角線・分割線分・分割辺を引くことによって、その分離点、結合統合点を消滅・解消していくことに他ならない。走査線が分離点に達する場合は、③のように即座に対角線・分割線分・分割辺が引けてしまって、この分離点をhelper点として、辺に更新・登録するには及ばない。

また、③、④で対角線・分割線分・分割辺を引いた相手がhelper点なら、その辺への登録を、辺から抹消しておく。

 走査線が結合統合点に達する場合は、③のようには、即座に対角線・分割線分・分割辺が引けるわけではないので、(何故なら相手の頂点は走査線より下にあるので)この点は、②のようにhelper点として辺に更新・登録され、③④によって、ここから対角線・分割線分・分割辺を引かれるのを待つのみである。

 ただし、helper点が統合点の場合は対角線・分割線分・分割辺で結んで、その上方のhelper点である統合点が解消される。

結局のところ、各辺に登録・更新・蓄えられるhelper点とは実質、結合統合点と一般頂点のうち左側が多角形の内部である頂点である。

穴の頂点が、適切に分離点、結合統合点、左側が多角形の内部でない(すなわち穴である)頂点として認識されるのなら、以上のアルゴリズムに不都合はない。すなわち、多角形に穴があっても、ちゃんと、単調な多角形に分割できる。すなわち三角形分割できる。

走査が完了してしまえば、穴のある必ずしも凸でない多角形を単調な三角形に分割するに、すなわち三角形分割するに、必要十分な対角線・分割線分・分割辺は明らかにされることになる。

次回、このように、必要な対角線・分割線分・分割辺が1本づつ明らかにされるとき、2重連結辺リストがどう変化され、最終的にどう利用されて、部分単調多角形が抽出されるのか勉強してみよう。

| | コメント (0) | トラックバック (0)

2011年5月 1日 (日)

コンピューター パソコン PC の消費エネルギーについて

例として、ネットでDELLのInspiron570の公式?仕様を材料に考える。電源の仕様としては、ワット数 300W 最大熱消費 1574 BTU/時 定格出力電流 7/4 A と規されている。

その他、コンピュータ環境として、温度範囲 動作時 10~35℃ 保管時-40℃~65℃ と記されている。

1W=3.4 BTU/h とすると 1574 BTU/時=463 W となる。

PCケースの換気風量にスペックがない。

どうも、このパソコンに限らず、この手の情報が不足している。少なくとも、この代表的な換気風量かPCケースの排気温度のどちらかの情報が欲しいのだが不足している。

http://www2s.biglobe.ne.jp/~ken-ishi/CPU-cooling.htm

を参考に、一般的にはと、換気回数を6回/分=360回/hと仮定してみて

外形寸法 176×440×375mm から風量は 1㎥/h 程度とし、室温を21 ℃ 排気温度をT ℃として

463 (w)=0.34×1(㎥/h)×(T-21) で計算すると

T=1383 ℃ となってしまうので、この仮定風量はオーダーからしてそぐわない。

http://pcconsidering.seesaa.net/article/194166000.html

を参考にすると 風量は 120~150 CFM すなわち 200~250㎥/hぐらいだろうか。

これだと、T=28~26 ℃ ぐらいであろうか。室温より、7~5 ℃の温度上昇である。

スペックでは室温35℃も動作範囲である。排気温は42℃~40℃程度となる。本当に室温35℃でも快適に動いてくれるだろうか?

200~250㎥/hの35℃の外気を21℃にまでヒートポンプのクーラで冷やすとして、COPが4だとすると、240~300 w ぐらいの消費エネルギーになる。

ここで何が言いたいのか、もしパソコンが満足のいく働きをするのに室温が21℃である必要があるのなら、このパソコンの消費電力は冬は463Wかもしれないが、夏はヒートポンプクーラの負荷も考えると実質763Wかも知れないということである。

私は、室温21℃でも室温35℃でも、消費電力を含めて、同じパフォーマンスであるパソコンの存在は信じられない。

しかし、そうであったとしても、室温35℃でも、最低我慢できる一般的な現代的な動作をしてくれるパソコンが、リーゾナルブルな価格ならば、素晴らしいパソコンと言えるだろう。つかう人間が汗だくになっても、パソコンを使って良い仕事ができるならばである。人間は機械とは違う。暑い環境でも気合いで乗り越えられることもある。

湯川秀樹だって暑い京都の夏を、福沢諭吉、勝海舟だってクーラーのない日本の暑い夏を乗り切っていたのだ。

省エネに貢献できるパソコンとは、このようなものでもある。ヒートポンプ経由でない排熱温度が60℃、100℃で、満足のいくパフォーマンスのコンピュータができれば、その排熱を給湯や、吸収式冷凍機の熱源に利用することだってできるかも知れない。

現在のパソコンのCPUは、フル稼働のとき、室温が21℃でも、その表面温度は60℃以上とか、かなり高いと聞く。ある意味素晴らしい。CPUの表面温度が100℃以上でも平気なら、外気温26℃、35℃の程度の差など、ゆくゆくは本質的な問題ではない。室温35℃、40℃で、現代の標準的なパフォーマンスを発揮できないパソコンだとしたら、CPUの性能を生かし切れていない、PCケース内の気流コントール設計の技術開発がない怠惰なダメパソコンと言って良いと思う。

省エネが叫ばれる今、コンピュータの性能表示の規格にも、問題ありではないだろうか? 通産省や関連学識者の怠惰を感ずる。

スーパコンピュ-ターで、どんなに演算速度を誇っても、液体窒素や、ヒートポンプ、クーリングタワーで冷やしまくなって平気なら、そんな開発には意味はない。金の無駄遣いだ。

私は、グーグルはそんな日本のスパーコンピュターやデータセンターの将来は眼中にないと思う。砂漠やアラスカ、シベリアにころがしたタフな無数のサーバーコンテナがとりあえずの視野だと想像する。その方が壊滅的なダウンの可能性もローコストに低くできる。基本的な暗号化技術があれば、むしろこのほうがセキュリティも高くなる。どこにアクセスすれば、まとまった盗むべき情報があるか?、そんなものはないからだ。どこに情報があるか? それは欲のないコントーロールされたネット上でしか機能しない機械しか知らないからだ。一台のアラスカやサバンナにころがったサーバコンテナの一つを略奪して中身を分析しても、ほんど何ひとつ知ることはできないからだ。

それなら、稼働率の高くない、今いったようなパソコンをネットでつないだグリッドコンピュータ化によるスーパーコンピューターの方が日本の為には優れている。

日本の夏の電力不足が懸念される。私はネットパソコンには、日本の為、日本の将来の為にも、他の事よりも貴重な電気を使うだけの価値があると信じている。人間が夏、部屋の中で、クーラを切って汗だくになっても、その人間に使われる、そこそこ動く、パソコンが日本を救うと信じる。

| | コメント (0) | トラックバック (0)

2011年4月23日 (土)

三角形分割 穴あき 非凸多角形 単調な多角形 平面走査 2分探索木

「コンピュータ・ジオメトリ」第3版初版第1刷でp53、「3.2 多角形を単調な部分多角形に分割する方法」を読んでいる。

穴はあるが自己交差のない、非凸多角形、凹多角形を、単調な多角形の分割を経て、三角形分割することが目論見である。

p58 動的2分探索木でとまどっている。穂影は、2分探索木に不案内で勉強も苦手である。ネットなどで調べるとソート技法にも関係するようだ。ソートを、ExcelやRuby(Jruby)、Mathmaticaの機能でブラックボックスで処理してきたつけかもしれない。

すでに、ソートされている要素の並びのリスト、ベクトル等に、新しい要素を加えたり、ある要素をそこから削除してから、それをまた、JRubyやMathematicaで要素の並びをソートし直して済ましてしまう穂影である。

数値だったり、順序ずけが可能な文字列が要素のリスト、ベクトルの場合は、善し悪しは別として、そんなことも可能であるが、平面走査の状態としての辺の並びの更新は、要素が辺と、動的な走査線の関係という概念なので、そうはいかない。

もっともベタな方法は、その全ての辺要素と捜査線との交点、例えば交点のx座標を求めて、分離点や結合点のx座標と較べて、この点に一番近い左側の辺を特定することになる。(大抵の実用上は、大した計算負荷ではないと思うが)。すなわち、分離点、結合点のすぐ左側の辺を特定する作業だ。このとき、前の辺々と走査線との交点の情報はもはや役にたたないと思うから、この作業が必要になると思う。

リストの先頭から、片っぱしから、辺々の捜査線との交点を計算し直すのは、効率上宜しくないから、2分探索木が必要などとも思う。穂影は、2分探索木の勉強をさぼって、まんず、リストの真中あたりから初めて、必要に応じて、リストの左右半分のどちらか(元の2分割)の真中あたりと、次々に元の4分割、8分割と、リストで隣となり合う2辺が、分離点あるいは結合点より左にあるかを調べることで済まそうかと考えている。

p58の2重連結リストだが、これは、p33の第2章線分交差2.2 2重連結リスト に遡るのだが、これは、愚っ直、素直に従ってみよう。

平面走査、2分探索木はここでも役割している。

| | コメント (0) | トラックバック (0)

2011年4月10日 (日)

穴あき非凸多角形の三角形分割アルゴリズムとブール演算・勉強の戦略2

http://hokage.cocolog-nifty.com/eyesonly/2011/04/post-1bb0.html

の続き。

コンピュータ・ジオメトリ 計算幾何学:アルゴリズムと応用

における、穴があいていることを含む、非凸多角形、凹多角形の三角形分割のアルゴリズムについてである。

この本、上記の目的を持つ者にとって、1つの解答を与えていると思うのだが、実はこのことが判りにくい本でもある。

上の目的が、プログラマにおける、ひとつの実用的な関心だったとして、この本は、どうも、それは副次的なことで、それより、各アルゴズムにおける分割可能性や、論理性、処理スッテプ数(計算時間)の関心が主のようでもある。何々は何々ができるとかの、数学的な定理の証明が主眼のようである。むろんそうだとして、これはとても重要なことで、この本に書いてあるアルゴリズムを拝借する上でも、貴重な安心でもある。アルゴリズムの品質に関わる。

多角形の三角形分割については、他書もあるが、穴あきになると、切り込みを入れて、穴あきでない多角形に分割して処理するですませる書籍が多い。しかし、これは、ほとんど、解決になっていない。人間の直観だから、そのような切り込みを入れることが容易なのであって、任意の与えられた穴あきの多角形を、コンピュターが人間の直観の力を借りずに、それを行うことは容易ではない。複数の穴の切り込み線が重なったら、切り込み線が他の穴を横断したらとか様々な問題を解決しなければならないからだ。どんな場合でも、コンピューターによる破たんのないアルゴリズムを、こうした本の内容からだけで、導き出すことは困難きわまりない。購入するだけの価値はない。

この本の、3章における、単純な多角形の定義を確認しておく。

「単純な多角形(simple polygon),すなわち自己交差しない閉じた多角形チェインで囲まれた領域だけを扱うことにする。したがって、領域に穴があってはならない」

とある。

3章 多角形の三角形分割の冒頭にこれがあるので、穴あきこそに興味がある者にとっては、いきなり落胆なのであるが、前回述べたように、実は、示されたアルゴリズムそのものは、穴あきでも、(たぶん)ちゃんと三角形分割できてしまうことが、3章の終りぐらいで、言い添えられているのである。

おそらく、穴あきでも、三角形分割はできるのだが、計算時間(処理ステップ)の議論ができないので、この本では、こんな記述の構成になっているのだと思われる。

可能性は高くないが、ひょっとしたら、自己交差も実は、分割する分には問題ないかも知れないのである。そんなことも、自分で注意しながら読まなくてはならない本ではある。自己交差はさすがに、無理だったとしても、自己交差を考える上では、良い訓練になるだろう。

間違っている可能性があるが(いつもそうであるように、後で直す可能性があるが)

単純な多角形(simple polygon),とは、自己交差がない、穴のない多角形ではあるが、凸多角形である必要はない。凹多角形でも良い訳だ。

我々は、凸多角形の三角形分割は容易で、凹多角形はそうでないことを知っているから、耳を切り取るなど、凹多角形をまず、凸多角形に分割しようと試みがち(実際そのような書籍も多い)だが

それより、まず、単調な多角形(それが凹多角形であっても)に分割した方が、単調な多角形は凸多角形のように、三角形分割しやすいので良策である。しかも、それは、(確認はしていないが、自己交差はともかく、)穴あきでも、計算量、計算時間の議論はともかく、通用する策である。という内容が

コンピュータ・ジオメトリ 計算幾何学:アルゴリズムと応用

の中に書かれている訳だ。

さてこの本が、私にとって良い本になりそうなのは、穴ありの凸でない三角形分割をものにできた後に、順序は逆になるが、

2.4の ブール演算(地図重ね合わせアルゴリズム) に進めることにある。この手もなかなか他に良書がない。

プログラムの順序上は、このブール演算で、所定の穴あき、非凸多角形を生成してから、その各々を三角形、分割するという手順が目論められるのだ。

| | コメント (0) | トラックバック (0)

2011年4月 9日 (土)

穴あき非凸多角形の三角形分割アルゴリズム・勉強の戦略

このブログ。検索フレーズランキングを見ると、穴あき凸多角形の三角形分割アルゴリズムでアクアセスして頂いているようだ。

個人的には、もし、これを一生けん命勉強しようとするなら、

コンピュータ・ジオメトリ 計算幾何学:アルゴリズムと応用 近代科学社

M。ドバーグ他 著 浅野哲夫 訳

を熟読してからになりそうだ。かなり私の目的にあっているし、今のところこれ以上のものを見つけていない。

第3版 2010年2月28日 初版1刷 が手元にある。

これの発行を知らなかったので、

2000年1月15日 初版発行 2001年9月30 初版第2刷発行

も手元にある。これを2000年版と言わせて頂く。

さらには、

Springer の

Computational Geometry Third Edition

                                                          2008,2000,1977

も手元にある。

キンドルでは Second Edition を購入した(これしかなかった)。

さて、これら文献で、私の興味を満足させる、戦略だが、

まず、邦訳2000年度版の72ページ

第3章 多角形の三角形分割 3.3 単調な多角形の三角形分割

において

これまで、単純多角形を三角形分割を方法を見てきたが、穴を含む多角形についてはどうだろう。そのような多角形も容易に三角形分割できるだろうか。答えはイエスである。事実、ここまで見てきたアルゴリズムは穴を含む多角形についても正しく動作する。多角形を単調な部分に分割するアルゴリズムのどの部分でも多角形が単純であるという事実は使っていない。

第3版だと、64ページ、第3章3節にある。

とあるので、 俄然、こころ強いのである。この本を勉強すれば、穴あきは、とりあえず、解決できそうだ。後はコーディングあるのみか?

自己交差の問題は残るが、まあ、それは、後に残しておいても良いだろう。

ちなみに、この記述の後、

高速のアルゴリズムを開発するのに確率化(randomization)が非常に良い道具であることが分かっているが、これについては、第4、6、9章で説明する。

と2000年度版、3.4 文献と注釈、74ページにある。同様の記述は第3版にもある。

高速化は実用的に、大変重要である。ただし、私にはまだ、こうした高速化、最速化の興味が、実用性なのか、純数学的興味なのかの判断はない。

扱う、三角形分割したいデータの規模、複雑さによるかとも思う。

コーディングして、走らせてみて、なんぼのもん、というのが私の今の考えである。

ふと、思ったのだが、私の三角形分割への興味は、それで、Java3DやX3D、VRMLあるいはRadiance(例えばPovRayの描画原理に関連した形状記述方の違いをまだ理解していないが)などで、描画させることにある。(実はこれを、データ・コンバータ的に統合したい)

とすれば、分割高速化もさることながら、どれだけ、少ない、大きな三角で分割するかという評価も重要になりそうだ。三角形の面積の二乗和を三角形の個数の二乗で除した値が大きいほど良いなどが、考えられないかと思う。(たぶん、意義はともかく、この具体記述には、意味がないか、間違っている。2011/4/10)

      

| | コメント (0) | トラックバック (0)

2011年3月13日 (日)

感謝しよう 応援しよう 称えよう メルトダウンと戦う方々を

感謝しよう 応援しよう 称えよう メルトダウンと戦っている方々を、戦った方々を。

このみんなの気持ちを伝えたい。

信じよう、彼らの懸命を。

勝利しても、その過程での放射能拡散はある。

近くの方々は避難すべき。

しかし、メルトダウンしたら、日本中どこに逃げても無駄だ。

我々は、彼らに命を預けている。

感謝しよう 応援しよう 称えよう メルトダウンと戦っている方々を、戦った方々を。

今後の生活より、今後の国民、世界の人々の命、健康の方が先決、重要だ。

確実にメルトダウンを止めることを応援しよう感謝しよう。

その炉に再度、灯をともすことを躊躇なく放棄する、現場の判断に感謝しよう、それを、応援しよう

現場は、営利企業とししての、経済活動継続、事業存続への甘い期待をはねのけて欲しい。

担っているのは、会社、官庁の期待、メンツではない。国民の願いである。

感謝しよう 応援しよう 称えよう メルトダウンと戦っている方々を、戦った方々を。

今、必要なのは、知りたがることではない、現場を信じる、現場で懸命な方々への、応援と感謝の気持ちだ。

我々は、後で現場の方々に、あのとき、ああすれば、こうすれば、を言うつもりはない、誰にも言わせない。

現場の献身・勇気を信じ、感謝するのみだ。メルトダウンを回避してくれれば、その不安をとり除いてくれれば、ゼロからの再生は、どんなにつらくても、われわれ日本人ひとりひとりの、務めだ。

未来をつなげてくれている、現場の方々の勇気に感謝しよう、応援しよう。

15日、未明12:30 福島原発1、3号とつづいて2号機

東電記者会見、危機的、記者会見の彼らは完全に壊れている。

現場の英雄達を頼るのみ

東電管理職に原発を所有させるのは、間違いだった。人類が原発を所有するのは間違いだった。

組織としての東電はもう使えない状態だ。

現場技術者は、全て東電の社員であることをやめて、緊急政府直轄で雇用して身分を保障されるべきだ。全権を自衛隊に与え、彼らを協力させるべきだ。

東電はいらない

| | コメント (0) | トラックバック (0)