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-2023 Wilhelm Burger, Mark J. Burge. All rights reserved. 007 * Visit https://imagingbook.com for additional details. 008 ******************************************************************************/ 009 010package imagingbook.common.geometry.fd; 011 012import imagingbook.common.geometry.basic.Pnt2d; 013import imagingbook.common.geometry.basic.Pnt2d.PntDouble; 014 015/** 016 * <p> 017 * This class is used to re-sample 2D polygons by interpolation. See Sec. 2.1.1 (Alg. 26.1) if [1] for details. Note 018 * that this class has no public constructor, use {@link #getInstance()} instead. 019 * </p> 020 * <p> 021 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction Using Java</em>, 2rd ed, 022 * Springer (2016). 023 * </p> 024 * 025 * @author WB 026 * @version 2022/10/26 027 */ 028public class PolygonSampler { // TODO: add unit tests 029 030 private static final PolygonSampler instance = new PolygonSampler(); 031 032 private PolygonSampler() {} 033 034 public static PolygonSampler getInstance() { 035 return instance; 036 } 037 038 /** 039 * Samples the closed polygon path specified by V at M equidistant positions. 040 * 041 * @param V the vertices of the (closed) polygon. 042 * @param M the number of sample points. 043 * @return the sample points as an array of Point objects. 044 */ 045 public Pnt2d[] samplePolygon(Pnt2d[] V, int M) { 046 int N = V.length; 047 double Delta = pathLength(V) / M; // constant segment length in Q 048 // distribute N points along polygon path P 049 Pnt2d[] S = new Pnt2d[M]; 050// S[0] = (Point) V[0].clone(); // q_0 = p_0 (duplicate p_0) 051 S[0] = PntDouble.from(V[0]); // q_0 = p_0 (duplicate p_0) 052 int i = 0; // lower index of segment (i,i+1) in P 053 int j = 1; // index of next point to be added to Q 054 double alpha = 0; // lower boundary of current path segment in P 055 double beta = Delta; // path position of next point to be added to Q 056 // for all M segments in P do: 057 while (i < N && j < M) { 058 Pnt2d vA = V[i]; 059 Pnt2d vB = V[(i + 1) % N]; 060 double delta = vA.distance(vB); 061 // handle segment (i,i+1) with path boundaries (a,a+d), knowing a < b 062 while (beta <= alpha + delta && j < M) { 063 // a < b <= a+d 064 S[j] = interpolate(vA, vB, (beta - alpha) / delta); 065 j = j + 1; 066 beta = beta + Delta; 067 } 068 alpha = alpha + delta; 069 i = i + 1; 070 } 071 return S; 072 } 073 074 /** 075 * For testing only: allows to choose an arbitrary start point by setting 'startFrac' in [0,1]. 076 * 077 * @param V the vertices of the (closed) polygon. 078 * @param M the number of sample points. 079 * @param startFrac the position of the first sample as a fraction of the polggon's circumference in [0,1]. 080 * @return the sample points as an array of Point objects. 081 */ 082 public Pnt2d[] samplePolygon(Pnt2d[] V, int M, double startFrac) { 083 int startPos = (int) Math.round(V.length * startFrac) % V.length; 084 return samplePolygon(shiftLeft(V, startPos), M); 085 } 086 087 private Pnt2d[] shiftLeft(Pnt2d[] V, int startPos) { 088 int polyLen = V.length; 089 Pnt2d[] P2 = new Pnt2d[polyLen]; 090 for (int i = 0; i < P2.length; i++) { 091// P2[i] = (Point) V[(i + startPos) % polyLen].clone(); 092 P2[i] = PntDouble.from(V[(i + startPos) % polyLen]); 093 } 094 return P2; 095 } 096 097 098 private double pathLength(Pnt2d[] V) { 099 double L = 0; 100 final int N = V.length; 101 for (int i = 0; i < N; i++) { 102 Pnt2d p0 = V[i]; 103 Pnt2d p1 = V[(i + 1) % N]; 104 L = L + p0.distance(p1); 105 } 106 return L; 107 } 108 109 private Pnt2d interpolate(Pnt2d p0, Pnt2d p1, double alpha) { 110 // alpha is in [0,1] 111 double x = p0.getX() + alpha * (p1.getX() - p0.getX()); 112 double y = p0.getY() + alpha * (p1.getY() - p0.getY()); 113 return Pnt2d.PntDouble.from(x, y); 114 } 115 116}