Path: utzoo!attcan!uunet!samsung!rex!wuarchive!texbell!sequoia!rpp386!woody
From: woody@rpp386.cactus.org (Woodrow Baker)
Newsgroups: comp.graphics
Subject: Re: Spline coefficients
Summary: spline coefficients
Keywords: matrix problem, help
Message-ID: <17320@rpp386.cactus.org>
Date: 17 Nov 89 14:08:11 GMT
References: <352@texhrc.UUCP>
Organization: River Parishes Programming, Plano, TX
Lines: 74

In article <352@texhrc.UUCP>, bls@texhrc.UUCP (Brian L. Sumner) writes:
> 
> I am tring to determine a set of spline coefficients, and to do
> so I need to solve the linear system
>     Ax = b
> where A can be a very large (positive definite?) banded matrix.
> This matrix looks like
> 
>     [ A B . . . ]
>     [ B C D . . ]
>     [ . D E F . ]
>     [ . . F G H ] 
>     [ . . . H I ]
> 
> where each of A,B, ... I, is itself a (positive definite?) banded matrix
> with the same number of bands, e.g.,
> 
>     [ a b . . . ]
>     [ b c d . . ]
>     [ . d e f . ]
>     [ . . f g h ] 
>     [ . . . h i ]
> 
> where each of a,b, ... , i, is again a positive definite?) banded matrix
> with the sme number of bands, ...
> 
> The number of levels this continues depends on the dimensionality
> of the problem, but in practice will be 1,2,3, or 4.
> 
> I do not believe that I should just throw such a matrix into a banded
> solver.  The regular structure of this matrix begs for a special (faster)
> technique.  If you are aware of a method to attack this problem with
> I would appreciate it.
> 
> Brian Sumner
> ...!nuchat!convex!texhrc!bls

I am currently struggling with the same problem.  Depending on what you are
trying to do, there are several ways to approach it.  Dr. Dobbs had an article
published a while back, written by a man named Ashdown that dealt explicitly
with this problem.  A deeper article on pur curvetracing using splines,
"Curve fitting with piecewise splines" or somthing like that by Micheal Plass
and M. Stone from Xerox Palo Alto Reasearch center was published in Siggraph
in '83 or '84.  I have a copy at home, as well as some nice reference work
on splines.  There are several nice books on the subject.  My project involvs
being able to take a scanned image, and curve trace it.  I have a rudimentry
spline drawing program that uses a mouse and does splines sort of.  Computing
the coefficients of the spline given the x and y coordinates of the control
points, and the end points, is fairly straight forward, and then evaluating
the spline is very straight forward.  My problem is that I'm lousy at math, and
could not even solve the redbook equations and re-arrange them such that
I could solve for the coefficients.  That has been done now, and I'll be
glad to post them.  Don Lancaster has published them in last months (or
maybe this months) computer shopper.  If you are trying to fit a curve to data
points, then the job becomes much harder.   Basically, you are on the right
track.  You can use a Gauss-Jordan elimination to solve the matrix.  Be sure
to use a piviot row modification however.  Alan Ashdons' article handles
the solving of the matrix nicely.  Plass's paper details an algorithm
that iterativly moves the data points closer to the line.  If you know the
total line length, then you can get a close approximation for t by taking
the distance between each line using a simple difrence squared and doing
a square root, to get delta x and delta y.  Then you can compute the length
of the line between the data points, and travel the curve, adding them up.
This will give you an APPROXIMATION of    t   and you can then divide any
individual segment by this value to get an approximate t for a given x and
y coordinate.  Then you do a least squares fit of the line, and iterativly
drive the x and y coordinates to the closes t value to them along the line.

This is sort of a off the top of the head crude overview of the Plass stuff.
I'd be glad to send a copy to anyone who needs it, just include a stamp....

Cheers

Woody