Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
this may help. –  David Mitra Apr 27 '12 at 13:31
add comment

2 Answers

up vote 2 down vote accepted

You want a convex hull algorithm.

share|improve this answer
    
Can you recommend a particular kind of 2D convex hull algorithm that works well with homogeneous coordinates? –  ja72 Apr 27 '12 at 13:31
1  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.