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.

Cuttle

Do you have a programming language you're working with? I would almost qualify this as asking for a library? ... or asking for original research articles. – Fraise

@Fraise It's pure algorithm question, language doesn't matter. – Cuttle

Do you have any guarantee on the input curves? What if your input is your final example. Then you wouldn't find any stacked lines. – Fraise

@Fraise You can assume all shapes are cut out without stacking, all shapes touch each other perfectly, all vertices in touching shapes are perfectly matched, vertices in one shape contain no duplicates, there's no self-crossing and whatever other preconditions which make writing an algorithm easier. – Cuttle

"If a shape has a hole in it." How is this defined/tested? – Aileen

The paths you're looking for are similar to a convex hull. Another way to look at it, you have an initial guess for the path that works, and you want to make a simpler path. You can simplify the path and see if the new path is an improvement. Inkscape does some path simplification. – Fraise

@Fraise Convex hull does have a somewhat similar look, but I don't see how it can be applied to my problem. Paths in my example are convex-y, but it's easy to come up with a counterexample. Paths don't have to be smallest in terms of inner area either. // Simplifying a shape can be done and there're various open-source solutons to this. Inkscape's algorithms (this is the real link) are understandably sophisticated, not sure I'll need something as complex as this. But either way, there're two issues: [...] – Cuttle

[...] (1) I don't have a way to find any path, so there's nothing to simplify. (2) If a found path is close to a shape's border, any simplification is almost guaranteed to put the path outside. So either the pathfinding needs to somehow find a path closer to the "middle" of the shape, or the simplification needs to somehow respect borders of other shapes. // @גלעדברקן Let's say all shapes are defined as Bezier chains [A p₁ p₂ B p₁ p₂ C ... Y p₁ p₂ Z], with optional holes defined the same way. If you don't want to handle holes, feel free to skip it, this case can be handled separately. – Cuttle

(1) A first path is the border that is not stacked. If you look at the border between the the blue and the green, then you decide the blue is "on top", the first guess for the green is to replace the stacked lines with the unstacked lines of the blue. (2) That's not true for "any" simplification. I think you were considering simplifying the interface line, not the non-interface line. – Fraise

@Fraise (1) The already existing path is a path indeed, but I don't know any approach to line simplification that gets from it to anything useful for my case. (2) By "simplification" I mean using less vertices to represent the same line within a threshold of error (and optionally other parameters like keeping sharp angles). Any such algorithm I know is, from a practical viewpoint, essentially random in whether it'll put the simplified line slightly to the left or slightly to the right of the original line (most often both at "random" intervals). I don't know what you mean by "interface line". – Cuttle

Consider the green and blue regions, but ignore the squiggly region. imgur.com/a/Zdz4EOM in one case the blue is on the top. In that case we need to simplify the shaded line from A to B. Pretty much any nodes can be removed to simplify. – Fraise

The interface path is the 'stacked' line as you called it. The line from A to B that is the interface between the two regions. That path is preserved in one shape and removed on the corresponding ocluded shape. – Fraise

I believe you can solve this exactly in the raster domain (ie map the curves/shapes onto a predetermined grid of particular DPI/resolution.) Once solved in the raster domain, you can then approximate the raster solution with a simpler set of curves, or use the raster solution as a guide. Would this be an acceptable answer? If so I can elaborate on how to do it. – Duhl

@Duhl I don't understand how you're going to solve the problem in the raster, but any solution is a solution. – Cuttle

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).

Acid

(1) My reason for working with Bezier curves is that in my case the data is already perfect, with zero error. That is, the touching shapes use exactly the same Bezier segment chain where they're touching each other. This makes me think that at least some preprocessing is better to perform on the curves rather than on polygons. I was also concerned that I would introduce error and cause small holes to appear, but now that I think about it, resulting stacked shapes will be tolerant to error, so working with polygons is probably the way to go in the main part of the algorithm at least. [...] – Cuttle

[...] (2) I haven't actually checked the data and don't know how lines are oriented. I assumed that determining inner areas would be the easy part. I think shapes with holes are encoded as compound shapes. (3) If I understood correctly, this algorithm is going to perform fine in many cases, but the produced path can also get too complex, for example, blue going through only green would hug every bump and have a lot of turns. Not only the line would be too complex, but transforming it into a Bezier curve can cause unwanted edge bleeding. [...] – Cuttle

[...] I assume a pathfinding algorithm for non-zero-sized objects exists, which can be used to avoid touching edges... But then the start and the end of the path would put the fake sized object outside the shape... Is there a reasonable way to put the path as deep inside the shape as possible (furthest from the edges)? (4) What are the names of the relevant graph algorithms? – Cuttle

@Cuttle orientations: cs.stackexchange.com/questions/24171/… . As far away as possible: en.wikipedia.org/wiki/Medial_axis . Visibility: en.wikipedia.org/wiki/Visibility_polygon . – Acid