#7169 closed enhancement (fixed)

Reported by: Owned by: Alan Thomas Alan Thomas normal OGR_SF svn-trunk normal dxf

Description

When a spline path is requested for a leader in a DXF file, we need to interpolate a cubic spline between those points with particular start and end tangents. This is accomplished by solving a linear system for the spline control points using a QR decomposition solver I wrote for another project (originally in C) some time ago. This isn't the speediest or cleanest implementation of cubic spline interpolation the world has ever seen, but being in an MIT-licensed environment places limits on the things that can be done by a non-expert, and in any case, efficiency is not really essential for a conversion tool like GDAL. Accuracy seems to be adequate for most purposes.

comment:1 Changed 13 months ago by Even Rouault

For linear system solving, you may have a look at alg/thinplatespline.cpp. There are 2 code paths one using Armadillo when available (which has probably a clever implementation underneath), and another code path, in matrixInvert() using Gauss-Jordan elimintation method. So it would be good if we could somehow have a single generic solver used in both the thinplatespline code and your new code (your QR solver is perhaps better than the Gauss-Jordan one)

comment:2 Changed 13 months ago by Alan Thomas

That is a good idea. Looking at the way things are set up, it might be possible to create a new file `gdallinearsystem.cpp` with a function `GDALLinearSystemSolve`. However, without a proper test case, any refactoring of thinplatespline would be risky. (From a quick check, the single test in tps.py doesn't even appear to call into the solve() function.)

Also I imagine anything using Gaussian elimination will be more efficient than my QR solver! Ideally we would have an LU solver; that seems to be the most common way to solve general linear systems. But like I said, I don't know too much about numerical methods.

comment:3 Changed 13 months ago by Even Rouault

TPS code is exerced in a number of locations by the autotest (you can see solve() being covered : https://rawgit.com/rouault/gdalautotest-coverage-results/master/coverage_html/alg/thinplatespline.cpp.gcov.html ). gcore/transformer.py tests the transformation itself (and a number of other places do TPS based warping). I'd say that if autotest still pass, we're probably good

comment:4 follow-up:  5 Changed 12 months ago by Alan Thomas

Do you have any comments on https://github.com/ThinkSpatial/gdal/commit/fd67c5a14bb38f8ac90462caae8bb62633900dea ? I have tested it on a Linux box with Armadillo (a package which is a real pain to set up!) and it seems to work just as well as without Armadillo.

comment:5 in reply to:  4 ; follow-up:  6 Changed 12 months ago by Even Rouault

Do you have any comments on https://github.com/ThinkSpatial/gdal/commit/fd67c5a14bb38f8ac90462caae8bb62633900dea ?

Looks good to me (besides the memory leaks in the error code path I pointed out)

I have tested it on a Linux box with Armadillo (a package which is a real pain to set up!) and it seems to work just as well as without Armadillo.

Ah, on Ubuntu (and likely Debian too), this is just a matter of "apt install libarmadillo-dev"

comment:6 in reply to:  5 Changed 12 months ago by Alan Thomas

Ah, on Ubuntu (and likely Debian too), this is just a matter of "apt install libarmadillo-dev"

Heh, it didn't even occur to me that such a specialised package would be in apt.

comment:7 Changed 12 months ago by Alan Thomas

In 41083:

Refactor linear system solver out of thinplatespline (refs #7169)

comment:8 Changed 12 months ago by Alan Thomas

Resolution: → fixed assigned → closed

In 41084: