趣味

2013年1月11日 (金)

ビッグデータ競争元年に思う ロングテールの中にいろ 日経の広告を見て思う

日経新聞の電子版を紙面ビュアーで読んでいて、ハーバードビジネスレビューというマネジメント誌の広告で、ビッグデータ競争元年というのが目にとまった。

何事も過ぎたるはおよばざるがごとしと言うか、過去に、何でもかんでもマーケティングと言って、役に立つ面を否定しないものの、それで全てがクリアーになる訳でもないことは、多くの人間が学習したところだろう。

ビッグデータ競争もその類かとも思う、すなわち、例によって、さほどのことはないよという気持ちと、別のところで危惧を感じるのは私だけではないだろう。

というのは、ここには、そのアイデアの卓越性・優劣以前に、寡占化、生データの独占化、個人のプライバシーの侵害という、悪夢のような暗黒の世界の広がりを見るからだ。そのことに気付いている人も少なくないと思われる。

もうひとつの危惧は、この広告にもあるように、データ・サイエンスティストほど素敵な仕事はない、といううたい文句だ。若い才能を呼びこむに、そこが新たらしい非創造的な分野に、いとも簡単に堕落して、創造的文化の可能性が衰退していく種となっていくように思えるのだ。

いろんな意味で、このビッグデータ競争の潮流から身を守っていくことに備えておくべきだろう。それは、ビッグデータ競争に溺れていく者を勝者などにしない営みの積み重ねでもある。

ビッグデータ競争が注目されるより前に、ロングテールと言うのが、はやった。古来より良質なものは、へんてこなものと同様にロングテールであることは皆知っている。人間には様々な水準があるからだ。文化・文明とは先覚者とも言うがロングテールがひぱって来たとも言える。メジャーはのろのろとロングテールの後を追って行くのだ。

ビッグデータ競争というのは明らかに、インターネットなどのITの発達と不可分なのだが、ロングテールが過去に増して注目されたのもまた、インターネットなどのITの発達がある。私はビッグデータ競争よりロングテールとインターネット文化の方に、有意義な未来のパラダイムがあると思う。

ひとりひとりが、良きロングテールであろうとすること、すなわち自己の個性を生かさんとするとき、所詮ビッグデータ競争がもたらすものなど三流、二流ではないかと予感するのである。であるからして、人類の進歩の可能性としてビッグデータ競争にかまけることなど、相当に無駄な足踏みではないかと思うのである。

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

2012年6月 4日 (月)

がっかりフジテレビオンデマンドがアクトビラ離脱のTSUTAYA TVへ

液晶テレビでアクトビラをそこそこ利用している。主に韓国のMUSIC BANKを観るためだ。フジテレビの見逃し番組を観たいと思ったら、結構古い話なのだが、TSUTAYA TVがアクトビラを離脱して、フジテレビオンデマンドがアクトビラで観れなくなっていた。

仕方がないので、この液晶テレビでTSUTAYA TVにアクセスの手続きのし直しである。TSUTAYA TVがアクトビラを離脱する前の液晶テレビなので、アクセスできない訳ではないのだが、最近のアクトビラ対応のブロードバンド対応デジタルテレビと違ってやや面倒だ。

アクトビラを利用するとき、パソコンであらかじめ、観たい番組をマイページに登録している。私に言わせると、そうでないととても使いものになるものではない。液晶テレビ上のアクトビラの操作画面は、観たいコンテツを検索する上でもパソコンに慣れた者には耐えがたい不便なものだ。所詮テレビであってパソコンでは無いのだから仕方ないが。

TSUTAYA TVであっても私にはそうである。従って、パソコンでTSUTAYA TVの観たい番組を検索してマイページに登録できる必要がある。しかし、そう思いたってから、この2日ばかりTSUTAYA TVのサイトは「PCサイトで提供しておりました会員情報機能は現在改修中のためご利用いただけません」なのである。いつまでそうなのか、プレスリーリス・お知らせを見ても音沙汰無である。

さぞ他のユーザーの憤懣も大きかろうとググってみても、そんな声は見つからない。みんな我慢強いのか、不思議に思う。ただ、他の事で、TSUTAYAの事業に批判が結構あるのを知ってしまった。中にはブラック企業だとしているものもある。

TBSオンデマンドはアクトビラとTSUTAYA TVの二股で結構なことだが、何故フジテレビオンデマンドはアクトビラを嫌ってTSUTAYA TVと癒着してしまったのだろうか?

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

2011年8月22日 (月)

ペインター9.5 intuous3 ドライバー直った

ペインター Corel Painter は12まで出ているようだが、私は8から9.5にしたまま、ほとんど使っていなかった。

ワコム WACOM の ペンタブレット intuos3 を持っているのだが、久しぶりにセットアップしても、タブレットドライバーが機能してませんとかのメセージが出て、筆圧、傾き、軸回転角(マーカ)ペンとか全然感知しなくてまいった。WindowXPでだ。

ネットで調べて、ドライバーをダウンロードして再インストールしたが直らない。結果初歩的なミスだったようだ。ダウンロードしたドライバーファイル、デスクトップに置いてインストールしたのが良くなかったみたいだ。ドライブCに移動してドライバーをインストールしたら回復した次第。

| | コメント (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)

より以前の記事一覧