Regular space subdivision

Question

I am writing an application which subdivides an N-dimensional axis aligned bounding box into smaller N-dimensional bounding boxes, I need an algorithm which will do this.
For example:

in 1 dimension a "bounding box" is simply a length
e.g. { Min=0, Max=100 }
which would be subdivided into
{Min=0, Max=50} and {Min=50, Max=100}

in 2 dimensions a "bounding box" is a square
e.g. {Min=[0,0], Max=[100,100]}
would be divided into
{Min=[0,0], Max=[50,50]}
{Min=[0,50], Max=[50,100]}
{Min=[50,0], Max=[100,50]}
{Min=[50,50], Max=[100,100]}

And so on, all I need is a description of an algorithm for doing this, language doesn't particularly matter, since once I know how to do it I can translate it into the language of choice (C# in this case)

EDIT:: In response to questions in comments:

• subdivisions must always be equal (as in the examples)
• boundaries are floating points, so divisibility by two isn't a problem

Answer 1

Break it into two problems: iterating over the grid of "Min" points, and constructing a small box for a Min point.

For your second case, {[0,0], [100,100]}, deltaX=50 and deltaY=50. The grid is

[0,   0]
[0,  50]
[50,  0]
[50, 50]

and it is trivial to construct the second column from the first:

[ 0,  0] [ 50,  50]
[ 0, 50] [ 50, 100]
[50,  0] [100,  50]
[50, 50] [100, 100]

Here's a three-dimensional case {[0,0,0], [100,100,60]}, delta = [50, 50, 30]

[ 0,  0,  0] [ 50,  50, 30]
[ 0,  0, 30] [ 50,  50, 60]
[ 0, 50,  0] [ 50, 100, 30]
[ 0, 50, 30] [ 50, 100, 60]
[50,  0,  0] [100,  50, 30]
[50,  0, 30] [100,  50, 60]
[50, 50,  0] [100, 100, 30]
[50, 50, 30] [100, 100, 60]

Answer 2

A function that splits the box in all dimensions (in Python):

def halfboxes(box):
  result = [[]]
  for (a, b) in box:
    result = [r + [(a, (a+b)/2)] for r in result] + \
             [r + [((a+b)/2, b)] for r in result]
  return result

h = halfboxes([(0,100), (20, 100)])

# Results in h =
#   [[(0, 50), (20, 60)],  [(50, 100), (20, 60)],
#    [(0, 50), (60, 100)], [(50, 100), (60,100)]]

If this is's a good solution also depends your performance requirements. It makes a lot copies of arrays, which is not really efficient. But it might well be good enough for your use case.

Edit:

A more efficient version, that doesn't copy any arrays:

def halfboxes(box):
   # total number of resulting arrays
   resultscount = 2**len(box)

   # allocate |resultscount| arrays
   results = [[] for i in range(resultscount)]

   spread = 1
   for (a,b) in box:
      low  = (a, (a+b)/2)
      high = ((a+b)/2, b)
      for i in range(resultscount):
         # "magic" to append the high/low parts to the correct array
         if i % (spread*2) < spread:
            results[i].append(low)
         else:
            results[i].append(high)
      spread *= 2
   return results

Here no arrays are copied and some calculations on the index are used to decide where the new boundaries should be added.

Answer 3

• calculate the first box:

dimension n: Min[0, 0, 0, .., 0] -- Max[delta₁/2, delta₂/2, ..., delta_n/2]

• your big box will be subdivised to 2ⁿ small boxes -> calculate 2ⁿ transalations to apply to the 1st box (including a translation of [0, 0, 0, .., 0])

(of course the code below is not optimized-organized...)

---

using System;
using System.Collections.Generic;

namespace WindowsFormsApplication1
{
    public class Class1
    {
        public static List<Box> GetSmallBoxes(Box bigBox)
        {
            int translationCoef;
            List<Box> boxes = new List<Box>();                        
            Box box;

            for (int k = 0; k < Math.Pow(2, bigBox.Dimension); k++)
            {
                box = new Box(bigBox.Dimension);

                for (int d = 0; d < bigBox.Dimension; d++)
                {
                    translationCoef = ((int)(k / Math.Pow(2, bigBox.Dimension - d - 1)) % 2) == 0 ? 1 : 0;

                    box.Mins[d] = bigBox.Mins[d] + (bigBox.Deltas[d] / 2) * translationCoef;
                    box.Maxs[d] = bigBox.Mins[d] + (bigBox.Deltas[d] / 2) * (1 + translationCoef);
                }

                boxes.Add(box);
            }

            return boxes;
        }

        public static void Main()
        {
            Box bigBox = new Box(5);
            bigBox.Mins = new int[] { 0, 10, 30, 20, 40 };
            bigBox.Maxs = new int[] { 80, 50, 110, 40, 50 };
            List<Box> smallBoxes = Class1.GetSmallBoxes(bigBox);
        }
    }

    public class Box
    {
        public int Dimension;
        public int[] Mins;
        public int[] Maxs;

        public Box(int dimension)
        {
            Dimension = dimension;
            Mins = new int[dimension];
            Maxs = new int[dimension];
        }

        public int[] Deltas
        {
            get
            {
                int[] deltas = new int[Dimension];
                for (int i = 0; i < Dimension; i++)
                {
                    deltas[i] = Maxs[i] - Mins[i];
                }
                return deltas;
            }
        }

        public override string ToString()
        {
            string str;
            str = "Min[";
            foreach (int min in Mins)
            {
                str += min.ToString() + ", ";
            }
            str = str.Substring(0, str.Length - 2);
            str += "] -- Max[";
            foreach (int max in Maxs)
            {
                str += max.ToString() + ", ";
            }
            str = str.Substring(0, str.Length - 2);
            return str;
        }
    }
}