CGAL users discussion list

[Juan Carlos Lopez Alfonso <>]

Thank you for your answer and help. In any case, I can't remove points, I need to use all points, because these points represent the simulated organs extracted from a medical machine. 

But, Can I change the coplanar test when CGAL computes the triangulation? is to say, Can I impose a "minimum" volume of my tetrahedrons?

Thank you in advance

JC.

On Fri, Jan 20, 2012 at 8:17 AM, Sebastien Loriot (GeometryFactory) <> wrote:

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)

       <laurent.rineau__CGAL@__normalesup.org
       <mailto:>
       <mailto:__normalesup.org

       <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>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss