# draw line around bunch of points

2 replies to this topic

### #1 2Dcube

2Dcube

Programming sucks

• GMC Member
• 704 posts
• Version:GM:Studio

Posted 03 September 2011 - 05:14 AM

Hey

I have a number of points on screen and want to draw a line around them, like the picture below.

I have tried a number of things (like drawing a line between all points and removing the ones that intersect) but not the desired results yet. I wonder if there's a simpler way to do this?

EDIT: Found a solution where I use a line and have it rotate around the points, breaking off when it hits a point. (hard to explain but kind of in real life if you were to use a rope and span it across the outer points)... let me know if you would like a better explanation

Still, I wonder if there's a mathematical way of doing it.

Edited by 2Dcube, 03 September 2011 - 06:22 AM.

• 0

### #2 Richard

Richard

Retired Staff

• Retired Staff
• 1258 posts

Posted 03 September 2011 - 10:21 AM

What you're computing called the convex hull of the set of points in 2D, and there's a widely used algorithm known as Graham Scan after its author, R L Graham, who published it in 1972. It's perhaps worth noting that you can look for the convex hull of a set of points in 3D, and also that Graham Scan is not easily adapted to that variant of the problem.

The Princeton Computer Science department have quite a nice visual demonstration of how the algoirthm works that I just found through Google. These are the main steps (adapted from their page, again, as they provide a good succinct overview of the algorithm):

• Find an 'extreme' point, such as the point with largest y coordinate. This will be the pivot and is guaranteed to be on the hull.
• Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).
• Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.
Take a look at their demos to give you more of an idea what they mean. I suspect that for now you might want to treat this as an interesting diversion but not one that you want to implement in your game, since you have something that works - but if I'm wrong then you should post back and we might be able to help you implement it!

A point to note is that I believe implementations of Graham scan should avoid actually computing the actual angle between the pivot and each of the other points when sorting them in step 2, because that is a time consuming operation (like your rotating line probably is!) and there are more optimised approaches to doing that sort.

Well - hope that's of interest and not too vague...!

Richard

Edited by Richard, 03 September 2011 - 10:22 AM.

• 0

### #3 2Dcube

2Dcube

Programming sucks

• GMC Member
• 704 posts
• Version:GM:Studio

Posted 11 September 2011 - 05:14 AM

Thanks Richard, that's very interesting. I never knew it would be that complicated. I found a Graham Scan class for Action Script which I think I can turn into GML fairly easily.
• 0

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users