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