Refining a boundary

Refining a boundary

Post by Dmitry Epstei » Tue, 15 Jul 2003 16:16:29






> in message

>> > Dmitry,

>> > you may have a look at the Fourier Series approach:
>> > http://www.fho-emden.de/~hoffmann/softpoly23062003.pdf

>> > The N point polyline (N-1 segments) is closed by a Bzier
>> > path and represented by two Fourier Series for x and y.
>> > Fourier Series can be interpolated for any M. An example
>> > is in the chapter "Between Contours" which describes
>> > interpolations between paths with originally N1,N2 points.
>> > The polylines can be self intersecting, no restrictions.

>> > Best regards --Gernot Hoffmann

>> Thanks.  From what I could figure out, with the maximum
>> number of harmonics the interpolating curve simply connects
>> all of the dots, and with fewer harmonics it fits a smooth
>> line to the point set, sort of like the least squares method.
>>  I can see how I could use this to reduce the number of
>> points in a polyline, but I am not sure how I could refine a
>> polyline in this manner.

>> Dmitry

> Dmitry,

> Actually I dont know what you are meaning by "refine".
> You can use MORE new points than originally given - thats
> the pleasant feature of the Fourier interpolation, because
> this is based on a function system. As you say - its a least
> squares method, and the function system is orthogonal with
> respect to the range 0..2*pi or the parameter s=0..1.

> And these new points can be taken from the path with deleted
> higher harmonics - the smoothed path.

> Unfortunately the method doesnt create equal segment lengths
> for equally spaced parameters s+ds .
> Its simple to make all but the last segment equally long, but
> the last fills the gap and is therefore shorter.
> The method is rather crude, increment s+ds until the segment
> is long enough. A more subtle method would iterate ds,
> starting by the last ds. This fails easily if the curve was
> "regular" before and is "irregular" later.

> An example and additionally the formulas are in the updated
> doc.

> Equal segment lengths (including the last) require IMO a
> global iteration.

> Best regards --Gernot Hoffmann

Thank you for the explantion.  One question that comes to mind is
how best to choose the cutoff frequency, with a generally arbitrary
number of points in the original polynom?

--
Dmitry Epstein
Northwestern University, Evanston, IL.  USA
mitia(at)northwestern(dot)edu

 
 
 

Refining a boundary

Post by Hans-Bernhard Broeke » Tue, 15 Jul 2003 18:42:48


[...]

Quote:> Thank you for the explantion.  One question that comes to mind is
> how best to choose the cutoff frequency, with a generally arbitrary
> number of points in the original polynom?

There is no "best" choice, because of the TANSTAAFL principle: "there
ain't no such thing as a free lunch".  

_You- have to make up your mind about a criterion where to stop the
Fourier series, or you'll end up with a very complicated way of
describing a polyline with sharp corners, instead of the smooth curve
you wanted.  The fine-pitched polyline you're trying to construct is a
discretized version of some smooth curve which isn't actually in your
input, so you have to decide what that smooth curve will be, in one
way or another.  Splines can provide a somewhat natural method of
doing it, and so can these Fourier series suggest in this sub-thread,
but not without some design decision left to you.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Refining a boundary

Post by Dave Eberl » Tue, 15 Jul 2003 21:39:30



Quote:> Thank you for the explantion.  One question that comes to mind is
> how best to choose the cutoff frequency, with a generally arbitrary
> number of points in the original polynom?

The ultimate flaw, in my opinion, about using "frequency space"
methods in a graphics problem that is inherently spatial.
Computer graphics researchers developed the concept of
"local control" for a reason.  Throwing away high-frequency
terms via Fourier series and not knowing the effect on the curve
from a geometric perspective would make me shy away from
such methods.  (In fact I do shy away from such methods.)

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Refining a boundary

Post by Gernot Hoffma » Wed, 16 Jul 2003 03:37:44



> Thank you for the explantion.  One question that comes to mind is
> how best to choose the cutoff frequency, with a generally arbitrary
> number of points in the original polynom?

Dmitry,

the Fourier interpolation was originally intended for noisy data,
like measured contour points. The cutoff frequency should be selected
interactively, like the intensity of sharpening in image processing.

If your polgons have some common features you may easily find a general
cutoff frequency "M" by trial and error, e.g. M = N div 5 .

In other applications I am using natural splines. These hit all points.
Other splines perform a kind of averaging and dont hit the points.
IMO, there isnt just one unique solution how to replace an N1 polygon
by an N2 polygon or a polyline by a smooth function.

In the moment I see the bigger problem in the creation of equal segment
lengths, including the last.

Best regards  --Gernot Hoffmann

 
 
 

Refining a boundary

Post by Dmitry Epstei » Wed, 16 Jul 2003 06:29:18





> in message

>> Thank you for the explantion.  One question that comes to
>> mind is how best to choose the cutoff frequency, with a
>> generally arbitrary number of points in the original polynom?

> Dmitry,

> the Fourier interpolation was originally intended for noisy
> data, like measured contour points. The cutoff frequency
> should be selected interactively, like the intensity of
> sharpening in image processing.

> If your polgons have some common features you may easily find
> a general cutoff frequency "M" by trial and error, e.g. M = N
> div 5 .

> In other applications I am using natural splines. These hit
> all points. Other splines perform a kind of averaging and
> dont hit the points. IMO, there isnt just one unique
> solution how to replace an N1 polygon by an N2 polygon or a
> polyline by a smooth function.

Come to think about it, maybe I don't need smoothing after all.  
The examples in your docs do indeed show something like "noisy
data", which obviously need smoothing.  That is not my case though.  
There *may* be some point in smoothing the contour in my case, but
it would have to be looked at from the physics perspective, which
is not very obvious (the polygon is approximating the shape of a
planar crack propagating through an elastic material).

Quote:> In the moment I see the bigger problem in the creation of
> equal segment lengths, including the last.

Perhaps I am mistaken, but the idea of a single function spanning
the entire curve (polynom or a finite Fourier series) appeals to me
more than many splines stitched together.  Because what happens if
some segment of the new polygon starts on one spline but ends on
another?  How do I even know on what spline it ends?

--
Dmitry Epstein
Northwestern University, Evanston, IL.  USA
mitia(at)northwestern(dot)edu

 
 
 

Refining a boundary

Post by Gernot Hoffma » Wed, 16 Jul 2003 15:24:33



> Come to think about it, maybe I don't need smoothing after all.  
> The examples in your docs do indeed show something like "noisy
> data", which obviously need smoothing.  That is not my case though.  
> There *may* be some point in smoothing the contour in my case, but
> it would have to be looked at from the physics perspective, which
> is not very obvious (the polygon is approximating the shape of a
> planar crack propagating through an elastic material).

> > In the moment I see the bigger problem in the creation of
> > equal segment lengths, including the last.

> Perhaps I am mistaken, but the idea of a single function spanning
> the entire curve (polynom or a finite Fourier series) appeals to me
> more than many splines stitched together.  Because what happens if
> some segment of the new polygon starts on one spline but ends on
> another?  How do I even know on what spline it ends?

Dmitry,

natural splines are a good choice as well. Like for all splines, the
parts are stitched together with point-, tangent- and curvature-
continuity. This means, the curve appears for the user "as one function"
but internally its handled piecewise.
The striking argument for the Fourier Series is the simplicity.

Here is an example for natural splines (made periodical by adding first
points beyond the last and last points before the first):
http://www.fho-emden.de/~hoffmann/spline04112001.pdf

I am sure you will get the best support by Dave, if you want to use
splines.

I am travelling now, therefore I cant respond in the next weeks.

Best regards  --Gernot Hoffmann