lib/src/jp/nyatla/nyartoolkit/core/utils/NyARDistMap.java

   1 /* \r
   2  * PROJECT: NyARToolkit(Extension)\r
   3  * --------------------------------------------------------------------------------\r
   4  * The NyARToolkit is Java edition ARToolKit class library.\r
   5  * Copyright (C)2008-2009 Ryo Iizuka\r
   6  *\r
   7  * This program is free software: you can redistribute it and/or modify\r
   8  * it under the terms of the GNU General Public License as published by\r
   9  * the Free Software Foundation, either version 3 of the License, or\r
  10  * (at your option) any later version.\r
  11  * \r
  12  * This program is distributed in the hope that it will be useful,\r
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15  * GNU General Public License for more details.\r
  16  *\r
  17  * You should have received a copy of the GNU General Public License\r
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.\r
  19  * \r
  20  * For further information please contact.\r
  21  *      http://nyatla.jp/nyatoolkit/\r
  22  *      <airmail(at)ebony.plala.or.jp> or <nyatla(at)nyatla.jp>\r
  23  * \r
  24  */\r
  25 package jp.nyatla.nyartoolkit.core.utils;\r
  26 \r
  27 import jp.nyatla.nyartoolkit.core.types.NyARIntPoint2d;\r
  28 \r
  29 /**\r
  30  * このクラスは、距離マップを利用した、頂点集合同士のマッチング処理機能を提供します。\r
  31  * 2つの点集合同士を比較して、集合の各点同士の距離が最も近くになる組み合わせを計算します。\r
  32  * <p>アルゴリズム - \r
  33  * 2つの点集合の総当たりの距離マップを作り、その距離が小さいのものから順に抽出することで、\r
  34  * 其々の点の移動距離が最小になる組み合わせを計算します。\r
  35  * </p>\r
  36  * <p>使い方　-\r
  37  * このクラスは、まず距離マップを作るために距離値をセットして、次に組み合わせを得る手順で使います。\r
  38  * 距離マップには行と列があります。列を基準値、行を比較値として、その距離値を格納します。\r
  39  * 行と列の距離マップを作り終えたら、組合せを計算します。\r
  40  * <ol>\r
  41  * <li>{@link setMapSize}関数で、マップサイズ（比較する頂点数）を設定する。\r
  42  * <li>{@link #setDist},または{@link #setPointDists}で、距離マップに全ての値を書き込む。\r
  43  * <li>\r
  44  * </ol>\r
  45  * </p>\r
  46  */\r
  47 public class NyARDistMap\r
  48 {\r
  49         /** 処理用のデータ型*/\r
  50         protected class DistItem\r
  51         {\r
  52                 public int row;\r
  53                 public int col;\r
  54                 public int dist;\r
  55         }\r
  56         /**　距離マップ用の配列*/\r
  57         protected DistItem[] _map;\r
  58         /**　ワーク変数*/\r
  59         protected int _min_dist;\r
  60         /**　ワーク変数*/\r
  61         protected int _min_dist_index;\r
  62         /**　ワーク変数*/\r
  63         protected int _size_row;\r
  64         /**　ワーク変数*/\r
  65         protected int _size_col;\r
  66         /**\r
  67          * コンストラクタです。\r
  68          * マップの最大サイズを指定して、インスタンスを作成します。\r
  69          * @param i_max_col\r
  70          * マップの最大列数\r
  71          * @param i_max_row\r
  72          * マップの最大行数\r
  73          */\r
  74         public NyARDistMap(int i_max_col,int i_max_row)\r
  75         {\r
  76                 this._min_dist=Integer.MAX_VALUE;\r
  77                 this._min_dist_index=0;\r
  78                 this._size_col=i_max_col;\r
  79                 this._size_row=i_max_row;\r
  80                 this._map=new DistItem[i_max_col*i_max_row];\r
  81                 for(int i=0;i<i_max_col*i_max_row;i++){\r
  82                         this._map[i]=new DistItem();\r
  83                 }\r
  84         }\r
  85         /**\r
  86          * この関数は、マップのサイズを指定します。\r
  87          * 値は初期化されません。\r
  88          * @param i_col\r
  89          * 新しい列数。\r
  90          * @param i_row\r
  91          * 新しい行数。\r
  92          */\r
  93         public void setMapSize(int i_col,int i_row)\r
  94         {\r
  95                 this._size_row=i_row;\r
  96                 this._size_col=i_col;\r
  97         }\r
  98         /**\r
  99          * この関数は、列と行を指定して、距離値1個をマップにセットします。\r
 100          * <p>注意 -\r
 101          * このAPIは低速です。性能が必要な時は、{@link #setPointsDists}を参考に、一括書込みする関数を検討してください。\r
 102          * </p>\r
 103          * @param i_col\r
 104          * 列のインデクスを指定します。\r
 105          * @param i_row\r
 106          * 行のインデクスを指定します。\r
 107          * @param i_dist\r
 108          * その行と列の距離値を指定します。\r
 109          */\r
 110         public void setDist(int i_col,int i_row,int i_dist)\r
 111         {\r
 112                 this._min_dist_index=this._size_col*i_row+i_col;\r
 113                 DistItem item=this._map[this._min_dist_index];\r
 114                 item.col=i_col;\r
 115                 item.row=i_row;\r
 116                 item.dist=i_dist;\r
 117                 //最小値・最大値の再計算\r
 118                 if(i_dist<this._min_dist){\r
 119                         this._min_dist=i_dist;\r
 120                 }\r
 121                 return;\r
 122         }\r
 123         /**\r
 124          * この関数は、２つの座標点配列同士の距離値を一括してマップにセットします。\r
 125          * <p>\r
 126          * 実装メモ - \r
 127          * 点のフォーマットが合わない実装されている場合は、この関数参考にオーバーロードしてください。\r
 128          * </p>\r
 129          * @param i_vertex_r\r
 130          * 比較する頂点群を格納した配列。\r
 131          * @param i_row_len\r
 132          * i_vertex_rの有効な要素数\r
 133          * @param i_vertex_c\r
 134          * 基準となる頂点群を格納した配列\r
 135          * @param i_col_len\r
 136          * i_vertex_cの有効な要素数\r
 137          */\r
 138         public void setPointDists(NyARIntPoint2d[] i_vertex_r,int i_row_len,NyARIntPoint2d[] i_vertex_c,int i_col_len)\r
 139         {\r
 140                 DistItem[] map=this._map;\r
 141                 //distortionMapを作成。ついでに最小値のインデクスも取得\r
 142                 int min_index=0;\r
 143                 int min_dist =Integer.MAX_VALUE;\r
 144                 int idx=0;\r
 145                 for(int r=0;r<i_row_len;r++){\r
 146                         for(int c=0;c<i_col_len;c++){\r
 147                                 map[idx].col=c;\r
 148                                 map[idx].row=r;\r
 149                                 int d=i_vertex_r[r].sqDist(i_vertex_c[c]);\r
 150                                 map[idx].dist=d;\r
 151                                 if(min_dist>d){\r
 152                                         min_index=idx;\r
 153                                         min_dist=d;\r
 154                                 }\r
 155                                 idx++;\r
 156                         }\r
 157                 }\r
 158                 this._min_dist=min_dist;\r
 159                 this._min_dist_index=min_index;\r
 160                 this._size_col=i_col_len;\r
 161                 this._size_row=i_row_len;\r
 162                 return;\r
 163         }\r
 164         /**\r
 165          * この関数は、現在の距離マップから、col要素に対するrow要素の組合せを計算します。\r
 166          * colに対して適したrow要素が見つからない場合は、o_rowindexの該当要素に-1を設定します。\r
 167          * この関数は内部データを不可逆に変更します。計算後は、距離マップの再セットが必要です。\r
 168          * @param o_rowindex\r
 169          * 組合せを受け取る配列です。\r
 170          * col[n]に対するrow[m]のインデクス番号mを、o_rowindex[n]に返します。\r
 171          */\r
 172         public void getMinimumPair(int[] o_rowindex)\r
 173         {\r
 174                 DistItem[] map=this._map;\r
 175                 int map_length=this._size_col*this._size_row;\r
 176                 int col_len=this._size_col;\r
 177                 //[0]と差し替え\r
 178                 DistItem temp_map;\r
 179                 temp_map=map[0];\r
 180                 map[0]=map[this._min_dist_index];\r
 181                 map[this._min_dist_index]=temp_map;\r
 182                 for(int i=0;i<o_rowindex.length;i++){\r
 183                         o_rowindex[i]=-1;\r
 184                 }\r
 185                 if(map_length==0){\r
 186                         return;\r
 187                 }\r
 188                 //値の保管\r
 189                 o_rowindex[map[0].col]=map[0].row;\r
 190                 \r
 191                 //ソートして、0番目以降のデータを探す\r
 192                 for(int i=1;i<col_len;i++){\r
 193                         int min_index=0;\r
 194                         //r,cのものを除外しながら最小値を得る。\r
 195                         int reject_c=map[i-1].col;\r
 196                         int reject_r=map[i-1].row;\r
 197                         int min_dist=Integer.MAX_VALUE;\r
 198                         if(1>=map_length-col_len){\r
 199                                 break;\r
 200                         }\r
 201                         for(int i2=i;i2<map_length;){\r
 202                                 //除外条件？\r
 203                                 if(map[i2].col==reject_c || map[i2].row==reject_r){\r
 204                                         //非検索対象→インスタンスの差し替えと、検索長の減算\r
 205                                         temp_map=map[i2];\r
 206                                         map[i2]=map[map_length-1];\r
 207                                         map[map_length-1]=temp_map;\r
 208                                         map_length--;\r
 209                                 }else{\r
 210                                         int d=map[i2].dist;\r
 211                                         if(min_dist>d){\r
 212                                                 min_index=i2;\r
 213                                                 min_dist=d;\r
 214                                         }\r
 215                                         i2++;\r
 216                                 }\r
 217                         }\r
 218                         //[i]の値の差し替え\r
 219                         temp_map=map[i];\r
 220                         map[i]=map[min_index];\r
 221                         map[min_index]=temp_map;\r
 222                         //値の保管\r
 223                         o_rowindex[map[i].col]=map[i].row;\r
 224                 }\r
 225                 return;         \r
 226         }\r
 227 }