Databases
StackOverflow2013
Postsdbo
POC++ algorithm for partitioning area of a given dimension into sub-parts with non overlapping borders
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC++ algorithm for partitioning area of a given dimension into sub-parts with non overlapping borders
    text
    copied!<p>I want to have an algorithm to partition an area of any given dimension into subspaces with non-overlapping borders.</p> <p>For example: With 2 dimensions where lower and upper bound for each dimensions are given as follows:</p> <blockquote> <p>LowerBounds: 1, 1 </p> <p>UpperBounds: 100, 50</p> </blockquote> <p>Above represents a 2D rectangle. i.e. Four corner points of a rectangle (1-1, 1-50, 100-1, 100-50). Now I want to cut in into 4 sub-rectangular parts with non-overlapping borders areas such as</p> <blockquote> <p>sub-rect1: ( 1-1, 1-25, 50-1, 50-25 )</p> <p>sub-rect2: ( 51-1, 51-25, 100-1, 100-25 )</p> <p>sub-rect3: ( 1-26, 1-50, 50-26, 50-50 )</p> <p>sub-rect4: ( 51-26, 51-50, 100-26, 100-50 )</p> </blockquote> <p>I hope you understand what I want. What I really want is to have a C++ algorithm that can work for any dimensions ranging from 1 to atleast 10. I am really bad with recursive algorithms. Both recursive or iterative algorithms would help.</p> <p><strong>UPDATE: Here is the solution that I came up with myself. I post it here so that it could help someone else with similar needs in future.</strong></p> <pre><code>/*! To display vector contents... */ std::ostream &amp;operator&lt;&lt;(std::ostream &amp;os, const std::vector&lt;int&gt; &amp;vec) { for (int i=0; i&lt;vec.size(); ++i) os &lt;&lt; " " &lt;&lt; vec[i]; os &lt;&lt; "\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&lt;int&gt; &amp;baseLowBound, std::vector&lt;int&gt; &amp;baseUppBound) { assert(baseLowBound.empty() == false &amp;&amp; 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&lt;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&lt;dimens;++i) { low = baseLowBound[i]; upp = baseUppBound[i]; // there should be atleast two intermediate points to get disjoint ranges assert(low &lt; (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&lt;dimens; ++i) { binFlagArr[i] = 0; } bool more = false; std::vector&lt;int&gt; lowBounds,uppBounds; do { uppBounds.clear(); lowBounds.clear(); for(int x=0;x&lt;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-&gt;id = 1; childs.push_back(node); // could store it somewhere but here I just print each subspace generated.... std::cout &lt;&lt; "--------------------------------\n"; std::cout &lt;&lt; "lowBounds: " &lt;&lt; lowBounds; std::cout &lt;&lt; "uppBounds: " &lt;&lt; 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&gt;=0; --i) { if(binFlagArr[i] == 0) { more = true; binFlagArr[i] = 1; for(int k=dimens-1;k&gt;i;--k) binFlagArr[k]=0; break; } } } while( more ); //free memory delete [] binFlagArr; //free memory for(int i=0;i&lt;dimens;++i) delete [] ranges[i]; delete [] ranges; } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload