   Algorithm help for Dynamic shadows
  Hello Everyone, I wrote this algorithm for sorting a random list of points in an array in clockwise order. I am not sure if anyone has already written such an algorithm but Mine seems like it has a few holes in it, as in a few conditions that it will not work. If some of you guys could look it over and see if there are anything i could add to make it more fool proof. Right now I am making a system for 2D dynamic shadows and have the shadows created as a random list of points and I think it will be easier just to order them after storing them to put them into the array in order. So I got all the points in the array to where it makes a good shadow, now I just need to order them in a clockwise order. The algorithm I made does a decent job but when the shadow is projected a certain direction it is not in clockwise order. Here is how I am sorting them:first I order all the points horizontally in the array(or by there x value) then choose a starting point usually the Y value of the midpoint of all the verts. Then compare all the points that are sorted if a points Y Value is above the chosen center's Y then add it to the finished list(still int x sorted order). So now all the points above the center horizontal line are in the final array sorted by there x value. Next all the points that are not in the final array(above the center y) are added to there own list and reversed. Then they are appended to the end of the final array to theoretically create a sorted point list in clockwise order.if anyone could look at this algorithm and what could be done to improve it or if there is an algorithm that is simpler that can accomplish the same taskThanks, David   
  anyone?   ;  What do you mean by clockwise ordering?Do you have a center point where you want all the other points sorted around? If so, you can just perform the sort with a comparator that checks two points and determine their relative clockwise order. "Just" check the angle between the vectors (with the origin at the center point). But you'll need some reference angle to start the clockwise sorting from.I may have misunderstood everything though :)[Edited by - pernyblom on May 19, 2010 2:44:05 PM];  What exactly is wrong with your current algorithm? Does it work as expected except that sometimes the vertices are counter-clockwise, or are there other issues?If you know that your shadow polygons will be convex you can use a convex hull algorithm. There are a few libraries around that find the convex hull for you such as CGAL.If the polygon may be concave you then have a problem with uniqueness. Which one of the two polygons below are correct?Here are a few links on finding non-convex hulls:http://biogeometry.duke.edu/software/alphashapes/http://www.geosensor.net/papers/duckham08.PR.pdfThis explains how find an alpha shape using the CGAL library I linked to above: http://www.cgal.org/Manual/last/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html