How to find outer corners of 2D polygon from set of points

Hello everyone, I have been burning some brain cells on this problem for a few hours now and no luck yet. I've tried quite a few things with no success and decided to seek help.

Alright, so I currently have a 2x140 vector of 140 x-y coordinates for points which when plotted form what looks like a rectangular grid. I'm trying to find the 4 points which correspond to the 4 outer corners of this 4-sided polygon. The main problem I'm having is that the polygon is wider at the top than at the bottom and is not exactly level with the x or y axis so I can't just find the min/max x/y coordinates and call those the corners. Here is a figure of the situation for clarity: http://imageshack.us/photo/my-images/43/207756bwnf8jcy.jpg/

Thanks for your time!

Juan

Answer 1

[Walter Roberson]

If you take the bounding box and if you have an estimate of the maximum number of samples per direction, then you can convert each point in to a pair of array coordinates with some simple arithmetic manipulation, and from that pair, sub2ind() will convert to a linear array index. Start with an array of 0's and set the grid to 1 at each of those linear indices.

Now you can search for the corners in that binary grid.

Once found, convert those locations back to linear indices, match against the points that created those same linear indices, look up the original values at those locations.