Problem with Convex Hull, again

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Problem with Convex Hull, again

Rafael Roberto
Hello,

like I've said before, I'm making an application that takes a set of points and create a convex hull for those points. I had some problems with my code because I was using the Cartesian kernel, not the Exact_predicates_inexact_constructions_kernel, for treat double numbers. But now that I changed the kernel, when I call the convex_hull_3 function, the program makes an access  violation (Unhandled exception at 0x104817fd (msvcp80d.dll) in ConstrainedDelaunay.exe: 0xC0000005: Access violation writing location 0xcccccccc.)

I have no idea what this could be. Does any body have any clue where I'm wrong?

The code is the follow ---------------------------------------
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Convex_hull_traits_3.h>
#include <CGAL/convex_hull_3.h>
#include <iostream>
#include <fstream>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Convex_hull_traits_3<Kernel>                  Traits;
typedef Traits::Polyhedron_3                                Polyhedron;

typedef Kernel::FT                                          Field_number;
typedef Kernel::Point_3                                     Point;

using namespace std;

int main(){
    ifstream file;
    file.open("resources/geometry.txt");
    vector<Point> points;
    Field_number x, y, z;

    while (!file.eof()) {
       file >> x >> y >> z;
       Point point(x, y, z);
       points.push_back(point);
    }

    Polyhedron polyhedron;

    CGAL::convex_hull_3(points.begin(), points.end(), polyhedron);

    return 0;
}

-----------------------------------------------------------------------

Thank you all,
Rafael Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Problem with Convex Hull, again

Ashwin Nanjappa-2
Rafael Roberto wrote:

> Hello,
>
> like I've said before, I'm making an application that takes a set of
> points and create a convex hull for those points. I had some problems
> with my code because I was using the Cartesian kernel, not the
> Exact_predicates_inexact_constructions_kernel, for treat double numbers.
> But now that I changed the kernel, when I call the convex_hull_3
> function, the program makes an access  violation (/Unhandled exception
> at 0x104817fd (msvcp80d.dll) in ConstrainedDelaunay.exe: 0xC0000005:
> Access violation writing location 0xcccccccc./)
>
> I have no idea what this could be. Does any body have any clue where I'm
> wrong?

I'm not having any problem running your convex hull code. Could you share
a small point set of yours which shows this problem?

Regards,
~ash
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Problem with Convex Hull, again

Ashwin Nanjappa-2
Ashwin Nanjappa wrote:
> I'm not having any problem running your convex hull code. Could you
> share a small point set of yours which shows this problem?

The reply I got from Rafael which he doesn't seem to have sent to the
mailing list:

====================================================================
Hi, Ashwin!

Attached to the e-mail is the file with the points I'm using.

I have already found that is nothing wrong with my code, that it works
fine in Linux with g++ compiler, for example. The problem is that didn't
work with any Visual Studio 2005 here in my university. What compile and
platform are you using over there?


Thanks a lot,
Rafael Roberto
====================================================================

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

 6.635440 6.635440 0.000000
 -0.000000 9.383929 0.000000
 -6.635440 6.635439 0.000000
 -9.383929 -0.000001 0.000000
 -6.635439 -6.635441 0.000000
 0.000001 -9.383929 0.000000
 6.635441 -6.635439 0.000000
 9.383929 0.000002 0.000000
 6.635440 6.635440 2.695469
 -0.000000 9.383929 2.695469
 -6.635440 6.635439 2.695469
 -9.383929 -0.000001 2.695469
 -6.635439 -6.635441 2.695469
 0.000001 -9.383929 2.695469
 6.635441 -6.635439 2.695469
 9.383929 0.000002 2.695469
 4.844582 4.844582 5.390938
 -0.000000 6.851274 5.390938
 -4.844582 4.844582 5.390938
 -6.851274 -0.000001 5.390938
 -4.844582 -4.844583 5.390938
 0.000001 -6.851274 5.390938
 4.844583 -4.844581 5.390938
 6.851274 0.000001 5.390938
 4.513058 4.513059 8.086407
 -0.000000 6.382428 8.086407
 -4.513059 4.513058 8.086407
 -6.382428 -0.000001 8.086407
 -4.513058 -4.513059 8.086407
 0.000001 -6.382428 8.086407
 4.513059 -4.513058 8.086407
 6.382428 0.000001 8.086407
 6.632059 6.632059 10.781876
 -0.000000 9.379148 10.781876
 -6.632059 6.632058 10.781876
 -9.379148 -0.000001 10.781876
 -6.632058 -6.632060 10.781876
 0.000001 -9.379148 10.781876
 6.632060 -6.632058 10.781876
 9.379148 0.000002 10.781876
 4.672345 4.672346 13.477345
 -0.000000 6.607694 13.477345
 -4.672346 4.672345 13.477345
 -6.607694 -0.000001 13.477345
 -4.672345 -4.672346 13.477345
 0.000001 -6.607694 13.477345
 4.672346 -4.672345 13.477345
 6.607694 0.000001 13.477345
 4.672348 4.672348 16.172813
 -0.000000 6.607698 16.172813
 -4.672348 4.672348 16.172813
 -6.607698 -0.000001 16.172813
 -4.672348 -4.672348 16.172813
 0.000001 -6.607698 16.172813
 4.672348 -4.672347 16.172813
 6.607698 0.000001 16.172813
 6.632059 6.632059 18.868280
 -0.000000 9.379148 18.868280
 -6.632059 6.632058 18.868280
 -9.379148 -0.000001 18.868280
 -6.632058 -6.632060 18.868280
 0.000001 -9.379148 18.868280
 6.632060 -6.632058 18.868280
 9.379148 0.000002 18.868280
 4.513056 4.513056 21.563751
 -0.000000 6.382425 21.563751
 -4.513056 4.513055 21.563751
 -6.382425 -0.000001 21.563751
 -4.513055 -4.513057 21.563751
 0.000001 -6.382425 21.563751
 4.513057 -4.513055 21.563751
 6.382425 0.000001 21.563751
 4.844584 4.844584 24.259218
 -0.000000 6.851276 24.259218
 -4.844584 4.844584 24.259218
 -6.851276 -0.000001 24.259218
 -4.844584 -4.844584 24.259218
 0.000001 -6.851276 24.259218
 4.844584 -4.844583 24.259218
 6.851276 0.000001 24.259218
 6.635440 6.635440 26.954689
 -0.000000 9.383929 26.954689
 -6.635440 6.635439 26.954689
 -9.383929 -0.000001 26.954689
 -6.635439 -6.635441 26.954689
 0.000001 -9.383929 26.954689
 6.635441 -6.635439 26.954689
 9.383929 0.000002 26.954689
 6.635440 6.635440 29.650156
 -0.000000 9.383929 29.650156
 -6.635440 6.635439 29.650156
 -9.383929 -0.000001 29.650156
 -6.635439 -6.635441 29.650156
 0.000001 -9.383929 29.650156
 6.635441 -6.635439 29.650156
 9.383929 0.000002 29.650156
Reply | Threaded
Open this post in threaded view
|

Re: Problem with Convex Hull, again

Ashwin Nanjappa-2
Ashwin Nanjappa wrote:
>
> I have already found that is nothing wrong with my code, that it works
> fine in Linux with g++ compiler, for example. The problem is that didn't
> work with any Visual Studio 2005 here in my university. What compile and
> platform are you using over there?

I'm on Visual C++ 2008 Express Edition and with the point set you shared I
can see the same error that you mentioned. It is indeed strange that you
don't get this error when you try it with g++/Linux. The error doesn't
happen if I change the kernel from Exact_predicates_inexact_constructions
to E_p_exact_constructions.

I've attached the call stack of this exception to this email. What is
strange is that it seems to be failing in a predicate, rather than in a
construction. Maybe the others in this list can shed some light on that.

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

 1      Triangulation_3.exe!std::_Debug_message(const wchar_t * message=0x0055e818, const wchar_t * file=0x0055e698, unsigned int line=1122)
*2      Triangulation_3.exe!std::vector<short,std::allocator<short> >::_Insert_n(std::_Vector_iterator<short,std::allocator<short> > _Where=..., unsigned int _Count=1, const short & _Val=3)
 3      Triangulation_3.exe!std::vector<short,std::allocator<short> >::insert(std::_Vector_iterator<short,std::allocator<short> > _Where=..., const short & _Val=3)
 4      Triangulation_3.exe!std::vector<short,std::allocator<short> >::push_back(const short & _Val=3)
 5      Triangulation_3.exe!CGAL::MP_Float::construct_from_builtin_fp_type<double>(double d=2.6954690000000001)
 6      Triangulation_3.exe!CGAL::MP_Float::MP_Float(double d=2.6954690000000001)
 7      Triangulation_3.exe!CGAL::Split_double<CGAL::MP_Float>::operator()(double d=2.6954690000000001, CGAL::MP_Float & num={...}, CGAL::MP_Float & den={...})
 8      Triangulation_3.exe!CGAL::Quotient<CGAL::MP_Float>::Quotient<CGAL::MP_Float>(const double & n=2.6954690000000001)
 9      Triangulation_3.exe!CGAL::NT_converter<double,CGAL::Quotient<CGAL::MP_Float> >::operator()(const double & a=2.6954690000000001)
 10     Triangulation_3.exe!CGAL::Cartesian_converter<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Simple_cartesian<CGAL::Quotient<CGAL::MP_Float> >,CGAL::NT_converter<double,CGAL::Quotient<CGAL::MP_Float> > >::operator()(const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & a={...})
 11     Triangulation_3.exe!CGAL::Filtered_predicate<CGAL::CartesianKernelFunctors::Orientation_3<CGAL::Simple_cartesian<CGAL::Quotient<CGAL::MP_Float> > >,CGAL::CartesianKernelFunctors::Orientation_3<CGAL::Simple_cartesian<CGAL::Interval_nt<0> > >,CGAL::Cartesian_converter<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Simple_cartesian<CGAL::Quotient<CGAL::MP_Float> >,CGAL::NT_converter<double,CGAL::Quotient<CGAL::MP_Float> > >,CGAL::Cartesian_converter<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Simple_cartesian<CGAL::Interval_nt<0> >,CGAL::NT_converter<double,CGAL::Interval_nt<0> > >,1>::operator()<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian
<double> > >,CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > >(const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & a1={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & a2={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & a3={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & a4={...})
 12     Triangulation_3.exe!CGAL::SF_Orientation_3<CGAL::Filtered_kernel_base<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >::operator()(const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & p={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & q={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & r={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & s={...})
 13     Triangulation_3.exe!CGAL::Point_triple_has_on_positive_side_3<CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > >::operator()(const CGAL::Point_triple<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & pl={...}, const CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & p={...})
 14     Triangulation_3.exe!CGAL::non_coplanar_quickhull_3<CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> >,CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > >(std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > & points=[87]({...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},...), CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> > &
 P={...}, const CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & traits={...})
 15     Triangulation_3.exe!CGAL::ch_quickhull_polyhedron_3<std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >::_Iterator<0>,CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> >,CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > >(std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > & points=[87]({...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{...},{..
.},{...},{...},{...},{...},{...},...), std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >::_Iterator<0> point1_it={...}, std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >::_Iterator<0> point2_it={...}, std::list<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >::_Iterator<0> point3_it={...}, CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> > & P={...}, const CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & traits={...})
 16     Triangulation_3.exe!CGAL::convex_hull_3<std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >,CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> >,CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > >(std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > first={...}, std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > beyond={...}, CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> > & polyhedron={...}, con
st CGAL::Convex_hull_traits_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > & traits={...})
 17     Triangulation_3.exe!CGAL::convex_hull_3<std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > >,CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> > >(std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > first={...}, std::_Vector_iterator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > >,std::allocator<CGAL::Point_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> > > > > beyond={...}, CGAL::Polyhedron_3<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,CGAL::Polyhedron_items_3,CGAL::HalfedgeDS_default,std::allocator<int> > & polyhedron={...})
 18     Triangulation_3.exe!main()
 19     Triangulation_3.exe!__tmainCRTStartup()
 20     Triangulation_3.exe!mainCRTStartup()
 21     kernel32.dll!RegisterWaitForInputIdle()
 22     [Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]

Reply | Threaded
Open this post in threaded view
|

Re: Problem with Convex Hull, again

Rafael Roberto
Hello everyone,

Ashwin, its works fine to me too when I change to Exact_predicates_exact_constructions, like you said. I have no idea what this problem could be, I'm starting using CGAL just now, so I still have much to learn to see those things.

And wasn't me that ran this code with g++ in Linux. Unfortunately we don't have Linux here, so I couldn't make this test, but Bernd (a list member) said to me that this worked fine with him in those conditions.

But now, I have a doubt: what is the real difference beteween Exact_predicates_exact_constructions to Exact_predicates_inexact_constructions?


Thank you all,
Rafael Roberto
Reply | Threaded
Open this post in threaded view
|

Re: Problem with Convex Hull, again

Ashwin Nanjappa-2
Rafael Roberto wrote:
> But now, I have a doubt: what is the real difference between
> Exact_predicates_exact_constructions to
> Exact_predicates_inexact_constructions?

Predicates are geometric tests where only the polarity of the result is of
interest (like pass/fail). Constructions are calculations that result in new
geometric entities. Now, all geometric algorithms in theory deal with
numbers of infinite precision. However, when we calculate on the computer we
are restricted to finite precision. Calculations of "exact" arithmetic can
be attempted, but it will slow down the program.

So, these 2 kernels offer tradeoffs between speed and precision. As their
titles indicate, predicates are exact in both, but constructions aren't in
E_P_I_C. But, E_P_I_C is faster than E_P_E_C.

See for more details:
<http://www.cgal.org/Manual/3.3.1/doc_html/cgal_manual/Kernel_23_ref/Class_Exact_predicates_inexact_constructions_kernel.html>
<http://www.cgal.org/Manual/3.3.1/doc_html/cgal_manual/Kernel_23_ref/Class_Exact_predicates_exact_constructions_kernel.html>

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