dimanche 5 juillet 2020

convexhull polygon including the points on the edges of the polygon

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 ) B must be included between A and C , I must be included between J and H ....

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