Point Classification in a set of Bounding Boxes

Question

I have a set of bounding boxes(rectangular) in a 3D space. The bounds of each box are computed and stored in a dictionary named "RegionBounds". Also, a set of points are populated in a List named "PointsToCategorize" Given a point(x,y,z) coordinates from the List populated and a bounding box to be checked in, i can check if the point is inside the box or not. The problem is, this is a big dataset. The number of points to be checked are like 1000 and the no of bounding boxes are like 250-300. So, if i loop through each bounding box for each given point; the total time it takes is like 5-6 minutes. Is there any efficient method that would do the process quicker ? If possible, a small code to do so would be great

public struct iBounds  {

public double x1, x2;
public double y1, y2;
public double z1, z2;

}
public struct iPoint  {        

   public double x,y,z

}

Dictionary<String, iBounds> RegionBounds = new Dictionary<String, iBounds>();
List<iPoint> PointsToCategorize = new List<iPoint>();

int no_of_bounding_boxes = 300;
int no_of_points_to_categorize = 1000;

for (int i = 1; i <= no_of_bounding_boxes; i++)
{

  String boundingBoxName = "bound_" + i;
  iBounds boundingBox = new iBounds
    {

        x1 = Computed By Some Other method and Formulas,
        x2 = Computed By Some Other method and Formulas,
        y1 = Computed By Some Other method and Formulas,
        y2 = Computed By Some Other method and Formulas,
        z1 = Computed By Some Other method and Formulas,
        z2 = Computed By Some Other method and Formulas

    };

    RegionBounds.Add(boundingBoxName, boundingBox);
}



   ////////////Start of Output section /////////////////////////

 for(int i= 1; i < = PointsToCategorize.Count; i++){

  foreach(var pair in RegionBounds)
   {
     String myboxNmame = pair.Key;
     iBounds myboxBounds = pair.Value;
      Console.WriteLine(PointInside(PointsToCategorize[i],myboxBounds).ToString());

  }
}

 ////////////// End of Output section //////////////////

private bool PointInside(iPoint mypoint, iBounds boxToBeCheckedIn)
{
    if (mypoint.x > boxToBeCheckedIn.x1) && (mypoint.x < boxToBeCheckedIn.x2){
        if (mypoint.y > boxToBeCheckedIn.y1) && (mypoint.y < boxToBeCheckedIn.y2){
            if (mypoint.z > boxToBeCheckedIn.z1) && (mypoint.z < boxToBeCheckedIn.z2){
                return true;
            }
        }
    }else{
        return false;
    }

}

Answer 1

You may want to use a OcTree or a kD-tree data structure, which is way more efficient than iterating through all the boxes.

See also this article at the section 2-D orthogonal range searching, it has a very good resume of available techniques and algorithms, which are easily extendable to 3D