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 }