# 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

## 2 Answers

You want a convex hull algorithm.

-
Can you recommend a particular kind of 2D convex hull algorithm that works well with homogeneous coordinates? – ja72 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

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.

-