# Find outline of $N$ points in a plane

If I have $N$ point coordinates $P_i = ( x_i, \, y_i )$ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this?

This is what I want to do:

Not that the number of points is typically less than 20. Also I am very familiar with homogeneous coordinates (in 2D and 3D) and how to use them to calculate if a point lies on a line, or while point intersects two lines, or which line joins two points, etc. Maybe I need to use points $P_i = ( x_i, \, y_i , \, 1 )$ and lines $L_i = [ n_x, \, n_y, \, -d ]$ where $n_x$, $n_y$ is the line normal vector, and $d$ is the distance from the origin.

-
this may help. – David Mitra Apr 27 '12 at 13:31

Why do you need to use homogeneous coordinates when your points are given in $(x,y)$ form? – Rahul Apr 27 '12 at 13:38
Because it's cool ;-) I love them, they always lead to very elegant solutions when describing points, planes, lines and conic sections. – ja72 Apr 27 '12 at 14:08