読者です 読者をやめる 読者になる 読者になる

C#ATIA

↑タイトル詐欺 主にCATIA V5 の VBA

端点一致を探る、組み合わせテスト4

こちらの続きです。
端点一致を探る、組み合わせテスト3 - C#ATIA


前々回 "このアルゴリズムでの問題点も、ある程度認識してはいるつもり" と
書いたのですが、これについて自分なりの解釈と方向性だけ示しておきたいと
思います。

このアルゴリズムで最大の効果を発揮するのは、空間内に出来る限り均一に
対象物(今回は端点)が分散した状態です。
以前、"モートン順序を利用した線形8分木" について検索したところ、あるサイトで
弱点を指摘している方がいました。

仮に端点が100個あるとします。
f:id:kandennti:20161214123455p:plain
上記の様に空間を分割した際、紫の部分に1個有り、残りの99個が
緑の部分に有った場合は、緑色の部分では総当りに近い状態になります。
紫部分がとてつもなく離れていた場合、空間の分割レベルを上げても
総当りに近い状態が避けられない事になってしまいます。

そこで考えたのが、
f:id:kandennti:20161214123503p:plain
紫部分は空間内の端点数が十分少ないので「衝突オブジェクトリスト」として
登録します。
残りの緑部分からLv0の空間を再度設定し、この新たな空間を分割するように
すれば、少ない回数の空間分割で総当りを避け1つの空間内の端点数を
少なく出来るのではないかと思っています。
その際、一度に行う空間分割レベルは1~2程度でも恐らく十分だろうとも
感じてます。

これをコード化出来るかな? 非再帰で・・・。