Ok, there was a misunderstanding...
In the last revision (1.20 point_locator_tree.C, 1.22 tree_node.C) the
ELEMENTS version works better then the NODES version in the search (it
doesn't involve the linear search) but it is slower when you populate the
tree. I also prefer the 1.19 version of point_locator_tree.C.
The NODES version doesn't inserts the element to all the tree nodes that
have non empty intersection with the element bounding box, it insert the
element to all the tree that bounds an element's node. With the NODES
version it is possible that the point you are searching isn't contained in
any element assigned to the node of the tree that bounds
the point and so you will need the linear search.
The ELEMENT version is slower when it populates the tree because it needs t=
calculate the element bounding box many times and probably it builds more
I actually use a different version of tree_node.C and I'll try to post it
in a new tread.
2007/9/13, Tim Kr=F6ger <tim@...>:
> Dear Lorenzo,
> On Wed, 12 Sep 2007, Lorenzo Botti wrote:
> >> However, it seems to me that the NODES version requires the linear
> >> search at the end of PointLocatorTree::operator() to be involved mor=
> >> often than the ELEMENTS version; in particular, the ELEMENTS version
> >> did *never* need the linear search in the case for linear elements,
> >> whereas the NODES version does (in my case, for linear TET10
> >> elements). While I don't doubt that it is still much faster in the
> >> mean, it causes approximately two problems for my application:
> >> 1.) Since I am using out_of_mesh_mode, I get wrong results, since the
> >> linear search is disabled in out_of_mesh_mode.
> > this sounds strange... the NODES BOUNDING BOX version should avoid
> > (completely in case of elements with rectilinear edges) the linear
> > for points within the mesh.
> > You shouldn't find any element forcing the linear search in out of mes=
> > mode.
> > With the ELEMENT CENTROID insertion method (revision 1.19) the linear
> > deals with the particular situations in witch the point you are
> > isn't contained in any element assigned to the node of the tree that
> > the point.
> The ELEMENT method is no longer using the centroids. It inserts the
> given element to all tree nodes that have non-empty intersection with
> the element's bounding box. This method is in use since August 4th of
> last year. See also the discussion in libmesh-devel around that date
> with the subject "Patch". (I admit that I am responsible for that
> silly subject.) This should work (i.e. not need the linear search)
> always except for elements with curved boundaries. In particular, it
> always worked (and still works) for my application (with TET10
> I don't know exactly what the NODES method is doing, but it doesn't
> seem to work for my example. Since I am not a native English speaker,
> I am not sure what you mean with "rectilinear edges"; do you just mean
> "non-curved edges" or do you mean "edges parallel to coordinate axes"?
> Please find attached a test program with which the problem can be
> verified. I have place my example mesh file at
> http://www.cevis.uni-bremen.de/~tim/a.xdr; use that file together with
> the test program. You will see that 29 positions in the mesh are not
> found without the linear search.
> Then replace point_locator_tree.C with its 1.19 version and repeat the
> test. All points will then be found without linear search.
> Best Regards,
> Dr. Tim Kroeger Phone +49-421-218-7710
> tim@..., tim@... Fax +49-421-218-4236
> MeVis Research GmbH, Universitaetsallee 29, D-28359 Bremen, Germany
> Amtsgericht Bremen HRB 16222
> Geschaeftsfuehrer: Prof. Dr. H.-O. Peitgen