## Refining a boundary

### Refining a boundary

Hi,

My problem has nothing to do with graphics, but it does have to do
with meshing, so I though this might be a good place to ask.

I have a boundary (an open-ended, non-self-intersecting curve) in a
plane, defined by N straight-line segments.  I need to replace it
with M segments of approximately equal length, while staying close
to the shape of the original curve.

Sorry if I am using wrong terminology - I don't know much about
computational geometry.  Any tips or references would be
appreciated.

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

### Refining a boundary

Quote:> My problem has nothing to do with graphics, but it does have to do
> with meshing, so I though this might be a good place to ask.

> I have a boundary (an open-ended, non-self-intersecting curve) in a
> plane, defined by N straight-line segments.  I need to replace it
> with M segments of approximately equal length, while staying close
> to the shape of the original curve.

This might be relevant:
http://www.magic-software.com/Documentation/BSplineReduction.pdf

--
Dave Eberly

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

### Refining a boundary

> Hi,

> My problem has nothing to do with graphics, but it does have to do
> with meshing, so I though this might be a good place to ask.

> I have a boundary (an open-ended, non-self-intersecting curve) in a
> plane, defined by N straight-line segments.  I need to replace it
> with M segments of approximately equal length, while staying close
> to the shape of the original curve. ...

> Thanks,
> Dmitry

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

### Refining a boundary

> in message

>> My problem has nothing to do with graphics, but it does have
>> to do with meshing, so I though this might be a good place to

>> I have a boundary (an open-ended, non-self-intersecting
>> curve) in a plane, defined by N straight-line segments.  I
>> need to replace it with M segments of approximately equal
>> length, while staying close to the shape of the original
>> curve.

> This might be relevant:
> http://www.magic-software.com/Documentation/BSplineReduction.pd
> f

Thanks for the link...  Couldn't understand much - too much
unfamiliar terminology.  But what it seems to do is reduce the
number of points in the polyline, which would typically be the
opposite of what I need.  Perhaps the method can be adapted for
refining too?  I can't tell.  It is also rather important that the
segments in the new polyline have more-or-less equal length.  Can
this B-spline method do that?

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

### Refining a boundary

> in message

>> Hi,

>> My problem has nothing to do with graphics, but it does have
>> to do with meshing, so I though this might be a good place to

>> I have a boundary (an open-ended, non-self-intersecting
>> curve) in a plane, defined by N straight-line segments.  I
>> need to replace it with M segments of approximately equal
>> length, while staying close to the shape of the original
>> curve. ...

>> Thanks,
>> Dmitry

> 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 Epstein
Northwestern University, Evanston, IL.  USA
mitia(at)northwestern(dot)edu

### Refining a boundary

Drats!  Looks like my replies didn't make it the first time around.
I'll try again :(

> in message

>> Hi,

>> My problem has nothing to do with graphics, but it does have
>> to do with meshing, so I though this might be a good place to

>> I have a boundary (an open-ended, non-self-intersecting
>> curve) in a plane, defined by N straight-line segments.  I
>> need to replace it with M segments of approximately equal
>> length, while staying close to the shape of the original
>> curve. ...

>> Thanks,
>> Dmitry

> 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 for the reply.  From what I understand, with the maximum
number of harmonics your interpolation routine simply connects all
the dots, while with fewer harmonics it fits a smooth line to the
point set, sort of like the least squares method?  But I am not
sure how I could use this to refine the polyline and redistribute
points evenly on the line.

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

### Refining a boundary

> in message

>> My problem has nothing to do with graphics, but it does have
>> to do with meshing, so I though this might be a good place to

>> I have a boundary (an open-ended, non-self-intersecting
>> curve) in a plane, defined by N straight-line segments.  I
>> need to replace it with M segments of approximately equal
>> length, while staying close to the shape of the original
>> curve.

> This might be relevant:
> http://www.magic-software.com/Documentation/BSplineReduction.pd
> f

Thanks for the link.  Unfortunately, I couldn't understand much of
what is there, but from what I can see this method is for reducing
the number of points on a polyline, which would be the opposite of
what I need.  Can it perhaps be adapted to refine the polyline with
equally spaced points?

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

### Refining a boundary

> Thanks for the link...  Couldn't understand much - too much
> unfamiliar terminology.  But what it seems to do is reduce the
> number of points in the polyline, which would typically be the
> opposite of what I need.  Perhaps the method can be adapted for
> refining too?  I can't tell.  It is also rather important that the
> segments in the new polyline have more-or-less equal length.  Can
> this B-spline method do that?

You never said how your N and M are related.  In this
post it appears you want M > N.  My suggestion was to
give you a curve that "stays close to the original".  Once
you have a continuous representation that such a curve
provides, you can select points on the curve that are
uniformly spaced by arc length.  See
http://www.magic-software.com/Documentation/MovingAtConstantSpeed.pdf
This method works for any curve representation.  With the
clarification in this post, perhaps an easier approach to
obtaining a curve representation is to just fit your original
N points with a natural cubic spline or some other type of
curve.  Various possibilities are at my "curve" pages at the
web site.

--
Dave Eberly

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

### Refining a boundary

Quote:> Perhaps I should tell a little more about the problem.  Initially
> there is a polygon consisting of approximately equal segments.  The
> polygon expands in some fashion in a series of discrete steps.  The
> number of segments remains the same after each expansion.  After a
> number of such expansions the average length of a segment will
> increase, and the segments will become uneven.  My goal is to
> replace this expanded polygon (polyline, actually, since part of
> the polygon is constrained) with a new one, so that the size of all
> segments are close to their original size.

My suggestion in another follow-up still holds, but with a
minor modification.  Fit your N points with a curve, call
it X(t) for tmin <= t <= tmax.  You want to choose
parameter values t[i], 1 <= i <= M, so that the lengths
|X(t[i+1]) - X(t[i])| are all the same.  (The other post
suggested selecting the t[i] so that the curve points
X(t[i]) are uniformly spaced with respect to arc length.)

For the sake of illustration, suppose you have selected
an interpolating curve and you want M = 3 with t[1]
= tmin and t[3] = tmax.  You want to choose t[2] so
that |X(t[3]) - X(t[2])| = |X(t[2]) - X(t[1])|.  A method
for choosing t[2] is bisection applied to the function
F(t) = |X(t[3]) - X(t)|^2 - |X(t) - X(t[1])|^2.  This is
generally slow to converge, so a Newton's method
(and possibly a hybrid with bisection) can be used to
find the root t[2] of F.  I used the squared lengths in
case X(t) is a polynomial curve, in which case F(t) is
is a polynomial and you could apply polynomial root
finding methods.

A recursive application of this gives you a refinement,
but M = 2^p+1.  For arbitrary M, you could set up the
problem as a system of equations of the type shown
for F(t), one per t[i], then use a multidimensional Newton's
method or some other (polynomial) system solver.

Yet another variation is to just choose the t[i] uniformly,
then modify t[2] so that |X(t[3])-X(t[2])| = |X(t[2])-X(t[1])|.
Modify t[3] so that |X(t[4])-X(t[3])| = |X(t[3])-X(t[2])|,
and so on.  Repeat the modifications of all the t[i] until
some stopping criterion is met such as the maximum
difference max_i |t[i+1]-t[i]| is smaller than some prescribed
epsilon.

--
Dave Eberly

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

### Refining a boundary

> > 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

### Refining a boundary

> in message

>> Perhaps I should tell a little more about the problem.
>> Initially there is a polygon consisting of approximately
>> equal segments.  The polygon expands in some fashion in a
>> series of discrete steps.  The number of segments remains the
>> same after each expansion.  After a number of such expansions
>> the average length of a segment will increase, and the
>> segments will become uneven.  My goal is to replace this
>> expanded polygon (polyline, actually, since part of the
>> polygon is constrained) with a new one, so that the size of
>> all segments are close to their original size.

> My suggestion in another follow-up still holds, but with a
> minor modification.  Fit your N points with a curve, call
> it X(t) for tmin <= t <= tmax.  You want to choose
> parameter values t[i], 1 <= i <= M, so that the lengths
>|X(t[i+1]) - X(t[i])| are all the same.  (The other post
> suggested selecting the t[i] so that the curve points
> X(t[i]) are uniformly spaced with respect to arc length.)

> For the sake of illustration, suppose you have selected
> an interpolating curve and you want M = 3 with t[1]
> = tmin and t[3] = tmax.  You want to choose t[2] so
> that |X(t[3]) - X(t[2])| = |X(t[2]) - X(t[1])|.  A method
> for choosing t[2] is bisection applied to the function
> F(t) = |X(t[3]) - X(t)|^2 - |X(t) - X(t[1])|^2.  This is
> generally slow to converge, so a Newton's method
> (and possibly a hybrid with bisection) can be used to
> find the root t[2] of F.  I used the squared lengths in
> case X(t) is a polynomial curve, in which case F(t) is
> is a polynomial and you could apply polynomial root
> finding methods.

> A recursive application of this gives you a refinement,
> but M = 2^p+1.  For arbitrary M, you could set up the
> problem as a system of equations of the type shown
> for F(t), one per t[i], then use a multidimensional Newton's
> method or some other (polynomial) system solver.

> Yet another variation is to just choose the t[i] uniformly,
> then modify t[2] so that |X(t[3])-X(t[2])| =
> |X(t[2])-X(t[1])|. Modify t[3] so that |X(t[4])-X(t[3])| =
> |X(t[3])-X(t[2])|, and so on.  Repeat the modifications of all
> the t[i] until some stopping criterion is met such as the
> maximum difference max_i |t[i+1]-t[i]| is smaller than some
> prescribed epsilon.

Thanks a lot for your help.  I'll ponder the above and perhaps go
with either splines or the Fourier series interpolation suggested
by Gernot Hoffmann.

One more question/suggestion.  What if I have already figured out
the desired length of the segment.  Does this help my case?  One
approach might be to find an intersection of the interpolating
curve and a circle with the radius equal to the segment length.

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

### Refining a boundary

Quote:> One more question/suggestion.  What if I have already figured out
> the desired length of the segment.  Does this help my case?  One
> approach might be to find an intersection of the interpolating
> curve and a circle with the radius equal to the segment length.

What you propose can be made to work, but if you already know
the length, you can still use a bisection/Newton's approach.  Given
t[1] and a desired length L, find a t-value t[2] for which
F(t) = |X(t) - X(t[1])|^2 - L^2 is zero (squared quantities once
again to produce polynomial expressions if X(t) is a polynomial
curve).

--
Dave Eberly

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

Refine your design skills. Check us out.

--
A Graphic Designer's Guide to the Galaxy
"Now over 120 Graphic Design links in 18 categories"