# Simple Polygon Construction

Mar

2009

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 Else Add p to tempStack End ForEach While !tempStack->Empty() Add tempStack->top() to Polygon toReturn tempStack->pop() 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 :)

“25/05/2009„

“26/05/2009„