Finding "outer-most" points

[Jizzler]

Given a set of points, I'm trying to draw an n-sided box around them, so that all are encompassed.

What I came up with is,

- For the starting point, find the northern-most point. Using a point due-north, I could calc the angles of the other points in relation. The next point would be the one with the least angle.

- For the remaining points, similar operation, but the "calc point" will be one that's perpendicular to the last two points.

- For all calcs, check to see if 180 needs to be added, if the next point should be an angle thats > 180.

Anyone have a better way?

[W1zzard]

you sort your points by y-axis value (x works too adjust algorithm accordingly)
start with the point having the highest y axis value, remember its x value, line starts here
find the next smaller y axis value, if that point has x > Xlast then connect it to your polygon
repeat last line until you have no more y axis points moving downward
now go back up from smallest y to largest y, if the point's x value is smaller than the last one's add it to your array.
repeat until you are out of points (back at the top)

make sure to sort before so you only have to increment you array index by one. much faster than having to search for the next element each time

[Jizzler]

-edit-

Yeah, I think I have a way now.

[Kreij]

The three most common algorithms to find the outermost points (or convex hull calculations) are Jarvis' March (what you are doing), Graham's Scan and Chan's Algorithm.

Chan's is a optimized version of the Jarvis March has the best performance.

[Jizzler]

Doh! The forum snafu unsubscribed me and I didn't see your reply. Thanks!

Yeah, I try to come up with something first before finding another (better) way. Modified W1zzards suggestion to a 'quadrant style' point comparison, but you can still end up with odd shapes.

Knowing what it's called made it easy to find some code. A plain ol' Jarvis March implementation will be fine for our needs. Will adapt it to PHP or straight to JS, ugh. ( for internal company website - we use GoogleMaps a lot for visual analysis).