Insert and then remove knot - Initial and final control points are not the same

[carlos-adir]

Describe the bug I got a particular case that, when I add a knot to a BSpline.Curve and then remove the same knot I don't get the previous control points.

To Reproduce Run this code

from geomdl import BSpline
from geomdl.operations import insert_knot, remove_knot

curve = BSpline.Curve()
curve.degree = 2
curve.ctrlpts = [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6]]
curve.knotvector = [0, 0, 0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1, 1]
print(curve.ctrlpts)

knot = 0.5
insert_knot(curve, [knot], [1])
print(curve.ctrlpts)
remove_knot(curve, [knot], [1])
print(curve.ctrlpts)

Then I get the result

[[0.0, 0.0], [1.0, 1.0], [2.0, 2.0], [3.0, 3.0], [4.0, 4.0], [5.0, 5.0], [6.0, 6.0]]
[[0.0, 0.0], [1.0, 1.0], [2.0, 2.0], [2.75, 2.75], [3.25, 3.25], [4.0, 4.0], [5.0, 5.0], [6.0, 6.0]]
[[0.0, 0.0], [1.0, 1.0], [2.0, 2.0], [3.25, 3.25], [4.0, 4.0], [5.0, 5.0], [6.0, 6.0]]

Expected Behavior The initial and the removed control points should be the same.

Configuration

• Visual Studio Code
• Python 3.9.1
• MSC v.1927 64 bit (AMD64) on win32
• geomdl.version = 5.3.1

[carlos-adir]

I made a test function with a random number of insert at random positions

from geomdl import BSpline
from geomdl.operations import insert_knot, remove_knot
import numpy as np

def test_curve_insertremove_oneknot_random():
    ntests = 1000
    dim = 3
    for i in range(ntests):
        p = np.random.randint(1, 6)
        n = np.random.randint(p+1, p+11)
        ctrlpts = np.random.rand(n, dim).tolist()
        curve = BSpline.Curve()
        curve.degree = p
        curve.ctrlpts = ctrlpts
        curve.knotvector = p*[0] + list(np.linspace(0, 1, n-p+1)) + p*[1]

        knot = np.random.rand()
        times = np.random.randint(1, max(2, p))
        insert_knot(curve, [knot], [times])
        remove_knot(curve, [knot], [times])
        np.testing.assert_allclose(curve.ctrlpts, ctrlpts)

[cafhach]

Why should the resulting control points be identical to the initial ones?

[portnov]

Well, because knot insertion and knot removal are the opposite processes for one another, so they should cancel each other, shouldn't they? :)

[portnov]

As far as I understood, implementation of knot insertion and removal processes in geomdl is taken directly from The NURBS Book. Unfortunately, the book has a number of typos :/

[cafhach]

They appear to be opposite processes, but are they really wrt the control points?

[portnov]

IMHO they should be. Refer to The NURBS Book, 2nd ed, p. 5.4.

[portnov]

In Sverchok, for example, this test works: https://github.com/nortikin/sverchok/blob/master/tests/nurbs_tests.py#L422 Note that in Sverchok insertion and removal of a knot several times is implemented very straightforward, by repeating the whole procedure several times. In the NURBS Book there is an algorithm which requires less calculations, but as far as I understood there are typos there — at least it did not work correctly for me right away; I tried to debug it for some time, but in the end I just reverted to the dumb but working algorithm.

[carlos-adir]

I made a nurbs library which computes the remove_knot by fitting the curve into another.

That is, since we know the knotvector before and after removal, we have the basis functions and we can find the best control points that approximates the curve with more knots.

For this example, the 'approximation' is in fact the original curve before knot insertion.

It's better described here: https://compmec-nurbs.readthedocs.io/en/latest/rst/theory-fitting.html

[carlos-adir]

I don't understand why this issue was closed as completed since it still a problem