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 🙂

### Like this:

Like Loading...

*Related*

TeCNoYoTTa

May 25, 2009@ 20:02:34ya3ni eh colinear ya 3amo 3abdala 😀

Jaqoup

May 26, 2009@ 02:21:56“the points are colinear”

means that the points are on the same line