CGAL users discussion list

[Matthijs Sypkens Smit <>]

> On Wednesday 10 October 2007 03:24:21 Dr. Liu Jianfei wrote:
> > I am using Nef_polyhedron_3 and its function locate(Point_3) for
> > point-in-polyhedron test for polyhedrons composed of triangles.
> > However the time to create a Nef_polyhedron_3 is very cost and always
> > fail when the number of triangles is more than 4,000. In fact, I have
> > just developed a new point-in-polyhedron algorithm, it aims to treat
> > large scale problems( a lot of tests with respect to models composed
> > of huge number of triangles). It is much efficient comparing with
> > results found in literatures.However I need some other codes to do
> > comparison directly and I wounder if the function locate in CGAL is
> > the suitable one.

Using a CGAL Nef polyhdron to do inside/outside tests on a polyhedron is 
relatively inefficient in my experience. From the limited tests that I did 
with some triangulated models it was in the order of 10000 times slower 
than using a (constrained) Delaunay triangulation. Another very fast 
method is the use of a binary space partition of your triangulated models. 
Both methods (Delaunay and BSP) have the drawback that the initial data 
structure is hard to create. I do not know any free codes that work in 3D 
and also approach CGAL's robustness.


-- 
Matthijs Sypkens Smit