# Polygon simplification that encloses original set of points

I have been trying to implement an optimization for 2D sprite rendering to fight the problem of limited fillrate on mobile devices. The idea is to render textured polygons instead of quads that will map to visible portions of an image with transparency discarding the invisble parts from processing.

Thus far I have implemented at least two approaches that let me find the set of points (outline) of an image with transparency data using Marching Squares (exact outline) and more flexible one, that also alows me to introduce much needed padding (Euclidian Distance Transform).

I have also prepared a triangulation with Ear Clipping, what I am left with is simplification of the set of points generated by first two algorithms mentioned.

Because of the nature of the problem I need an algorithm that can eliminate points, eventually move or introduce new points that result in area-optimized version of the original shape but also guarantees that the new shape encloses the previous one (as I don't want to cut visible parts of an image I am about to render)

I googled and checked my options but so far I haven't found anything usefull. I was looking at Ramer–Douglas–Peucker line simplification algorithm but it doesn't seem to provide guarantees I need.

Is the problem I am facing something common, does it have some kind of name? Any suggestions on how I should approach the given problem?

So far the most obvious simplification was to remove the points that do not add to the curvature (adjacent edges to the vertex create 180 degree angle) but thats not enough.

• in other words get a convex hull (possible add some holes to it) and then triangulate it. – ratchet freak Jan 30 '16 at 19:21
• Convex hulls are not the most optimal solution (consider image of a cross as an example). I would rather want the algorithm to generate concave shape that better fits the actual shape and then triangulate. – Adrian Lis Jan 31 '16 at 20:44