Алгоритм C ++ для разбиения области заданного измерения на части с неперекрывающимися границами

Я хочу иметь алгоритм для разделения области любого данного измерения на подпространства с неперекрывающимися границами.

Например: с двумя измерениями, где нижняя и верхняя границы для каждого измерения заданы следующим образом:

Нижние границы: 1, 1

Верхние границы: 100, 50

Выше представлен 2D-прямоугольник. то есть четыре угловые точки прямоугольника (1-1, 1-50, 100-1, 100-50). Теперь я хочу разрезать на 4 части прямоугольной формы с неперекрывающимися границами, такими как

sub-rect1: (1-1, 1-25, 50-1, 50-25)

подпункт2: (51-1, 51-25, 100-1, 100-25)

подпункт3: (1-26, 1-50, 50-26, 50-50)

sub-rect4: (51-26, 51-50, 100-26, 100-50)

Я надеюсь, вы понимаете, что я хочу. Что я действительно хочу, так это иметь алгоритм C ++, который может работать с любыми измерениями от 1 до 10. Я действительно плох с рекурсивными алгоритмами. Оба рекурсивных или итеративных алгоритма помогут.

ОБНОВЛЕНИЕ: Вот решение, которое я придумал сам. Я публикую его здесь, чтобы в будущем он мог помочь кому-то с такими же потребностями.

/*! To display vector contents... */
std::ostream &operator<<(std::ostream &os, const std::vector<int> &vec)
{
for (int i=0; i<vec.size(); ++i)
os << " " << vec[i];

os << "\n";
return os;
}/*! Takes upper and lower bound as arguments on any dimensions and generate
* subspaces by dividing each dimension into two disjoint parts...
* It works as follows. First we divide each dimension separately into
* two parts (to get 4 points per each dimension).
* Then we combine all permutations of those parts of each dimension.
*/
void Tuner::generateSubSpaces(std::vector<int> &baseLowBound, std::vector<int> &baseUppBound)
{
assert(baseLowBound.empty() == false && baseLowBound.size() == baseUppBound.size());

int dimens = baseLowBound.size();

// first create an array of arrays to hold 4 parts for each dimension....
int **ranges = new int*[dimens];
for(int i=0;i<dimens;++i)
ranges[i]=new int[4];

// variables to handle 4 points for each dimension....
int upp, low, midLow, midUpp;
for(int i=0;i<dimens;++i)
{
low = baseLowBound[i];
upp =  baseUppBound[i];

// there should be atleast two intermediate points to get disjoint ranges
assert(low < (upp-2));

midLow = (low + upp) / 2; // roughly equal division
midUpp = midLow+1;

ranges[i][0]=low;
ranges[i][1]=midLow;
ranges[i][2]=midUpp;
ranges[i][3]=upp;
}

// Now to create all possible combinations, we use this flag array...
int *binFlagArr = new int[dimens];
for(int i=0; i<dimens; ++i)
{
binFlagArr[i] = 0;
}

bool more = false;
std::vector<int> lowBounds,uppBounds;
do
{
uppBounds.clear();
lowBounds.clear();

for(int x=0;x<dimens;++x)
{
if(binFlagArr[x] == 0)
{
lowBounds.push_back(ranges[x][0]);
uppBounds.push_back(ranges[x][1]);
}
else
{
lowBounds.push_back(ranges[x][2]);
uppBounds.push_back(ranges[x][3]);
}
}Node *node = new Node(lowBounds, uppBounds);
node->id = 1;
childs.push_back(node);

// could store it somewhere but here I just print each subspace generated....
std::cout << "--------------------------------\n";
std::cout << "lowBounds: " << lowBounds;
std::cout << "uppBounds: " << uppBounds;

// The following will generate next binary permutation
/*! For dimens = 3, the binary flag will give us something as follows 8 combinations in sequence:
* 0 0 0
* 0 0 1
* 0 1 0
* 0 1 1
* 1 0 0
* 1 0 1
* 1 1 0
* 1 1 1
*/
more = false;
for(int i=dimens-1; i>=0; --i)
{
if(binFlagArr[i] == 0)
{
more = true;

binFlagArr[i] = 1;

for(int k=dimens-1;k>i;--k)
binFlagArr[k]=0;

break;
}
}

} while( more );

//free memory
delete [] binFlagArr;

//free memory
for(int i=0;i<dimens;++i)
delete [] ranges[i];
delete [] ranges;
}