Previous: fitpc4 Up: ../plot79_f.html Next: fitpl3
SUBROUTINE FITPL2 (XNEW,YNEW,NPNEW, X,Y,NP, DELTA)
C$ (Fit - Polyline 2-D)
C$ Given a set of points (X(I), Y(I), I = 1,NP) forming a 2-D
C$ curve, find a new set of points (XNEW(I), YNEW(I), I =
C$ 1,NPNEW), which is smaller if possible by eliminating
C$ consecutive colinear, or almost colinear, segments.
C$
C$ The output arguments are:
C$
C$ XNEW(*)........New X values returned.
C$ YNEW(*)........New Y values returned. If the old values
C$ need not be preserved, XNEW(*) and YNEW(*)
C$ may be the same arrays as X(*) and Y(*)
C$ respectively.
C$ NPNEW..........Number of new (X,Y) pairs returned. Space
C$ must be available in XNEW(*) and YNEW(*) to
C$ store at most NP items, since NPNEW .LE. NP
C$ on return.
C$
C$ The input arguments are:
C$
C$ X(*)...........Old X values.
C$ Y(*)...........Old Y values.
C$ NP.............Number of old (X,Y) values.
C$ DELTA..........Maximum deviation between the data points
C$ and the required vector approximation,
C$ measured relative to the line segment
C$ lengths in order so that it is independent
C$ of the scale of the input data.
C$
C$ It is assumed that X and Y are approximately equally
C$ scaled, so that distance computations can be done without
C$ undue accuracy loss. Internal scaling is done according to
C$ the curve arclength, so that the range of X and Y can
C$ approach the underflow and overflow limits of the host
C$ machine without causing harmful underflow or overflow.
C$
C$ This routine may prove useful in determining a reduced set
C$ of points which can satisfactorily represent a much larger
C$ set, but for which plotting time is excessive. This will
C$ generally be the case for points entered from a digitizer.
C$
C$ The output set of points is always a subset of the input
C$ point set, and contains the same first and last points.
C$ Thus, if the input points are integral values, the output
C$ points will be too.
C$
C$ In the case of polygons, the last input point point should
C$ be identical to the first one. If this point lies only
C$ slightly off the line segment connecting its adjacent
C$ neighbors, it could possibly be eliminated. Thus, for
C$ polygons, one should call this routine twice using
C$ different start points, then select the smaller output set.
C$
C$ The algorithm is the split-and-merge one given by
C$
C$ Theo Pavlidis, "Algorithms for Graphics and Image
C$ Processing", Computer Science Press (1982), pp. 281-292.
C$
C$ The criterion for accepting a point near a line segment as
C$ colinear is based on a combination of the user-provided
C$ DELTA and the number of sign changes in the intermediate
C$ point distances from the line segment. If the sign changes
C$ are frequent, the intermediate points are distributed on
C$ both sides of the approximating line, and the line is a
C$ better choice than it would be if the points were
C$ predominantly on one side.
C$ (28-DEC-83)