helper.knot_removal returns incorrect result (+ fix)

[tomas16]

Describe the bug

I used knot_insertion to split a NURBS curve, then tried to use knot_removal to merge the two parts again. The output was different from the original: the curve had the wrong shape because the control points computed by knot_removal are incorrect.

I compared the implementation to the NURBS book, and there are 2 bugs in it:

• The algorithm in the book doesn't distinguish between the ctrlpts input and the internal working copy ctrlpts_new. The algorithm in the book writes to and reads from the control points, but the geomdl version writes to ctrlpts_new and reads from ctrlpts, so doesn't pick up its own changes.
• The while j - i >= t condition is while j - i > t in the book.

With these 2 changes, I got the correct result. Patch attached.

Btw I highly recommend having a round trip knot_insertion, knot_removal as a test.

Configuration:

• Python version: 3.11.9
• geomdl install source: PyPI
• geomdl version/branch: 5.3.1

knot_removal.patch

[portnov]

See also: #135.

[tomas16]

I found an additional issue: the algorithm always tries to remove num knots, even when the various checks come out above tolerance. Patch attached.

Explanation:

• The algorithm was missing the if t == 0: return condition.
• Once that's added in, the t += 1 index fix is incorrect. A python loop for t in range(0, num) will never have t==num at the end. However in the book, the authors write C-like pseudo-code. A loop like for (int t=0; t<num; t++) results in t==num at the end. Since we now also have a break inside the loop, "fixing" t after the loop becomes complicated, so instead I replaced it with a while loop that behaves like the original C-style loop in the book.

Finally, this function should also output t as the actual number of knot removals. Again, the book mentions t is supposed to be one of the outputs. I didn't output it in the patch to not break the rest of your code. (I added it in my version though, because I need it)

knot_removal.patch