W3C home > Mailing lists > Public > public-svg-wg@w3.org > April to June 2009

Fwd: Re: Smooth curves passing through/near a set of points. [ISSUE-2282]

From: Doug Schepers <schepers@w3.org>
Date: Fri, 19 Jun 2009 12:44:26 -0400
Message-ID: <4A3BC06A.6080907@w3.org>
To: SVG WG <public-svg-wg@w3.org>
Forwarded from Patrick Ion.

-------- Original Message --------
From: Patrick Ion <ion@ams.org>
Subject: Re: Smooth curves passing through/near a set of points. 
[ISSUE-2282]
Date: Fri, 19 Jun 2009 09:47:03 -0400
To: W3C SVG Public Working Group <public-svg-wg@w3.org>

In reply to postings from Chris Lilley and Doug Schepers on which I
was CC'd:

On Jun 11, 2009, at 11:34 AM, Chris Lilley wrote:
> A couple of years ago, at TPAC, we were discussing a class of
> curves with the property of passing through a set of points (or
> near, for some definition of near), and differing from the curves
> that SVG already has (cubic and quadratic Beziers) or might have
> (non-uniform rational b-spline curves) in that no off-curve control
> points are used to define the curve, only the on-curve knots.
>
Yes, we did.
> I suppose these are piecewise curves with some fairing or
> smoothness property where the pieces join.
No, they are not piecewise curves with fairing.  That was part of
their properties I was struck by.

> Does this ring any bells? I can't even recall the name for that
> class of curves, sorry.
The class of curves I was calling harmonic or Steiner interpolants.
Steiner because
in the case of three points you get the classical Steiner ellipse
through the points.
It is not really  something that's widely known and appreciated.
It's probably best to
explain the situation myself (see below).

They are smooth curves in their ideal forms, and  they involve
transcendental
functions (i.e., trigonometric ones) in their calculation.  So
digitally they are
effectively polynomially approximated and thus not strictly smooth
($C^\infty$, to
use TeX coding); but then neither is anything else.  Actually there
ought to be
an algebraic equation for any given interpolant curve of this class,
but it seems
computationally demanding to find it, and you don't need it  to plot,
just a Discrete
Fourier Transform of order about the number of points involved, so
usually not much.

> We have a couple of use cases for such curves, now; one is for
> graphing/charting applications where it is desired to run a smooth
> (for some definition of smooth) curve through a set of 2D points
> rather than joining them by a polyline.
Harmonic interpolants are particularly nice for polygonal situations.

> The second is to run a curve through a set of 3D points (where the
> 3D space is a colour space) to produce colour gradients from a list
> of colours, without perceptual discontinuities. Current gradients
> effectively connect colours by polylines, so there is a perceptual
> discontinuity at each colour stop.
You can do the same job in more dimensions in a similar way.   In
fact, harmonic interpolants
have been used to draw roller-coasters (Achterbahn) in 3D, as well as
the Nurbergring race
track in 2D.

Finally then let me add some notes on the very basics of this I wrote
some time
ago.  I have some other materials around, and I even had a Java
applet that let
you click points and then drew the interpolant.  I don't know if I
can find that
quickly.  I could do something similar in GeoGebra fairly easily, I
think.  One of the
problems with the few pages of notes is they don't have the obviously
needed
diagrams.

For the fundamental point that amounts to the decomposition of
polygons into linear sums of standard regular polygons (i.e., into
harmonic
components) illustrated in applets, see
http://www-personal.umich.edu/~pion/WebGeom/index.html
This is not an actively maintained web site, but it's where the
applets are
exposed publicly.

The short notes I have now put there too:
http://www-personal.umich.edu/~pion/WebGeom/Steiner_ellipse_letter.pdf

I think harmonic interpolants are under-appreciated.  I anyone has
any questions
I'd be happy to address them and try and prepare a better
exposition.  The rough
notes from 2005 may not use notation that everyone likes.

Then Doug (June 17, 2009) pointed out the very interesting work of
Raph Levien,
and, in particular, his thesis, which looks very nicely done.  I'm
impressed too by
the presence of real working software to back it all up, such as
ppedit that runs
straight away on my Mac.

The Steiner interpolation mentioned above, to use some of Levien's
terms,
does not have extensionality (which does not seem to me  to be a
necessary
   property),  is round, does not have clear monotone  curvature
properties
but has nice visual ones, and is smooth ($C^\infty$) and truly global
(which can
be seen as a disadvantage).

Again, I'd be very happy to engage in conversation with anyone about
some of
these things, and utterly delighted if it can help SVG in any way.  I
hope one
day we'll be able to do scientific documents with text, diagrams and
formulas
in some integrated way.

All the best,

	Patrick







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Patrick D. F. Ion

Associate Editor     [mailto: i@a.org where i=ion and a =ams]
Mathematical Reviews
416 Fourth Street
Ann Arbor, Michigan  48103, USA
Tel: [1]-(734)-996-5273      FAX: [1]-(734)-996-2916
Math Reviews
<http://www.ams.org/mr-database/>
                              <http://www.ams.org/publications/60ann/
AnniversaryYear.html>

University of Michigan   [mailto:p@u.edu where p=pion and u =umich]
                                              Campus Mail Stop: 4820

W3C Math Working Group Co-Chair            <http://www.w3.org/Math/>
MathML  (now becoming MathML3)             <http://www.w3.org/TR/
MathML/>

AMS Math on the Web pages                         <http://www.ams.org/
mathweb/>

MSC2010 Revision                                          <http://
MSC2010.org/>
MSC 2010 Draft as TiddlyWiki                       <http://
MSC2010.org/MSC-draft.html>
**********************************************************
Electronic Mail is not secure, may not be read every day,
and should not be used for urgent or sensitive issues.
Received on Friday, 19 June 2009 16:44:34 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 19 June 2009 16:44:36 GMT