Convert sprite to shape

[lizard]

How to convert an external border of the sprite in the polygon? Google gives horrible words like triangulation for convex objects, Graham-scan and pattern recognition. Found that, but how to find external border of sprite? I have a very rough idea about the edge-detection, but would love to hear your opinion.
PS. Yes, I'm too lazy to manually calculate the vertex.
PPS. Yes, it's hard to code image processing in Love only with mapPixel()

[TechnoCat]

Graham-scan should find the convex hull of any set of points. Is that what you are looking for? I believe it is O(nlog(n)) even.

I'm assuming your "points" will be any pixel with an alpha in this case.

[vrld]

First of all: This (segmentation) is not an easy problem. You won't need polygon triangulation, Grahams scan (used for finding the convex hull of some points, i.e. the minimal polygon that contains all those points) or pattern recognition though.
Second: you won't be able to avoid calculating the vertices and using mapPixel/getPixel.

Just to check if I understood you correctly: You want to get the outline of that what's on an image, i.e.:

outline.png (3.83 KiB) Viewed 2274 times

If you use an alpha value of 0 for the outside of the sprite (like in the image above), then congratulations, because you basically already have segmented the image.

To actually extract the border's shape, you can scan the image from top to bottom, and check if a pixel lies on the border of the shape, i.e. if it has neighboring pixels that are on the inside and neighboring pixels that are on the outside of the shape. If it does, add it to a list of vertices (you will need to have two vertex lists, one for the left border and one for the right).

When you are done, reverse the left border vertex list and add it to the right border. You now have a list of all border vertices in clockwise order.

Because there are so many vertices, you will need to sort out some of them. One way to do this is to only consider every 5th or so vertex and discard the rest.

A better way is to check if three vertices make a sharp corner: Get the distance of the middle vertex to the line spanned by the outer vertices. If it is lower than a threshold, discard the middle vertex. Repeat until no vertices can be discarded.

I hope that was comprehensible :/

[lizard]

Thank you for suggestion.