Simplifying a path

[Ottia Tuota]

A new plugin. My try on simplifying paths. If Gimp already has a tool for that job, I hope somebody tells me.

The problem is hard, and all I can say is that mostly the plugin works all right though sometimes its decisions seem strange. Anyway, this is the first published version, and we can think the plugin to be still just experimental, so there is room for improvements. To get the plugin, go to

http://kmarkku.arkku.net/Path_modify_fil...aster.html

scroll to the bottom, and click the download button. You get a zip file. Unzip it and place the one file it contains (simplify_path.py) in your user's plug-ins folder. Then (re)start Gimp. To use the plugin: in the Paths tab, right-click the path you want to simplify and follow the links Tools > Modify path > Simplify.

The plugin takes a path and tries to diminish the number of anchors, doing some smoothing but hopefully not too much. An example: On the left you see a path and on the right its anchors:

   

With default input values the plugin did the following: Below, on the left you see the original path (blue) and the simplified version (red) on top of each other. It may be difficult to see from that picture but there are small differences: many small bends were smoothed out. On the right you see the anchors of the simplified path.

   

The GUI looks as follows:

   

I hope the meanings of the inputs are clear enough.

Of the inputs the last one (about selection) may be the most important in practice. It enables the user to restrict the effect to some subset of the anchors. I shall give examples in another post.

The plugin is based on a neat mathematical idea (I think), but unfortunately, when one starts to implement a neat idea, it usually happens that soon one is in the middle of a mess. The plugin is full of my own ad hoc solutions to various problems. Please report if you find it doing something too odd.

[Ottia Tuota]

I continue about the Simplifying plugin. The last input gives three options to choose from:

• Ignore any selection
  
• Simplify the part inside the selection, preserve the rest
  
• Preserve the part inside the selection, simplify the rest
  

Example 1

First an example of the second choice. I made an elliptic selection and then Selection to path. On the left you see the resulting path with its anchors:

   

Too many anchors at the belly. I made a new selection covering those anchors (middle picture). Then I called the plugin otherwise with default inputs but choosing "Simplify the part inside the selection, preserve the rest". The result is on the right: the part inside the selection was simplified; in this case it happens to mean that those anchors disappeared altogether.

Also, the result is smoother. Namely, Gimp's Selection to path seems to have difficulties here. At the belly the path had several small straight line segments forming angles. I have even seen a case where there was a tiny concave arc! But the result from the plugin is smooth and nicely arching.

Example 2

Next the last choice, "Preserve the part inside the selection, simplify the rest". This is useful when you want to protect some particular anchors from the process of simplification. Consider the 'QR' on the left:

   

I first tried to simplify it by setting only "Preserve straight edges" to Yes. The result (not shown here) was good except that even after setting the "Allowed deviation" to a lower value there were clear gaps between the original and simplified paths. Examining those gaps suggested that certain anchors should be preserved. So I made a selection covering those anchors (in the middle picture) and called the plugin again and choosing "Preserve the part inside the selection, simplify the rest" (and of course "Preserve straight edges" set to Yes). The result was much better (on the right). Zooming in (in Gimp, not here!) one sees that the fit is not perfect but anyhow very good. And the number of anchors came down somewhat.

Example 3

The plugin can also be used to remove anchors from paths. Inkscape's node-removing tool is pleasant in that it tries to preserve the shape of the curve by changing the neighbouring handles. Gimp's tool, on the contrary, seems just to delete an anchor without adjusting handles in any way, resulting in distortion in the curve.

The new plugin may be helpful here. Consider the circle on the left.

   

It is the usual 4-anchor approximation. I made the selection as shown here and called the plugin with "Simplify the part inside the selection, preserve the rest". I also set the "Allowed deviation" a little higher (otherwise nothing happened). I got a 2-anchor approximation of the circle (in the middle). On the right you see the 4-anchor (blue) and the 2-anchor (red) paths on top of each other. Not bad.

[denzjos]

The plugin is working fine to simplify a path after selection -> path. I just need to scale the path a little down. 
   
Nice work Ottia Tuota

[Ottia Tuota]

Good to hear. But the plugin also changes the path a little, so after using it, perhaps some corrections are needed in the path. Depends of course how you are going to use the path. But I believe the plugin finds some usage.

[Krikor]

I liked the result applied to a letter created manually with a mouse.

➤ In red the original stroke - a quick stroke using the mouse.
➤ In blue, the final result after using the plugin to simplify the original path.
   

[Ottia Tuota]

Good. If you use it to smooth a path you may have to set the "Allowed deviation" a little higher. And if there is some troublesome part you can close it in a selection and simplify only it. It is a quirk of the plugin, due to how it works, that the result may be different when it is applied only to a smaller part.

(I might as well explain more closely where that quirk comes from: When we think of smoothing a path we naturally think it as a local operation. We think it as "bottom-up", and that would be one idea to try to design such a plugin. But this plugin works "top-down": Usually it takes first a whole stroke and tries to find an approximate Bézier arc for it. If it does not find a good one, it splits the stroke in two and tries the same for each half. And so on. But if the user restricts the operation to a selection, then the plugin does not start with the whole stroke but with the smaller part. This time it may find approximate solutions that it would miss otherwise. Calculations go different routes. It is a matter of luck actually.)

And restricting the operation to a selection you can set "Allowed deviation" higher without disturbing the rest of the path.

[Ofnuts]

(05-16-2021, 09:20 AM)Ottia Tuota Wrote: The plugin is based on a neat mathematical idea (I think)

Care to expand on that?

By the way, there is a know algorithm to smooth a path, implemented in a C plugin (but unlike yours, it doesn't remove anchors, it just finds the set of colinear tangents that ensure that the paths is smooth on all anchors).

[Ottia Tuota]

(05-16-2021, 09:17 PM)Ofnuts Wrote:

(05-16-2021, 09:20 AM)Ottia Tuota Wrote: The plugin is based on a neat mathematical idea (I think)

Care to expand on that?

By the way, there is a know algorithm to smooth a path, implemented in a C plugin (but unlike yours, it doesn't remove anchors, it just finds the set of colinear tangents that ensure that the paths is smooth on all anchors).

Thanks, Ofnuts, I shall expand on it but not now since I have no time. The great problem for me is that my knowledge about all algorithms out there is very very small, so if googling does not help I tend just to write my own solutions.

Perhaps you could give some hints on how to find such info, like that site you mentioned, or that Welzl's algorithm (that is a pearl!) and such? When you need an algorithm, how and where do you search for one?

This simplifying plugin of mine is meant to simplify, so its main purpose is to delete anchors. But it also creates new anchors. So, it does not rely on the original anchors but makes its own decisions. Smoothing is just a by-product.

[Ofnuts]

To be honest, I work very often the other way. It's not "I have this problem, how can I solve it", it is more like "This solution looks cool, what kind of Gimp problem could it solve?". And IIRC Welzl's algorithm (found on WIkipedia) is pretty much the latter. But I admit I must be some kind of science pervert because my Wikipedia surfing often leads me to some rather hardcore engineering/math articles

Otherwise, asking the question in my favorite search engine (DuckDuckGo, not Google) very often elicits hits on StackOverflow or Wikipedia or both and then either they are the answers or they have usable pointers to answers.

[Ottia Tuota]

Attached you find some explanations on the ideas behind the Simplify plugin. Pardon the long-windedness. It is so rare that anybody shows interest in the mathematical side of things. (And no fear: I did not include any real mathematics, like formulas and such.)


  Simplify_text.pdf (Size: 159.66 KB / Downloads: 587)