Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Simplifying a path
#11
Interesting. Did you try to figure out what is t for which P(t)==K. From my dealings with Bézier curves over the past years, I would says that it is a bell curve very centered around t=0.5 (even if that specific curve has a cusp or a loop), so using this instead of trying to find the "best" point could save you some time. But of course it only works with single splines and not full strokes.

Also you can save some time by letting Gimp do as much computation for you as possible (since its done in C, somewhat faster than Python). For instance an accuracy criteria could just be the distance between your K=P(0.5) and the point in the middle of the stroke (using Gimp's getPointAtDist()).
Reply
#12
(I am not quite sure if I understand your comments quite right.)

No I have not thought about P(t)=K. But I may some day. And yes there is that fact that the stroke consists of several small arcs, and we cannot tell even on which arc the most distant point K is.

I have the feeling that when searching for an approximate Bezier arc it is important to choose K somewhere close to the middle of the stroke, and I think that the most distant point works well. Also, the splitting is good to do at the same point so that the stroke will never be split anywhere close to either end point but somewhere in the middle. That is why the point K is computed rather carefully.

Finding K is not done by running along the stroke. It is (usually) done by solving the points where the tangent is parallel to the chord. That comes down to solving equations of degree 2. So it should be fast enough.

I did not know about getPointAtDist and I don't find how to call it. But I found now that a stroke has a method get_point_at_dist(). It is the same I suppose.

Yes that error measure is the trouble spot. It should be made faster before even thinking to try to make the code faster elsewhere. But we are measuring distance between something like a stroke and its candidate approximate Bezier arc. There is no guarantee that the curves are close to each other anywhere else but the three points p0,p3,K. The two curves may not run side by side, and the stroke can contain small and large bends. The measure must take into account the whole lengths of the curves somehow; one point is not enough. But anyhow, I am sure the code could be made better with some better idea. This version is working all right, and for an experimental plugin it will do so far.

As a small entertainment I mention that some years ago my Parametric curves plugin (some old version) used as the error measure the area between two curves. The area was computed by summing a large number of narrow triangles. Well, no sense in going back to that solution...
Reply
#13
(05-19-2021, 07:46 AM)Ottia Tuota Wrote: (I am not quite sure if I understand your comments quite right.)

No I have not thought about P(t)=K. But I may some day. And yes there is that fact that the stroke consists of several small arcs, and we cannot tell even on which arc the most distant point K is.

I have the feeling that when searching for an approximate Bezier arc it is important to choose K somewhere close to the middle of the stroke, and I think that the most distant point works well. Also, the splitting is good to do at the same point so that the stroke will never be split anywhere close to either end point but somewhere in the middle. That is why the point K is computed rather carefully.

Finding K is not done by running along the stroke. It is (usually) done by solving the points where the tangent is parallel to the chord. That comes down to solving equations of degree 2. So it should be fast enough.

I did not know about getPointAtDist and I don't find how to call it. But I found now that a stroke has a method get_point_at_dist(). It is the same I suppose.

Yes that error measure is the trouble spot. It should be made faster before even thinking to try to make the code faster elsewhere. But we are measuring distance between something like a stroke and its candidate approximate Bezier arc. There is no guarantee that the curves are close to each other anywhere else but the three points p0,p3,K. The two curves may not run side by side, and the stroke can contain small and large bends. The measure must take into account the whole lengths of the curves somehow; one point is not enough. But anyhow, I am sure the code could be made better with some better idea. This version is working all right, and for an experimental plugin it will do so far.

As a small entertainment I mention that some years ago my Parametric curves plugin (some old version) used as the error measure the area between two curves. The area was computed by summing a large number of narrow triangles. Well, no sense in going back to that solution...

My long practice of programming says that the best algorithm is one that work fast in the most frequent cases, but doesn't fail (or has a fallback) for the pathological cases even if that makes it run much slower for these. So any shortcut is OK if you can evaluate how good/bad the result is.
Reply
#14
I think that here most cases are pathological. But that word "shortcut" was good. I changed the error measuring routine so that it cuts its work short as soon as the error exceeds the allowed value. The running time came down from 41 seconds to 25 seconds in a test case. I really should have realized to do this myself. Thanks for the help.

But the code should be overhauled anyhow. We shall see. Now I think I shall be doing something else for awhile.

The new version is 0.8 in the same place:

http://kmarkku.arkku.net/Path_modify_fil...aster.html
Reply
#15
The Simplify plugin is now again a little faster. The new version is 0.9, here:

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

I remind that the plugin must be regarded as experimental. So, if its working is not ideal please be understanding.
Reply
#16
(05-31-2021, 05:36 PM)Ottia Tuota Wrote: The Simplify plugin is now again a little faster. The new version is 0.9, here:

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

I remind that the plugin must be regarded as experimental. So, if its working is not ideal please be understanding.
This link gives me:

Error 404

Page Not Found

EDIT: Link at post #14 works though, thanks!
Reply
#17
(05-31-2021, 08:46 PM)Zero01 Wrote: This link gives me:

Error 404

Page Not Found

EDIT: Link at post #14 works though, thanks!

You are right. And I cannot edit post #15 any more. So, I give here the link again:

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

Thanks for reporting!
Reply


Forum Jump: