1
$\begingroup$

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:

Geogebra screen

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.

  • 0
    [this](http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/xn-convexhull.pdf) may help.2012-04-27

2 Answers 2

3

You want a convex hull algorithm.

  • 0
    Because it's cool `;-)` I love them, they always lead to very elegant solutions when describing points, planes, lines and conic sections.2012-04-27
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.