zbMATH — the first resource for mathematics

A ‘taut-string algorithm’ for straightening a piecewise linear path in two dimensions. (English) Zbl 0908.65007
The algorithm developed in this paper can be described as follows: Let there be given a set of points $$\{u_1,\dots, u_n\}$$ and the piecewise linear path defined by drawing straight lines between the points $$u_j$$. Moreover, choose a positive number $$\delta$$ such that the length of each straight-line segment is at least $$3\delta$$.
Then the straightening method described in the paper is as follows: For $$j= 2,\dots,n- 1$$, each $$u_j$$ is surrounded by a circle of radius $$\delta$$. Then a piece of string that starts in $$u_1$$ and ends in $$u_n$$ is threaded through all these circles, and the new path is constructed by “pulling” this string tight.
An iterative algorithm is developed that generates the new path to prescribed accuracy. Its convergence is proved, and it is illustrated by some numerical examples.
Reviewer: G.Walz (Mannheim)

MSC:
 65D17 Computer-aided design (modeling of curves and surfaces)
Full Text: