Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Sorting In Graham Scan

Revision en1, by ivplay, 2016-04-15 18:58:23

Given N points. I want to find convex hull keeping collinear points. How should I prepare my initial sort function so that I don't have to make a right turn for points who are collinear? Example: 6 1 1 3 0 2 0 4 1 2 2 0 0  Here is the image for those points. Now I want point F(2,2) comes before point C(1,1) also point B(2,0) comes before point D(3,0) I mean I want following order after sorting A,B,D,E,F,C. what should be my sorting criteria?

Tags convex hull, computational geometry, geometry algorithm, sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ivplay 2016-04-15 18:58:23 524 Initial revision (published)