Source code for MaxStepApproximation.java

/*
 * Copyright (C) 2012 W. Patrick Hooper <wphooper@gmail.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package path;

import geometry.LineSegment;
import java.util.NoSuchElementException;
import java.util.Stack;
import number.Complex;

/**
 * Construct a new polygonal path from a path, which consists of the most 
 * shallow segments which whose length is bounded from above by a constant,
 * the maximum step.
 *
 * @author W. Patrick Hooper
 */
public class MaxStepApproximation implements PolygonalPath {

    final Path p; // original path
    final double max_step;  // depth 

    /**
     * Construct a version of the path whose iterator moves over the most 
     * shallow segments of length less than max_step_length.
     * 
     */
    public MaxStepApproximation(Path path, double max_step_length) {
        p = path;
        max_step = max_step_length;
    }

    /**
     * This is a private class which implements an iterator over the sub-paths
     * of depth d.
     */
    private class ApproximationIterator implements EdgeIterator {

        Stack<PathIterator> iterator_stack; // A sequence of iterators at increasing depths

        /**
         * Construct an initial iterator starting at the first sub-path of depth
         * d.
         */
        public ApproximationIterator() {
            iterator_stack = new Stack<PathIterator>();
            iterator_stack.push(p.iterator());
        }

        /** This function removes all iterators who have no more sub-paths from the stack. */
        private void removeEnds() {
            while ((!iterator_stack.empty()) && (!iterator_stack.peek().hasNext())) {
                iterator_stack.pop();
            }
        }

        @Override
        public boolean hasNext() {
            removeEnds();
            return !iterator_stack.empty();
        }

        @Override
        public LineSegment next() {
            removeEnds();

            if (iterator_stack.empty()) {
                // Throw an error. This would have been avoided if the user had called hasNext() first.
                throw new NoSuchElementException("The DepthApproximation iterator has no more elements.");
            }

            // This will store the deepest path in the stack:
            Path deepest_path = iterator_stack.peek().next();
            // Its depth is given by the stack size minus 1.

            while (PathUtil.distanceFromStartToEnd(deepest_path) > max_step) {
                
                // temp.iterator() returns an iterator over the next level of subpath
                PathIterator next_depth_iterator = deepest_path.iterator();

                if (!next_depth_iterator.hasNext()) {
                    // it should have at least one edge!
                    throw new NoSuchElementException("DepthApproximation was given a path with no edges.");
                }

                // this path is one deeper:
                deepest_path = next_depth_iterator.next();

                iterator_stack.add(next_depth_iterator);
            }
            
            // now the path is guaranteed to be at depth d, so we return it.
            return new LineSegment(deepest_path.startingPoint(), deepest_path.endingPoint());
        }
    }
    
    /** Iterate over the sub-paths making up the path. */
    @Override
    public EdgeIterator iterator() {
        return new ApproximationIterator();
    }

    /** Return the ending point of the path. */
    @Override
    public Complex endingPoint() {
        return p.endingPoint();
    }

    /** Return the starting point of the path. */
    @Override
    public Complex startingPoint() {
        return p.startingPoint();
    }

    /** Convert the path to a string. */
    @Override
    public String toString() {
        return PathUtil.toString(this);
    }
}

Last modified on August 17, 2018.