NAME: fancompress PURPOSE: Decimates polylines in an aesthetically pleasing fashion. CALLING SEQUENCE: outidx = fancompress(inpts,err) INPUT: inpts: N x 2 dimension array, where inpts[*,0] are the x components of the polyline and inpts[*,1] are the y components of the polyline err: The amount of error allowed before including a point Keywords: vector: Will enable the vectorized fan compression algorithm. step: Controls the number of steps to perform per loop, during vectorized implementation. At the limit, where step = N, the vectorized version works like the iterative version. OUTPUT: An array of indexes into inpts. Indices will range from 0 to N-1. First and Last points are always included. NOTES: 1. Based almost entirely on the paper: Fowell, Richard A. and McNeil, David D. , “Faster Plots by Fan Data-Compression,” IEEE Computer Graphics & Applications, Vol. 9, No. 2,Mar. 1989, pp. 58-66. 2. One modification from published algorithm, handles NaNs by always including the point before a group of NaNs, 1 NaN and the point after the NaNs. This ensures that gaps will be drawn accurately. 3. Algorithm is fairly slow, because it requires 1 pass over all data points. Optimizing this algorithm by divide and conquer, vectorization, or dlm may be a worthwhile use of time in the future. 4. Vectorized version is essentially a divide and conquer version of the Fowell & McNeil algorithm. The idea being to split the array into sub-problems that can be addressed in parallel using IDL vector-ops. The fan-comparison operation at the core of the fan-compression algorithm takes 3-sequential points to work. So if step = 1, the algorithm will split the input array of length N in floor(N/3) segments; Making an independent decision on whether to keep the middle point of each segment, based upon the start and end points of each segment. If a point is removed, the 5-element fan vector at the start point is updated, and this will be applied in the subsequent test. 5. If step is higher an internal loop will perform the operation iteratively within-segments, but in parallel across segments. For example, If step is 3, N will be split into floor(N/5) segments(5-point segments). Operating on points 1-2-3 of the segment in the first iteration of the internal loop, points 1-3-4 or 2-3-4 on the second iteration and points 1-4-5,2-4-5,or 3-4-5 on the third iteration. Which sequence ends up being operated on depends on whether the point was accepted or rejected in the previous iteration. 6. Vectorized(step=1) version generally achieves a speed up of 1000% at decrease in compression by ~10%. For example, if the iterative version creates a 1 Mb of output in 1 sec, this will create 1.1 Mb of output in .1 sec. Higher values of step, tend to decrease compression rates until step becomes large, then compression approaches the iterative solution $LastChangedBy: pcruce $ $LastChangedDate: 2009-07-27 17:44:33 -0700 (Mon, 27 Jul 2009) $ $LastChangedRevision: 6496 $ $URL: svn+ssh://thmsvn@ambrosia.ssl.berkeley.edu/repos/spdsoft/trunk/general/misc/fancompress.pro $