Есть большой параллелепипед в d-мерном дискретном пространстве. Его разбивают на некоторое кол-во подобластей параллелепипедов (разных размеров), маленькие параллелепипеды не пересекаются, а в большом не остается дыр.
Теперь нужно организовать поиск, т.е. по набору из d целых чисел (точка в d-мерном пространстве) найти соотв. маленький параллелепипед. Поиск должен работать как можно быстрее, актуальные значения d=2,3 число подобластей от сотен до десятков тысяч.
Попробовал перебором - дурацкая затея, и вроде как есть ощущение что можно сюда прикрутить std::map. У меня есть объект индекса indx<D> (точки в этом самом пр-ве) из D чисел, для которого есть правильная std::less
namespace std{
template< class T > struct less;
template< int D > struct less<aiv::indx<D> > {
bool operator()( const aiv::indx<D>& x, const aiv::indx<D>& y ) const {
for( int i=D; i>=0; i-- ){
if( x[i] < y[i] ) return true;
if( x[i] > y[i] ) return false;
}
return false;
}
};
};
Можно сделать структуру
struct indx_cube{
indx<D> min, max;
inline bool operator < ( const indx_cube& other ) const {
return std::less< indx<D> >()( max, other.min );
}
};
и юзать indx_cube в качестве ключа map. Вот теперь нападает утренний тупняк - вроде как понятно, что можно таким образом накидать в map параллелепипедов. Но будет ли работать поиск? Скажем мне нужно найти что то по точке indx<D> I. Если я в качестве ключа передам indx_cube(min=I,max=I), че нить разумное получится? Что бы точка попала в подобласть должно быть покомпонентное
min[i]<=I[i] && I[i]<max[i]
Че та не хватает воображения;-(
