001    package org.hackystat.projectbrowser.page.trajectory.dtw.step;
002    
003    import java.awt.Point;
004    
005    import org.hackystat.projectbrowser.page.trajectory.dtw.constraint.AbstractConstraintFunction;
006    
007    /**
008     * Implements symmetric cost function.
009     * 
010     * @author Pavel Senin.
011     * 
012     */
013    public class SymmetricStepFunction extends AbstractStepFunction {
014    
015      private String stepPattern;
016    
017      /** Step pattern p0 according to Sakoe-Chiba. */
018      public static final String STEP_PATTERN_P0 = "P0";
019    
020      /** Step pattern p05 according to Sakoe-Chiba. */
021      public static final String STEP_PATTERN_P05 = "P05";
022    
023      /** Step pattern p1 according to Sakoe-Chiba. */
024      public static final String STEP_PATTERN_P1 = "P1";
025    
026      /** Step pattern p2 according to Sakoe-Chiba. */
027      public static final String STEP_PATTERN_P2 = "P2";
028    
029      /**
030       * Constructor.
031       * 
032       * @param stepPattern specifies the step pattern.
033       */
034      public SymmetricStepFunction(String stepPattern) {
035        this.stepPattern = stepPattern;
036      }
037    
038      /**
039       * {@inheritDoc}
040       */
041      @Override
042      public Point doStep(Point position, double[][] distanceMatrix,
043          AbstractConstraintFunction constraints) {
044        return null;
045      }
046    
047      /**
048       * {@inheritDoc}
049       */
050      @Override
051      public double[][] getCostMatrix(double[][] distanceMatrix) {
052    
053        int rows = distanceMatrix.length;
054        int columns = distanceMatrix[0].length;
055    
056        double[][] costMatrix = new double[rows][columns];
057    
058        // [2.1] starting point
059        costMatrix[0][0] = distanceMatrix[0][0];
060    
061        // [2.2.1] first column
062        for (int i = 1; i < rows; i++) {
063          costMatrix[i][0] = distanceMatrix[i][0] + costMatrix[i - 1][0];
064        }
065    
066        // [2.2.2] first row
067        for (int j = 1; j < columns; j++) {
068          costMatrix[0][j] = distanceMatrix[0][j] + costMatrix[0][j - 1];
069        }
070    
071        if (STEP_PATTERN_P0.equalsIgnoreCase(this.stepPattern)) {
072          doCostP0(costMatrix, distanceMatrix);
073        }
074        else if (STEP_PATTERN_P05.equalsIgnoreCase(this.stepPattern)) {
075          doCostP05(costMatrix, distanceMatrix);
076        }
077        else if (STEP_PATTERN_P1.equalsIgnoreCase(this.stepPattern)) {
078          doCostP1(costMatrix, distanceMatrix);
079        }
080        else if (STEP_PATTERN_P2.equalsIgnoreCase(this.stepPattern)) {
081          doCostP2(costMatrix, distanceMatrix);
082        }
083    
084        return costMatrix;
085      }
086    
087      /**
088       * Fills the cost matrix using the step P2.
089       * 
090       * @param costMatrix the resulting cost matrix.
091       * @param distanceMatrix the initial distance matrix.
092       */
093      private void doCostP2(double[][] costMatrix, double[][] distanceMatrix) {
094        int rows = distanceMatrix.length;
095        int columns = distanceMatrix[0].length;
096        for (int j = 1; j < rows; j++) {
097          for (int i = 1; i < columns; i++) {
098            double[] options = { Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE };
099            if ((i - 1) > 0 && (j - 2) > 0) {
100              options[0] = costMatrix[i - 2][j - 3] + 2 * costMatrix[i - 1][j - 2] + 2
101                  * costMatrix[i][j - 1] + costMatrix[i][j];
102            }
103            if ((i - 1) > 0 && (j - 2) > 0) {
104              options[1] = costMatrix[i - 3][j - 2] + 2 * costMatrix[i - 2][j - 1] + 2
105                  * costMatrix[i - 1][j] + costMatrix[i][j];
106            }
107            options[2] = costMatrix[i - 1][j - 1] + 2 * costMatrix[i][j];
108            double minDistance = Math.min(options[0], Math.min(options[1], options[2]));
109            costMatrix[i][j] = distanceMatrix[i][j] + minDistance;
110          }
111        }
112      }
113    
114      /**
115       * Fills the cost matrix using the step P1.
116       * 
117       * @param costMatrix the resulting cost matrix.
118       * @param distanceMatrix the initial distance matrix.
119       */
120      private void doCostP1(double[][] costMatrix, double[][] distanceMatrix) {
121        int rows = distanceMatrix.length;
122        int columns = distanceMatrix[0].length;
123        for (int j = 1; j < rows; j++) {
124          for (int i = 1; i < columns; i++) {
125            double[] options = { Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE };
126            if ((j - 1) > 0) {
127              options[0] = costMatrix[i - 1][j - 2] + 2 * costMatrix[i][j - 1] + costMatrix[i][j];
128            }
129            if ((i - 1) > 0) {
130              options[1] = costMatrix[i - 2][j - 1] + 2 * costMatrix[i - 1][j] + costMatrix[i][j];
131            }
132            options[2] = costMatrix[i - 1][j - 1] + 2 * costMatrix[i][j];
133            double minDistance = Math.min(options[0], Math.min(options[1], options[2]));
134            costMatrix[i][j] = distanceMatrix[i][j] + minDistance;
135          }
136        }
137      }
138    
139      /**
140       * Fills the cost matrix using the step P05.
141       * 
142       * @param costMatrix the resulting cost matrix.
143       * @param distanceMatrix the initial distance matrix.
144       */
145      private void doCostP05(double[][] costMatrix, double[][] distanceMatrix) {
146        int rows = distanceMatrix.length;
147        int columns = distanceMatrix[0].length;
148        for (int j = 1; j < rows; j++) {
149          for (int i = 1; i < columns; i++) {
150            double[] options = { Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE,
151                Double.MAX_VALUE, Double.MAX_VALUE };
152            if ((j - 2) > 0) {
153              options[0] = costMatrix[i - 1][j - 3] + 2 * costMatrix[i][j - 2] + costMatrix[i][j - 1]
154                  + costMatrix[i][j];
155            }
156            if ((j - 1) > 0) {
157              options[1] = costMatrix[i - 1][j - 2] + 2 * costMatrix[i][j - 1] + costMatrix[i][j];
158            }
159            if ((i - 2) > 0) {
160              options[2] = costMatrix[i - 3][j - 1] + 2 * costMatrix[i - 2][j - 1]
161                  + costMatrix[i - 1][j] + costMatrix[i][j];
162            }
163            if ((i - 1) > 0) {
164              options[3] = costMatrix[i - 2][j - 1] + 2 * costMatrix[i - 1][j] + costMatrix[i][j];
165            }
166            options[4] = costMatrix[i - 1][j - 1] + 2 * costMatrix[i][j];
167            double minDistance = Math.min(options[0], Math.min(Math.min(options[1], options[2]), Math
168                .min(options[3], options[4])));
169            costMatrix[i][j] = distanceMatrix[i][j] + minDistance;
170          }
171        }
172      }
173    
174      /**
175       * Fills the cost matrix using the step P0.
176       * 
177       * @param costMatrix the resulting cost matrix.
178       * @param distanceMatrix the initial distance matrix.
179       */
180      private void doCostP0(double[][] costMatrix, double[][] distanceMatrix) {
181        int rows = distanceMatrix.length;
182        int columns = distanceMatrix[0].length;
183        for (int j = 1; j < rows; j++) {
184          for (int i = 1; i < columns; i++) {
185            double[] options = { costMatrix[i - 1][j - 1] + 2 * costMatrix[i][j],
186                costMatrix[i][j - 1] + costMatrix[i][j], costMatrix[i - 1][j] + costMatrix[i][j] };
187            double minDistance = Math.min(options[0], Math.min(options[1], options[2]));
188            costMatrix[i][j] = distanceMatrix[i][j] + minDistance;
189          }
190        }
191      }
192    }