点集合から矩形に含まれる点部分集合を抽出する（象限分割法）

始めに

前置き

　このアルゴリズムは、１９８９～１９９１年に受注したシステムのためにわたしが独自に構築したものですが、現在では一般的な４分木の１種と認識しています。
　また、本ブログのメインテーマは巡回セールスマン問題となりますが、本記事の象限分割法と巡回セールスマン問題を比較したときの計算量の違いや解法の難度の要因を模索していました。
　その要因は、一目瞭然とも言えるのですが、逆にその要因を厳密に特定できれば、巡回セールスマン問題の解法に役立つのではないかと考えたのです。
　結論は未だにでていませんが、キーワードは「関係」と「組み合わせ」ではないかと思っています。

概要

　対象座標系は２次元直角座標系とします。
　点集合P=｛p1.p2.p3...,pn｝としたとき、検索条件を｛ｘ1、ｘ2、ｙ1、ｙ2｝で示される矩形情報とします。
　出力は、検索矩形内に内包される点集合Pの部分集合PPとなります。

応用例

　①　検索条件矩形を画面または、Windowとします。それぞれの検索条件矩形の座標は、点集合Pの座標系に変換します。
　②　マウスなどでクリックしたとき、そのクリックした点に一定の幅を持たせ検索条件矩形とします。①と同様に座標変換が必要です。これにより、クリックした点に近い点がいくつか得られます。

計算量

１点の抽出（クリック点に最も近い点など）

　点集合の要素数をNとしたとき、１点を抽出（検索）する場合を考えます。
１点を抽出（検索）する場合の検索条件は、できるだけ狭い矩形となります。
　但し、矩形が狭すぎると０点の抽出となる場合もあります（抽出できないケース）。
　m点を抽出したとき、検索点とm点の距離を計算し最も近い点を検索結果とします。

AVL木

　２分探索木のAVL木の考え方が４分探索木にも適用されます。
底となるノードとルートとの距離が平均的であることが求められます。
これを平衡木と呼びます。
２分探索木の場合、距離の差を１以内とすることが可能ですが、4分探索木の場合、それは難しいように思われます。
筆者は4分探索木の平衡木化の考察を行っていないので、この考察を行うことも面白いかもしれません。

計算量

　４分探索木が平衡木であると仮定すると、検索回数（計算量）F=LogN（低は４）に近くなります。
但し、ベースとなる点集合の配置座標などにより、厳密な計算量は現在計算できません。

アルゴリズム

アルゴリズムの概要

　①　点集合Pから４分木を生成
　②　検索条件矩形に内包される点集合を抽出

「４分木を生成」のアルゴリズム

図を参照ください。

　①　点集合Pからｘとｙの最小値と最大値を取得
　②　①で取得した値に僅かな幅を持たせ、点集合世界を設定
　　　（点集合Pの全ての要素が点集合世界に内包されることになります）
図のボタン［アルゴリズム　ステップ１］をクリックしてください。
　　　上図の点LBとRTが点集合Pのｘとｙの最小値と最大値となります。
　　　幅Wを加算ないしは減算した点RminとRmaxが点集合世界となります。
　　　尚、それぞれの点は左下隅、右上隅となります。
　③－１　点集合から任意の点を点集合世界に投入します。
　　　随時、ｎ点まで投入を繰り返します。
　　　つまり、逐次投入となります。
　　　尚、ここでは２点までを例として示します。
図のボタン［アルゴリズム　ステップ２、３］をクリックしてください。
　　　P１を投入したとき、点集合世界はⅰ～ⅳの領域に分割されます。

　　　Rminの座標を（Rminx,Rminy）
　　　Rmaxの座標を（Rmaxx,Rmaxy）
　　　P1の座標を（P1x,P1y）
　　　としたとき、

　　　ⅰ～ⅳの領域は次の座標域で表現できます。
　　　ⅰ：P1x-Rmaxx,P1y-Rmaxy
　　　ⅱ：Rminx-P1x,P1y-Rmaxy
　　　ⅲ：Rminx-P1x,Rminy-P1y
　　　ⅳ：P1x-Rmaxx,Rminy-P1y

　　　これを４分木で表現します。
　　　木構造のルートは、P1（第１の投入点）となります。
　　　そして、P1はノードとなり点集合世界の域座標を所有します。
　　　また、P1はⅰ～ⅳの座標域を持つ４つの分枝を所有します。
　③－２　２点目（P2）を投入します。
　　　P2はP１で構築された領域のⅳに存在するものとします。
　　　P2はP1の領域ⅳを４つの領域に分割します。
　　　　これを４分木で表現します。
　　　P2は木構造のルートP1の領域ⅳの分枝に所属します。
　　　このとき、領ⅰ～ⅲの分枝は要素を持ちません。
　　　また、P２はⅰ～ⅳの座標域を持つ４つの分枝を所有します。
　④　注意点
　　　逐次投入していく点が座標域の境界上（軸上）に存在するとき、どちらの座標域に属するかという問題については、ルールを決めておきます。
　　　このルールが検索時と合致していれば問題は起こりません。

検索のアルゴリズム

　①　検索条件は矩形の左下隅と右上隅の座標になります。
　②　検索する順番は木構造の上位レベルから行います。
　③　検索条件矩形が木構造のノードの分枝のいくつかにまたがるときは、その全ての分枝を捜査します。
　④　座標域の境界上（軸上）に検索条件矩形が接するときは、木構造で設定したルールに従います。全てを捜査しても問題ありませんが、検索速度が少し遅くなります。

アプリのプロデュース（produce）とその計画

プロデュースの意味

　英語の produceの本来の意味は「生産する」「作り出す」ということらしいです。
まぁ、それは大きな問題ではなくて、アプリの開発のことを何と呼ぶことにしようかという単純な思いから調べていた結果見つけたものです。

　日本では、プロデューサーとか聞くと偉い人のようなイメージがあって、単純に何かを作り出す人というイメージではありませんね。

　例えば、TV番組のプロデューサーは番組に何らかの価値を込めて放映します。
そして、必ずそこには視聴率という評価がつきまといます。

　当たり前のことですが、わたしはアプリも同じようなものじゃないかと考えてしまいました。
アプリの開発をアプリをプロデュースすると呼ぶことにして、第一歩を踏み出したような気分になったわたしですが、第２歩目が難しいですね。

ミリオンヒットを考える

　世の中には何百万ダウンロードというミリオンヒットのアプリがいくつもあるようですね。
どうしてミリオンヒットになったのかと考えるとよくわかりません。

　ただの運なのかと考えるとどうやらそうでもなさそうです。
でも、これはという決め手になる共通性は見つかりません。

　１つだけわかったのは、必ずどこかのストアで公開しているということです。
当たり前のことですが、自分のアプリをプロデュースしてどこかのストアで公開するということが絶対条件のようです。

計画

　十分な元手のないわたしは副業をしながらアプリをプロデュースしなければなりません。
そして、アプリの公開ルートは次の３つであると認識しています。

・WINDOWS　PCで開発⇒WINDOWSのストアで公開
・WINDOWS　PCで開発⇒アンドロイド・スマホで公開
・MAC　PCで開発⇒iOS・スマホで公開

　ところが、わたしが持っているのは、WINDOWS　PCとiＰadだけです。
iＰadを持っている理由は前の３記事くらいに書いてあるので笑ってやってください。

　iＰadを持ってよかったのは、この記事が書けていることくらいでほとんど役に立っていません。
でも、この記事を書いているということは、それだけ学んだということだと思います。
（高い授業料だったのかな～）

　で、３つのルートのためにMAC　PCや２種類のスマホを揃えたいと思います。
でも、今は無理です。

　いつまでにと考えても答えは出ません。
で、計画が必要となるのですが、その計画も立ちません。

　では、どうするかというと今できる WINDOWSのcromeストアで何かしらやっていこうと思いっています。
全く、計画にもなっていませんね。

アプリのストア

　前記事で保留にした何をアプリストアで販売するのか？の答えは「巡回セールスマン問題」関連となります。

　そこまではよかったのですが、スマホをターゲットとしたアプリの開発は当面お預けとなります。

　理由は、開発環境として調査していた「Monaca」が無料では使えないことがわかったからです。
有料グレードが３段階くらいあって、最高グレードは年会費５万円でした。
「ちょっと待て」となったのは、「Monaca」を調査していた理由がMACの実機が買えなかったからです。
　MAC　BOOKは新品で最低価格１０万くらいです。

結論として「Monaca」は使えないとなった次第です。

さて、それではどうしようかといろいろ調べた結果、わたしのアプリのストアの認識が間違っていたようです。
　前回か前々回か忘れましたが、わたしはアプリとはスマホなどの類で動くゲームのようなミニシステムだと思っていたのです。

ところが、Crome アプリストアを見つけ、Micrososoft のアプリストアも存在するようです。
何も、スマホに拘る必要はなかったのです。

　悔しいのは、先日契約したiPadがしばらく役に立たないことです。
しかし、今年中には役に立てたいと思っています。

今回の調査の結果として、アプリを開発して販売（収益を上げる）するルートが３つできたことになります。

①　WINDOWSパソコンで開発⇒Crome アプリストアで販売
②　MAC　BOOKで開発⇒iPhoneで販売
③　WINDOWSパソコンで開発⇒Androidoで販売

です。

　現在、可能なのは①だけです。
②はMAC　BOOK（１０万円）がありません。
さらには、Appストアで販売するための審査が厳しいようです。
確実に審査に引っかかるのが、アプリはスマホで動くことだそうです。
タブレットで動いてもストアに置いてくれません。
そこで、AUショップに行って尋ねたところ、スマホの契約は月額１万ほどかかるそうです。イタタ
③はAndroidoスマホがありません。

何故、①だけじゃダメなの？の理由はお客さんの数がまるで違うからです。
お客さんの数が増えれば、それだけ収益に繋がる可能性が増えます。

予定では①～③のルートを最悪１年以内に揃えたいと思っています。
途中で頓挫するかもしれません。
他の生活手段がないとアプリ開発だけでは、軌道にのせるまでが大変です。

ところで、今日の午前中にCrome アプリストアにアプリを１つ登録しました。
即興でホームページを作って、それを表示させるアプリです。

まだまだ、収益に結びつきませんが、ルートの１つは確保しました。
参考までに即興のホームページのURLは次です。

巡回セールスマン問題

ここには、Crome アプリストアで「TSP」で検索して巡回セールスマン問題のアプリを起動すれば行くことができます。

さて、②と③のルート構築まで、即興ホームページをアップグレードしたいと思います。
ルートができても、商品が貧弱では売り物にならないでしょうから。

それに関連してこのブログもカテゴリ「TSPの基礎技術」でいくつかの証明などを投稿していく予定です。

アプリの開発へ

　いや～、随分調べたり試したりするのに時間がかかりました。

　で、結論はというと当初描いていた構想は砕け散りました。
どういうことかというと、タブレットで開発することはできないんですね。
構図としては、PCで開発してタブレット（またはスマホ）で試す（動かす）ということになります。

　そのことを知って、愕然としたわたしは足掻きに足掻きました。
何故なら、タブレットが無駄な買い物になってしまうからです。
無駄な買い物となると月々６，５００円の支出は途方もなく重たく感じられます。

　で、いくつかのサポートセンターをたらい回しにされたあげく、ある電話対応のオペさんが、アドバイスをくれました。
「Windows で調べるとできるかもですよ」
　わたしは「なりほど」と思い、いくつかの手法を調べだしました。

　その１つが、MACのOSをWindowsでエミュレートする方法で、そのセットアップに３日くらいかかったのです。
しかし、サクサク動かないし、エラーは多発するしで嫌になって横になって考えてみたら、
「この環境で開発したアプリはストアに出せないのでは？」

　つまり、この環境で開発したアプリを表のストアに並べると、違法行為になるはずだと思いました。
何故かというとわたしはMACのOSを購入していないからです。
闇のルートで手に入れた環境で開発したアプリを表舞台に出すのは、危険だと思いました。

　そこで、Monacaという開発環境を探し出してセットアップ中です。
Monacaは、HTML5とJavaScriptで開発するらしく、CかC++で開発したかったわたしは妥協したことになります。

　その妥協は、HTML5とJavaScriptを学習するという余計な労力を必要としますが、胸をはってストアに並べることができるらしく、
まあ、余計な心配をせずに済みます。

　ということで、開発環境の方向はこれで当面いこうかと思います。

　次なる問題は次の２つです。
①　アプリを開発して、生活できるのか？
②　どんなアプリを開発するのか？

　①は開発環境を調査しているときに得た情報によると、無料アプリにして広告収入で稼ぐという手段がよさそうかなと思いました。そこで、以前登録していたi-mobileを利用しようと思い、このブログにちょっとタグを張り付けて見ました。
　しかし、このブログで広告収入を得ようとは思いません。以前別なブログにこのタグをはったとき、月に７、８円の収入にしかならなかったからです。アプリはダウンロードしてもらえれば、それなりになりそうです。

　そこで、②が問題になってきます。
現段階で予定はありますが、それは次回のブログでということでお願いします。

初めてのApple

　昼の投稿なので、とりあえず「こんにちは～」です。

　そもそも、このブログは趣味で小説（ジャンルはハードSF）を書くために以前作って放置していたものですが、
一転してテーマが『iPadアプリの開発の記録』となりました。

　思い起こせば、１０日前「外出先でもオンラインゲームがしたい～」という不純な動機からAUショップを訪ねたのが始まりでした。
綺麗な女性の店員さんが応対してくれて、「画面の大きさで４種類くらいのタブレットがありますよ」ということで、miniからProまで見せてもらいました。

　気になったのが、OSがiOSだったことです。これがわたしに大きな躊躇（契約しようかな？どうしようかな？）を与えたのです。
というのもパソコンを使い始めてから３０数年ですが、全てがインテル系のCPUだったためです（仕事ではDEC社のVAXなど使っていましたが）。そのため、その日は「検討します」と言って帰ってきました。

　それから、パソコンでiPadの情報を調べていると、意外というか運命というかいくつもの未知の存在が明らかになっていきました。

　わたし本人がどこから書いたらいいのか迷っているので、この記事をお読みになっている方はもっと困惑するかもしれませんが、時系列的に書いて見たいと思います。

　・（わたしは）１０年ほど前まで首都圏で自営あるいは派遣でSEをやっていました。
　・病となって実家に戻ってきたのですが、パソコンは手放せませんでした。
　・数年前にクラウドソーシングなるものを発見しました。
　・そこには、わたしにとって未知なる存在を多く含んだ仕事がたくさんありました。
　・つまり、仕事はあっても手が届かなかったのです。

　さて、未知なる存在とは何かというと、Android、iOs、スマホのアプリ（どうやって開発したらいいのかわからなかったのです）などでした。さらには、多種類のWEB言語が並び、わたしはCやC++で制御や理数系の仕事をしていたのでまるで畑違いでした。

　ほどなく、Android、iOsはスマホのOSであることはわかりましたが、アプリの開発方法は依然わかりません。なにしろ、わたしはスマホを持っていないので（今もですが）、スマホアプリは友人がやっているスマホゲームのことかと思っていたくらいです。ガラケーとパソコンがあればわたしのやりたいことは満たされていたのでスマホは無用だったのです。

　昨年のことですが、数か月の泊まり込みの仕事があったのですが、そこのネット環境は無いにも等しいくらい遅かったのです。思わず、「ISDNじゃないですよね]と失礼なことを聞いてしまいました。ご飯が３食を１食に減らされてもネット環境だけは譲れないわたしは、AUのルータの契約をしました。何故、AUかというと他社の電波が届かなかったためです。ガラケーもDocomoからAUに代えて現在に至っています。

　話が飛び歩いていますが、 AUとのお付き合いはそれが始まりだったということです。そして、２か月ほど前わたしのパソコンに
とんでもない災難が降りかかりました。Windows７を使っていたわたしに、再三にわたって「Windows１０にしませんか～今なら無償ですよ～」というメッセージが流れたのです。おそらく魔がさしたのかメッセージが煩かったのかわたしはWindows１０にヴァージョンを上げました。

　悲劇はそこから始まります。わたしの持つAUのルータは１か月１２Gの制限つきです。Windows７のときは２０％か３０％で済んでいた通信量が、１日で１Gを軽く超えていました。最初はWindows１０へのアップグレードのためかと思っていましたが、いつになっても通信量は減ることはありませんでした。ネットで調べてみるとそれはWindows１０の仕様の問題みたいだったので、詳しく調べもせずに諦めました。諦めたというより半月もたずに制限を超えてしまいました。

　どうしたかというと、固定電話の光回線を使いました。「それなら問題ないだろう」と思われた方は都会に住んでいらっしゃいますね。わたしの実家は光の基地局から遠く遠く離れていて、平均4ｍｂｐｓくらいの通信速度しかでないのです。

　そこで、「タブレットはどうだろうか？」となったわけです。AUのルータはほとんど遊んでいますし。ようやく最初の文章とつながりがでてきましたね。

　ネットで調べていると「swift」という開発言語が、無償で手に入ることを知りました。そして、swiftを理解するためには「Objective-c」や「x-code」を知る必要があるということもわかりました。ネットの説明によるとそれらの開発環境はほとんど無償で、開発したアプリをストアにのせるために年間1万円くらい必要だと理解してますが、間違っているかもしれません。（未知だった「Objective-c」や「x-code」はAppleの開発環境だったのですね。多分）

　この段階で「外出先でもオンラインゲームがしたい～」が「自宅で仕事ができるかもしれない～」に代わって、さて機種選びとなったのでした。

　調べた結果、iPadのタブレットのCPUは「A8」「A8x」「A9x」あるようです。ちなみにわたしはインテル系の8086、80386、80486までのアーキテクチャはいくらか理解していますがモトローラ系と今でもいうのでしょうか？Apple系といった方がいいのでしょうか？それについては全くわかりません。わかりませんが、CPUの性能比をみると「A8x」が手ごろではないかと思いました。

　そこで選んだのが、「Air2」というモデルでした。ちなみにAndroidoで動くタブレットも調べて見ましたが、ハード的なコストパフォーマンスはiPadが上ではないかと思ったのです。

　ところが、家に持ち帰った「Air2」でいつもやっているオンラインゲームをやろうとしたら動かないではありませんか。原因を調べるとそれはFlash Playerにありました。Flash Playerはadobeの製品です。appleとadobeは喧嘩をしているらしく、Flash PlayerはiOSでは動かないそうです。つまり、Flash Playerを使っているゲームはiOSでは遊べないということです。

　何かいい方法はないかと調べて見たら、「puffin」というFlash Playerもどき（エミュレータ―？）のアプリがあってゲームは動き出しました。ところが画面がスクロールしません。調べて見たら「puffin　ブラウザ」を全画面表示にしなければならないようです。「Air2」ではシアターモードでした。

　ここまでは、無料のアプリをダウンロードしていたので問題ありませんでしたが、本筋である「x-code」のIDEアプリは600円でした。そして、支払いに進むとクレジット　カードが必要だと言ってきます。プリペイドでできるはずなのですが、操作方法がわかりません。なにしろ、スマホを含めてパソコン以外の機器を使うのが初めてなので勝手がよくわかりませんでした。翌日AUショップに行って1500円のiTunesカードを買って使い方を教えてもらいました。

　これからダウンロードした「x-code」のIDEを触ってみますが、果たして結末や如何にというところです。