Find outline of $N$ points in a plane

Question

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.

Answer 1

You want a convex hull algorithm.

Answer 2

Many Computational Geometry books, including Discrete and Computational Geometry by Satyan Devadoss and Joseph O'Rourke (Princeton U. Press, 2011) treat geometrical approaches to finding the convex hull of a point set in the plane, as well as the computational complexity issues associated with this problem. Of course there is also the same issue in higher dimensional spaces.