import java.util.List; final int X=0; final int Y=1; final int Z=2; Simplex simplex; class Simplex { Function2D func; float[][] p = new float[3][3]; List points = new ArrayList(); float pmin; Simplex(Function2D func) { this.func = func; set(0,0,0,1,1,0); } void set(float x1, float y1, float x2, float y2, float x3, float y3) { points.clear(); p[0][X] = x1; p[0][Y] = y1; p[1][X] = x2; p[1][Y] = y2; p[2][X] = x3; p[2][Y] = y3; p[0][Z] = func.eval(p[0][X],p[0][Y]); p[1][Z] = func.eval(p[1][X],p[1][Y]); p[2][Z] = func.eval(p[2][X],p[2][Y]); sort(); pmin = p[0][Z]; } float min() { return p[0][Z]; } void update(float[] ps) { p[0] = ps; sort(); } void sort() { if(p[0][Z] < p[1][Z]) swap(0,1); if(p[0][Z] < p[2][Z]) swap(0,2); if(p[1][Z] < p[2][Z]) swap(1,2); points.add(p[0]); points.add(p[1]); points.add(p[2]); } void swap(int i, int j) { float[] temp; temp = p[i]; p[i] = p[j]; p[j] = temp; } boolean step() { float[] m,n; println(this.min() + " " + abs(p[2][Z] - p[0][Z])); n = reflect(); if (n[Z] < p[2][Z]) { m = reflectgrow(); if (m[Z] < n[Z]) update(m); else update(n); } else { m = reflectshrink(); if (m[Z] < p[1][Z]) { update(m); } else { n = noreflectshrink(); if (n[Z] < p[1][Z]) update(n); else shrink(); } } return false; } float[] pivot() { float[] mean = new float[2]; mean[X] = (p[1][X] + p[2][X]) / 2; mean[Y] = (p[1][Y] + p[2][Y]) / 2; return mean; } float[] reflect() { float[] res = new float[3]; float[] pv = pivot(); res[X] = 2*pv[X] - p[0][X]; res[Y] = 2*pv[Y] - p[0][Y]; res[Z] = func.eval(res[X],res[Y]); return res; } float[] reflectgrow() { float[] res = new float[3]; float[] pv = pivot(); res[X] = 3*pv[X] - 2*p[0][X]; res[Y] = 3*pv[Y] - 2*p[0][Y]; res[Z] = func.eval(res[X],res[Y]); return res; } float[] reflectshrink() { float[] res = new float[3]; float[] pv = pivot(); res[X] = 1.5*pv[X] - 0.5*p[0][X]; res[Y] = 1.5*pv[Y] - 0.5*p[0][Y]; res[Z] = func.eval(res[X],res[Y]); return res; } float[] noreflectshrink() { float[] res = new float[3]; float[] pv = pivot(); res[X] = (pv[X] + p[0][X])*0.5; res[Y] = (pv[Y] + p[0][Y])*0.5; res[Z] = func.eval(res[X],res[Y]); return res; } void shrink() { p[0][X] = (p[0][X] + p[2][X]) * 0.5; p[0][Y] = (p[0][Y] + p[2][Y]) * 0.5; p[1][X] = (p[1][X] + p[2][X]) * 0.5; p[1][Y] = (p[1][Y] + p[2][Y]) * 0.5; sort(); } void draw() { drawPoints(); drawProjection(); } void drawPoints() { stroke(0.6,0.6,0.6); beginShape(TRIANGLE_STRIP); Iterator ite = points.iterator(); while(ite.hasNext()) { float[] pnt = (float[])ite.next(); vertex(pnt[X],pnt[Y],pnt[Z]); } endShape(); stroke(0,0,0); line(p[0][X],p[0][Y],p[0][Z],p[1][X],p[1][Y],p[1][Z]); line(p[2][X],p[2][Y],p[2][Z],p[1][X],p[1][Y],p[1][Z]); line(p[0][X],p[0][Y],p[0][Z],p[2][X],p[2][Y],p[2][Z]); } void drawProjection() { stroke(0.4,0.4,0.4); beginShape(TRIANGLE_STRIP); Iterator ite = points.iterator(); while(ite.hasNext()) { float[] pnt = (float[])ite.next(); vertex(pnt[X],pnt[Y]); } endShape(); } } void setupSimplex() { simplex = new Simplex(function); simplex.set(-10,-10,-10,-9,-9,-10); } void updateSimplex() { simplex.step(); } void drawSimplex() { simplex.draw(); }