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

Question

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 using 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!!

But can it be (1,1) -> (0,0) -> (1,-1) -> (-1,-1) -> (-1,1) -> (1,1) for example ? Can it pass multiple times by (0,0) ? What are you trying to do exactly ? — krookedking

krookedking krookedking · Accepted Answer · 2011-04-13T09:28:42

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...

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

2 Answers