[HOME] → [発明]

計算幾何学について

元々は、甘利俊一氏などの情報幾何学という分野に興味があって、間違って、計算幾何学の本を買ったのが最初です。
国民的美少女コンテスト用の画像を作ったときに使ったモーフィングは、単純なアフィン変換によるものだったわけですが、この方法では、微分したら不連続になってしまいます。実際に見た目では問題無いのですが、アルゴリズムとしてはダサいものです。その時に、いろいろ考えていて、思い付いたと錯覚したり、色々していたのですが、何のことはなく、下の1番の本の中に書いてありました。実際には、時間がかかりすぎるものだったのですが、計算幾何学の分野には、僕が考えるような問題の答えがいっぱい詰まっていると認識しました。

pag1tetoで、ドローネ４面体(3次元でもドローネ三角形と呼ぶのが正しいのかも知れない)パッチを使うという辺りで、計算幾何学に切実な必要性が出てきたのですが、3次元のドローネ三角形パッチの方法については載っていなくて、しばらくいろんな本を探しました。
減色を含めて、ベクトル量子化圧縮の問題は、人口の分布に応じて、郵便ポストをどんな風に配置すれば、すべての人の歩く距離の二乗和が最小になるか？ みたいな地理的最適化問題と同じなので、減色時の代表色の選択の部分は、同じアルゴリズムになります。ただし、必要な精度と、使える時間が異なります。計算幾何学の分野で良く使われているバケット法などのアルゴリズムを使うよりは、僕がpag1tetoで使っているアルゴリズムの方が、高速なはずです。
その結果、例えば、TSPも、計算幾何学の問題ですが、うまく応用できました。他の計算幾何学の問題に対しても適用できるはずだと思っていますが、今のところ時間が取れません。計算幾何学の問題に限らず応用範囲は広いと思っています。

発明ディレクトリ