質問: 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか? 条件は次の通りです 1.集合Pはあらかじめ、任意の順番でソートしておける 2.点pの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか? みなさんのアイディアを貸してください
回答: こういうのはどうでしょう。 集合pの座標値の小数点(任意の点pの座標も含めて)が例えば最大下三桁だとする。 集合pのX座標を1000倍した集合Aをつくる。 集合pのY座標を1000倍した集合Bをつくる。 AもBも整数で昇順ソート済みとする。 任意の点p(x,y)を各1000倍したものを(X,Y)とする。 Marginをm、1000倍したのをMとする。 集合Aから、X-M<=A<=X+Mとなる要素を抜き出す。AAとする(例えば3個とする) 同様に集合Bから、Y-M<=B<=Y+Mとなる要素を抜き出す。BBとする(例えば3個とする) AAの要素とBBの要素の直積(3×3で9個)をとり、各1000で割るとそれは集合pのX、Y座標となる。 これは任意の点pと集合pの要素の距離ではなく、X座標のMarginとY座標のMarginが独立にmとした場合に要件を満足するようと思いますが、どうなのでしょうか。