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