Drap, Pierre 
41 Determination of the bounding box 
A relevant bounding box is corresponding approximately to the 
minimum volume of the object. We are working on a generic 
method to compute such a bounding box. 
For all convex object with a dominating direction we can use an 
analysis of the main component, which can be used without any 
consideration on the object. The first problem is to determine the 
capable transformation going from the original referential to a local 
referential where one of the axis is equipollent to the object main 
axis. This is equivalent to looking for a maximum variance through 
this axis. In this new referential it is possible to compute a 
bounding box by sorting coordinates which results in a good o 
approximation of the smaller bounding box. 
  
Unfortunately, this method does not function well if the points are 
inside the volume, or if the architectural volume is concave. This : ie : 
means that we have to get first the convex envelop before using the Figure 3. The minimum volume bounding box. 
covariance method to get the bounding box. Actually we use an 
hybrid method, as we already have a set of relevant information on the architectural object. These information are 
collected during the survey phase by the operator according to the architectural model used. 
4.2 Determination of relevant points using topological organization 
Here, we want to retrieve objects, like blocks with particular values of their attributes. For example, we may wish to get 
all blocks of the entity belonging to the same course. To solve this problem, we could ask the operator to point out for 
the current block which block is the next or the previous in the course. Then this information could be store in some 
attribute of the block. Nevertheless, this works fine as long as you don't need to find also, for example, which is the 
upper block: in this case, you'll have to write a new procedure to take upper blocks into account. 
A more general way is to consider blocks as spatial objects and the entity (or its Bloc-Manager) as a spatial database. It 
is then possible to find all blocks with a particular value of their coordinates in the referential of the entity. To achieve 
this, a direct solution is to scan all blocks meeting the criterion or more generally to sort data according to this criterion. 
This is fine but could be quite time consuming as the whole set of data have to be examined at least once before getting 
an answer. Moreover, if such queries are often made, ordering has to be done at each time making the program 
unusable. Finally, last but not least, the desired ranking could be partial: for example we may wish to find the k nearest 
neighbors of an item that are closer than a certain distance. 
In this experimentation we make use of an octree as an implicit spatial index. An octree is a hierarchical data structure 
which uses a regular decomposition of space to index spatial objects. Each octree block is a cube (a container block) 
where leaf blocks contain the spatial objects, whereas non-leaf blocks are decomposed into 2! sub-blocks, where d is the 
number of dimensions (3 for us). In this case the bounding boxes that contain the objects are disjoint and, due to its 
extent, an object can be associated with more than one bounding box or container block. We then use the algorithm 
proposed by Hjaltason and Samet (Hjaltason and Samet, 1995) to rank the objects. This method recursively visits the 
tree nodes containing some query points, starting from the root. This algorithm replaces the recursion stack by a so 
called priority queue which enables to record the blocks whose descendants have not been visited yet as well as the 
objects which have not yet been visited. In this priority queue the objects as well as the container blocks are ordered 
according to their distance to the query point, so that, at each step, the next object or block to be examined is the closer 
from the query point. The efficiency key of this method is, (a) that not all the objects have to be visited before getting 
the result, (b) the search can be dynamically adjusted depending on the objects already reported: each time an object is 
reported the algorithm can resume from the point it has reached instead of starting again from the beginning. Another 
interest of this algorithm is that it can be extended to more than three dimensions as long as consistent distance 
functions can be defined (see Hjaltason and Samet). 
At this point, we have armed ourselves with an efficient method to make queries based on positional definition of 
objects. For instance, we can search for neighbors of a block, after it has been measured, asking which are the blocks in 
the direction defined by the normal vector of one of its faces and located at less than a given threshold distance of this 
face. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B5. Amsterdam 2000. 191