Draw a convex hull using given points in java / android

Question

I have some two-dimensional points, and I want to draw a polygon using these points. This polygon must pass through all the points indicated, which means that there is no such point that is inside or outside the polygon.

For example: if I have points: (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 as follows:

(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 cannot be:

(1,1) → (0,0) → (-1, -1) → (-1,1) → (-1,1) → (1, -1) → (1,1)

To draw a polygon, I use the drawLine function and draw lines from one point to another and, finally, from the last to the first.

Is there any algorithm or code for this?

thank!!

Answer 1

A quick google search: convex shell algorithms , and here's the Java implementation .

EDIT: re-read your question and realized that this is not what you wanted. The name "Convex hull" may be misleading ...

Answer 2

I think your problem is not as trivial as it seems. IMHO is a particular form of traveling salesman problem , but without intersecting paths.