Optimizing a vector image by removing unnecessary points and stacking shapes

Question

I need to optimize a vector image with filled shapes constructed from bezier lines. Input image and how shapes look when separated:

I want to optimize the image by removing unnecessary lines and relying on stacking of shapes to preserve the look, but with much fewer vertices. Result shapes should look like this:

This problem can probably be broken down into separate steps:

1. Detecting stacked lines. This is more or less straightforward: calculate points along a line, find vertices along them. If vertices are stacked, it becomes trivial.

2. Finding bezier paths through filled areas of other shapes. An algorithm for this is likely to already exist, but I don't know it. (I really need help here.) Also it's unclear what shapes to go under. Maybe I should solve all possibilities and compare. It'll probably become clearer once I get to it. (Hints/suggestions are welcome.)

3. Finding optimal order of stacking so that the number of vertices is minimal. This sounds painful for someone not heavily into algorithms like me, but this seems to be some sort of minimization of number of vertices through different "paths", so can be done. (Correct me if I'm wrong.)

4. If a shape has a hole in it, it probably means that everything inside is to be stacked on top of it, so it's a separate simple case in which no extra calculations are needed.

Overall, the second point seems to be the most (the only?) problematic, so I need a nudge in the right direction.

In terms of the sample image, how do I find a bezier path for the potentially obscured part of the green shape to go through the blue shape (and optionally the yellow shape) and vice versa, for the blue one to go through the green one? I don't need the path to be the shortest one, I need it to have the least vertices in it.

Essentially, I need to find these paths with minimum number of vertices. Feel free to ignore the rest as irrelevant context.

Answer 1

I see multiple questions that are difficult in their own right here. Some thoughts:

Working directly with Bézier curves seems difficult. My suggestion would be to approximate them by polygons, or maybe by pairs of polygons, one sampled and one inscribed. If the latter, you’ll need to consider the second derivative of the curve to determine whether it’s convex or concave or if it transitions from one to the other (cut it at the inflection point if so).

The curve direction can identify a hole. If the boundary curves are oriented so that the right hand side is inside the shape, then the counterclockwise curves represent holes. For simple Bézier shapes, every shape containing part of the corresponding clockwise boundary must be stacked in front. Clockwise/counterclockwise direction of a simple polygon can be tested via signed area.

Curve simplification is a shortest path problem, but the metric is not Euclidean. Suppose that we know the stacking order of some simple polygons. Given one of these polygons P, we form the polygon Q consisting of the union of P and every polygon in front of P that intersects it. We want to continuously deform the parts of the boundary of P that lie in the interior of Q so as to minimize the number of edges. For each part, we should be able to simulate a breadth-first search from one endpoint to the other in the implicit infinite graph via visibility algorithms.

Optimizing the stacking order feels NP-hard. I haven’t worked out a reduction; this is just my gut feeling as a credentialed algorithm designer knowing that a seemingly simpler ordering problem – feedback arc set – is NP-hard, and that simple polygons offer a lot of freedom for constructing gadgets. My suggestion in practice would be to compute the convex hull of each polygon and declare that the order of two polygons whose hulls do not intersect does not matter. Take the complement of this graph and enumerate its orientations that do not contain a cycle (there are efficient algorithms for this). For each orientation, perform a topological sort to extend it to a total order and then optimize the curves accordingly. If this is still too expensive, I’d reach for a genetic algorithm, specifically BRKGA with the natural decoder (each chromosome contains one number per shape; sort the shapes by number).