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