Thread: Convex hull with CGAL

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    Convex hull with CGAL

    Hello everybody and merry Christmas !

    We have as bonus assignment in course topics in Algorithms to implement Graham's scan.

    The pseudocode

    My question :
    I want to sort by polar angle the points with the help of CGAL. I thought that I could use the line segments orientation predicate, but I couldn't find any method that does that.

    My attempt : ( Of course I haven't yet do the sorting step )
    Code:
    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
    #include <CGAL/convex_hull_2.h>
    #include <stack>
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef K::Point_2      Point_2;
    
    
    bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point);
    void removeP0fromSetOfPoints(std::vector< Point_2 >  &P, Point_2 &P0);
    
    int main()
    {
      CGAL::set_ascii_mode(std::cin);
      CGAL::set_ascii_mode(std::cout);
      std::istream_iterator< Point_2 >  in_start( std::cin );
      std::istream_iterator< Point_2 >  in_end;
      std::ostream_iterator< Point_2 >  out( std::cout, "\n" );
    
      std::vector< Point_2 >  P (in_start, in_end);
    
      std::vector< Point_2 >  Q;
    
            Point_2 P0 = P[1];
            int posP0 = 1;
            for(int i = 1 ; i < P.size() ; i++)
            {
                    if( duplicatePoint(P, i, P[i]) )
                            P.erase (P.begin()+i);
                    if( P[i].y() < P0.y() )
                    {
                            P0 = P[i];
                            posP0 = i;
                    }
                    if( P[i].y() == P0.y() )
                            if( P[i].x() < P0.x() )
                            {
                                    P0 = P[i];
                                    posP0 = i;
                            }
            }
    std::cout<<" MIN = " <<P0<<std::endl;
            P.erase(P.begin() + posP0);
    std::cout<<"input<----------------"<<std::endl;
    std::copy(P.begin(), P.end(), out);
    
            /* compute convex hull in Q from input P */
            Q = P;
    
    //TEST  CGAL::convex_hull_2(Q.begin(), Q.end(), out ) ;
    
    
            std::stack<Point_2> S;
    std::cout<<"result<----------------"<<std::endl;
            std::copy(Q.begin(), Q.end(), out);
    
            return 0;
    }
    
    bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point)
    {
            for(int i = 0 ; i < pointPos ; i++)
                    if(P[i] == point)
    
    ...
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Well what I am looking for is simply not providing in CGAL. That's why I couldn't find it I emailed professor and said that he forgot to mention that
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. CGAL in Ubuntu 12.04
    By anirban in forum Tech Board
    Replies: 10
    Last Post: 07-25-2012, 09:52 AM
  2. Simple c++ convex hull help
    By Stamatis in forum C++ Programming
    Replies: 11
    Last Post: 03-04-2012, 11:57 AM
  3. convex hull using c
    By sunils120 in forum C Programming
    Replies: 1
    Last Post: 08-29-2011, 06:50 AM
  4. CGAL question
    By disruptivetech in forum C++ Programming
    Replies: 0
    Last Post: 04-28-2008, 11:34 AM
  5. Convex Hull <#>
    By Moni in forum C++ Programming
    Replies: 6
    Last Post: 06-07-2003, 09:45 AM