## Identifying the edge of a cloud of points

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Identifying the edge of a cloud of points

Say I have a cloud of points whose locations are specified in Cartesian coordinates. These points are not on a grid, but are randomly scattered. How do I identify the points on the edge of the cloud? If the points were on a regular grid, I'd simply look for maximum and minimum coordinates along each column and row of the grid, but it's not immediately obvious to me how I'd do this in the absence of a grid. Any thoughts would be appreciated!

DannyBoy

Posts: 1160
Joined: Fri Feb 13, 2004 12:56 pm
Location: In the Billiard Room with the Lead Pipe

### Re: Identifying the edge of a cloud of points

My first thought is to pick three points at random (or just the first three) to form a triangle. Then check the fourth point, if it is within the bounds of the triangle ignore it. If it is outside the bounds of the triangle, insert it between the two points it is closest to, then check those two points for a concave angle. If the point has become concave thanks to the addition of the new point, remove it. Then repeat for every other point. Does that make sense?
Note that this has an O(nm) where n is the number of points total and m is the number of points in the cloud, so a worst case run of O(n^2) so you're looking at a slow algorithm for significantly large number of points. There might be a better way but I can't think of it right now.

Wizard

Posts: 3226
Joined: Mon Sep 22, 2003 4:52 pm
Location: ON, CA

### Re: Identifying the edge of a cloud of points

Thanks for the reply, Wiz! It turns out that the term I needed to Google was convex hull and there have been quite a few algorithms developed to address the problem. (When the shape is not convex, then things become quite a bit more difficult it seems!) Anyway, I thought I'd share in case someone else has a similar problem. Merry Christmas, dude!

DannyBoy

Posts: 1160
Joined: Fri Feb 13, 2004 12:56 pm
Location: In the Billiard Room with the Lead Pipe

### Re: Identifying the edge of a cloud of points

What does active instructor and reserve instructor mean in billiards? I was looking for a billiards instructor on a website and it said please select "active instructor" or "reserve instructor" what does that mean?
wourbasi

Posts: 1
Joined: Fri Mar 23, 2012 12:03 am