CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

One solution is once the triangulation is built,
remove points while there is an almost flat tetrahedron.
To detect them, compute the jacobian using Interval_nt
and if the interval contains 0, then remove one of the
four points.

Alternatively, you can use

CGAL::Simple_cartesian<CGAL::Interval_nt<> > Intvl_K;
CGAL::Cartesian_converter<K,Intvl_K> to_interval;

Intvl_k::Point_3 p1_approx=to_interval(p1);
...

if ( CGAL::possibly(
        CGAL::Orientation(p1_approx,
                          p2_approx,
                          p3_approx,
                          p4_approx)==CGAL::COPLANAR
     ) ) //remove one of the four points from the triangulation


see:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/NumberTypeSupport_ref/Class_Interval_nt.html
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/STL_Extension_ref/Class_Uncertain.html

Sebastien.

On 01/20/2012 02:55 AM, Juan Carlos Lopez Alfonso wrote:
> Hi Sebastien and Laurent:
>
> First of all, I want to thank for your answers. I have tested the
> conditions of coplanar points. In CGAL thsi condition
> (CGAL::orientation(p1, p2, p3, p4) == CGAL::COPLANAR) is not satisfied
> when the Jacobian is equal to zero, so I have a question:
>
> - I need to use the triangulation and the Jacobian in other software,
> for this reason I can't use an exact representation of doubles.
> Therefore, How I can change the CGAL condition to coplanar points? is to
> say, I need to consider the coplanar condition in CGAL using my
> Jacobian, is it possible? or is possible to change the coplanar
> condition in order to obtain thetraedra with more volume?
>
> Thank you in advance
> Juan Carlos
>
> On Thu, Jan 19, 2012 at 5:33 PM, Sebastien Loriot (GeometryFactory)
> <
>  
> <mailto:>>
>  wrote:
>
>     On 01/19/2012 04:13 PM, Juan Carlos Lopez Alfonso wrote:
>
>         Hi Sebastien and  Laurent:
>
>         Please, see these links below with my code and the input file of
>         3D points:
>
>         http://dl.dropbox.com/u/__2516160/main.cpp
>         <http://dl.dropbox.com/u/2516160/main.cpp>
>         http://dl.dropbox.com/u/__2516160/CubeSmall.txt
>         <http://dl.dropbox.com/u/2516160/CubeSmall.txt>
>
>         When I run my code, the test (if (CGAL::orientation(p1, p2, p3,
>         p4) ==
>         CGAL::COPLANAR)) is never satisfied, but when I compute the
>         Jacobian is
>         equal to 0.000000000000, is to say, that the 4 points of several
>         thetraedra are coplanar. Maybe Laurent have reason, but How can
>         I solve
>         this problem? Could you give me suggestions?
>
>
>     This is what Laurent explained you.
>     The test GAL::orientation uses the kernel
>     Exact_predicates_inexact___constructions_kernel meaning that predicates
>     are correctly evaluated. Which also implies that your points are not
>     collinear.
>
>     If you really want to compute the jacobian by hand you need to use an
>     exact number type such as CGAL::Gmpq.
>
>     something like that should work:
>     typedef CGAL::Simple_cartesian<CGAL::__Gmpq> Exact_kernel;
>     CGAL::Cartesian_converter<K, Exact_kernel> convert;
>     Exact_kernel::Point_3 p1_exact=convert(p1);
>     ...
>     ...
>     Exact_kernel::Point_3 p4_exact=convert(p4);
>
>     CGAL::Gmpq jacobian = (p2_exact.x() - p1_exact.x()) * ....
>
>     if (jacobian ==0) ...
>
>     You'll see that jacobian is not 0
>
>
>     See also this FAQ entry:
>     http://www.cgal.org/FAQ.html#__inexact_NT
>     <http://www.cgal.org/FAQ.html#inexact_NT>
>
>     Sebastien.
>
>
>         Thank you for all and waiting your answer
>         Juan Carlos
>
>         On Thu, Jan 19, 2012 at 3:41 PM, Laurent Rineau (GeometryFactory)
>         
> <
>         
> <mailto:>
>         
> <mailto:
>         
> <mailto:>>>
>  wrote:
>
>             Le jeudi 19 janvier 2012 15:12:16 Juan Carlos Lopez Alfonso
>         a écrit :
>          > Hi Sebastien:
>          >
>          > To detect that points are coplanar, I have computed the jacobian
>             of each
>          > thetraedra:
>          >
>          > //for each thetraedra !!!
>          > ........
>          > Tetrahedron t = T[i];
>          >
>          > Vertex p1 = cit->vertex(0);
>          > Vertex p2 = cit->vertex(1);
>          > Vertex p3 = cit->vertex(2);
>          > Vertex p4 = cit->vertex(3);
>          >
>          > double Jacobian =
>          > (p2.x - p1.x) * (p3.y - p1.y) * (p4.z - p1.z) + (p3.x - p1.x) *
>             (p4.y -
>          > p1.y) * (p2.z - p1.z) + (p4.x - p1.x) * (p2.y - p1.y) * (p3.z
>         - p1.z)
>          >  - (p4.x - p1.x) * (p3.y - p1.y) * (p2.z - p1.z) - (p3.x - p1.x)
>             * (p2.y -
>          > p1.y) * (p4.z - p1.z) - (p2.x - p1.x) * (p4.y - p1.y) * (p3.z -
>             p1.z);
>          > ........
>
>             That way of detecting coplanarity is subject to rounding errors.
>             Probably you
>             have almost-coplanar points in your data set, but in
>         reality, using a
>             certified arithmetic, there are not coplanar.
>
>             --
>             Laurent Rineau, PhD
>             R&D Engineer at GeometryFactory
>         http://www.geometryfactory.__com/ <http://www.geometryfactory.com/>
>             Release Manager of the CGAL Project http://www.cgal.org/
>
>
>             --
>             You are currently subscribed to cgal-discuss.
>             To unsubscribe or access the archives, go to
>         https://lists-sop.inria.fr/__wws/info/cgal-discuss
>         <https://lists-sop.inria.fr/wws/info/cgal-discuss>
>
>
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://lists-sop.inria.fr/__wws/info/cgal-discuss
>     <https://lists-sop.inria.fr/wws/info/cgal-discuss>