Creating a Polygon Around an Image

[fletchergames]

I want to create a polygon around an image for better collision detection. Right now, I’m just using the full rectangle around the sprite.

For some of the larger sprites, this isn’t good enough. A circle wouldn’t really work either because of all the tentacles. What I would like to do is define a generic polygon around them. Unfortunately, I don’t know precisely how to do this.

I figure that the first step is to do Breadth First Search from the corner of the image to find all the non-transparent points at the edge of the image. To make sure I find ALL of them, I’ll wrap a 1-pixel box of transparency around the image (just in case any of the tentacles touch the edge and cut off some of the other tentacles from the Breadth First Search).

Now I could use those points to somehow define a polygon, but it might have 1000 vertices connected by 1-pixel-long lines, which is clearly bad. How do I determine which points to use in the polygon?

[bleb]

Once you’ve got your 1000, pixel-long edged polygon, you can reduce the number of vertices without sacrificing important details.

Basically, iterate over each vertex and decide if it’s important or not by looking at it’s two neighbours. So for vertices A-B-C, B is important if the distance from B to the line segment A-C is above a certain threshold. If not, A, B and C are close to collinear and B can safely be removed.
Continue scanning around the polygon until no more vertices are removed.

The other option is to compute the convex hull of the non-transparent pixels and use that for collision detection.

[Kova]

so are those images often replaced? Obviusly the best solution (but not the quickest, best for performance) is to create polygon yourself for every image. I guess you have many of them or user can add his own so you need the algorithm.

[fletchergames]

@bleb

Once you’ve got your 1000, pixel-long edged polygon, you can reduce the number of vertices without sacrificing important details.

Basically, iterate over each vertex and decide if it’s important or not by looking at it’s two neighbours. So for vertices A-B-C, B is important if the distance from B to the line segment A-C is above a certain threshold. If not, A, B and C are close to collinear and B can safely be removed.
Continue scanning around the polygon until no more vertices are removed.

…

That should work. I’ll try that.

@Kova

so are those images often replaced? Obviusly the best solution (but not the quickest, best for performance) is to create polygon yourself for every image. I guess you have many of them or user can add his own so you need the algorithm.

There aren’t alot of images that I want to do this for, and I believe they’re final at this point. So I could create the polygons myself.

Setting up my own polygons manually would definetly be better performance-wise and might actually take less effort.

Even so, I would rather have a method that does this for me so that I can reuse it, so I will try doing it algorithmically first. If that takes too long, then I’ll set up the polygons manually.

Thank you both for your help.

[BloodRain]

I used this in a game and it worked great and fast.I used some final polygons to remeber the coordinates.I used pixel grabber to get an array of colors from the image then get the coordinates of the polygon.