I am trying to implement Graham Scan method to implement the Convex Hull algorithm , but I want to add the set of points on the Hull which are on the edges of the polygon (points which are collinear to the adjacent vertices of the polygon )
I think I have to change the comparator function in sort function (sorting the points according to counterclockwise polar angle ) . But I cant able to do it , what i have to change in this :-
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// A function used by library function qsort() to sort an array of
// points with respect to the first point
// p0 is the first point
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;
// Find orientation
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
Aucun commentaire:
Enregistrer un commentaire