Draw a convex hull using the given points in java/android

I have some 2D points given and i want to draw a polygon using those points. This polygon must pass through all the given points means there is no such point which is inside or outside the polygon.

For example: if i have points like: (0,0), (1,1), (-1,-1),(-1,1) and (1,-1) and if i want to draw a polygon using those then my points array should be sorted in following manner:

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) OR

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

but it cant be:

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1,1)

For drawing the polygon, i am u开发者_高级运维sing drawLine function and drawing lines from one to another point and finally from last to first point.

Is there any algorithm or code available for this?

thanks!!

A quick search in google : convex hull algorithms, and here is a Java implementation.

EDIT : re-read your question and realised it is not what you wanted. The title "Convex Hull" can be misleading...

I think your problem is not as trivial as it seems. IMHO its a special form of the travelling salesman problem, but without intersecting paths.