001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 *  image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause 
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 
006 * Copyright (c) 2006-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 
007 * Visit http://imagingbook.com for additional details.
008 *******************************************************************************/
009
010package imagingbook.pub.fd;
011
012import java.awt.geom.Point2D;
013
014public class PolygonSampler {
015        
016        public PolygonSampler() {
017        }
018        
019        /**
020         * Samples the closed polygon path specified by V at M
021         * equi-distant positions. 
022         * @param V the vertices of the (closed) polygon.
023         * @param M the number of sample points.
024         * @return the sample points as an array of Point2D objects.
025         */
026        public Point2D[] samplePolygonUniformly(Point2D[] V, int M) {
027                int N = V.length;
028                double Delta = pathLength(V) / M;       // constant segment length in Q
029                // distribute N points along polygon path P
030                Point2D[] S = new Point2D[M];
031                S[0] = (Point2D) V[0].clone();  // q_0 = p_0 (duplicate p_0)
032                int i = 0;                      // lower index of segment (i,i+1) in P
033                int j = 1;                      // index of next point to be added to Q
034                double alpha = 0;       // lower boundary of current path segment in P
035                double beta = Delta;    // path position of next point to be added to Q
036                // for all M segments in P do:
037                while (i < N && j < M) {
038                        Point2D vA = V[i];
039                        Point2D vB = V[(i + 1) % N];
040                        double delta = vA.distance(vB);
041                        // handle segment (i,i+1) with path boundaries (a,a+d), knowing a < b
042                        while (beta <= alpha + delta && j < M) {
043                                // a < b <= a+d
044                                S[j] = interpolate(vA, vB, (beta - alpha) / delta);
045                                j = j + 1;
046                                beta = beta + Delta;
047                        }
048                        alpha = alpha + delta;
049                        i = i + 1;
050                }       
051                return S;
052        }
053        
054        /**
055         * This is for testing: allows to choose an arbitrary start point by
056         * setting 'startFrac' in [0,1].
057         * @param V the vertices of the (closed) polygon.
058         * @param M the number of sample points.
059         * @param startFrac the position of the first sample as a fraction of the 
060         * polggon's circumference in [0,1].
061         * @return the sample points as an array of Point2D objects.
062         */
063        public Point2D[] samplePolygonUniformly(Point2D[] V, int M, double startFrac) {
064                int startPos = (int) Math.round(V.length * startFrac) % V.length;
065                return samplePolygonUniformly(shiftLeft(V, startPos), M);
066        }
067        
068        private Point2D[] shiftLeft(Point2D[] V, int startPos) {
069                int polyLen = V.length;
070                Point2D[] P2 = new Point2D[polyLen]; 
071                for (int i = 0; i < P2.length; i++) {
072                        P2[i] = (Point2D) V[(i + startPos) % polyLen].clone();
073                }
074                return P2;
075        }
076        
077        
078        protected double pathLength(Point2D[] V) {
079                double L = 0;
080                final int N = V.length;
081                for (int i = 0; i < N; i++) {
082                        Point2D p0 = V[i];
083                        Point2D p1 = V[(i + 1) % N];
084                        L = L + p0.distance(p1);
085                }
086                return L;
087        }
088        
089        protected Point2D interpolate(Point2D p0, Point2D p1, double alpha) {
090                // alpha is in [0,1]
091                double x = p0.getX() + alpha * (p1.getX() - p0.getX());
092                double y = p0.getY() + alpha * (p1.getY() - p0.getY());
093                return new Point2D.Double(x, y);
094        }
095        
096}