that was one of the assignments in Scientific Computing Dept in my college

\”to construct a simple polygon form ALL the points i have in a plan\”

well, a simple polygon is the polygon where it\’s edges doesn\’t intersect

i thought of an algorithm that is near to the incremental convex hull algorithm

and here is the pseudo-code

Simple_Polygon_Construction (Points)
     Sort (Points)   //sort the points Ascending on x and descending on Y
     Line L=Construct_Line(Points[0],Points[Points->Size])   //construct a line from the two extreme points on the X-Axis
     ForEach Point p in Points
            IF p above L
                 Add p to Polygon toReturn
                 Add p to tempStack
     End ForEach
     While !tempStack->Empty()
            Add tempStack->top() to Polygon toReturn
     End While
return Polygon toReturn

well the algorithm weight here will be O(n log (n) ) as it will be the sorting complexity and the polygon construction will be O(n)

where n is the number of points

till now i\’ve tested it on 100 random points and it worked fine

i think the only case that the algorithm won\’t work as expected is when ALL the points are colinear where a simple polygon is not possible

i searched for any other algos and didn\’t find any, i duno why

thats why i posted this topic

if u have any comment pliz be my guest 🙂