2D Neighbourhood Representation
Some Java code for a 2D neighbourhood representation scheme. Definitions can be found in our 2012 GECCO paper. Permission to use and modify the code or image (SVG, PNG, PDF) is granted, but please include a reference to our paper or link to this page.
/** Accepts an index and returns an Int2D location in the VN neighbourhood*/
public Int2D VNify(int n) {
Int2D result = new Int2D(0,0);
if (n == 0) return result;
int k = (int) Math.ceil( -1.0/2.0 + Math.sqrt(1 + 2.0*(n))/2.0 );
int nprime = n - (int) (2.0*k*(k-1)) - 1;
int positivey = nprime - k;
int negativey = 3*k - nprime;
int firstx = nprime;
int secondx = 2*k - nprime;
int lastx = nprime - 4*k;
if (nprime <= k) result.setLocation(positivey, firstx);
else if (nprime <= 2*k) result.setLocation(positivey, secondx);
else if (nprime <= 3*k) result.setLocation(negativey, secondx);
else result.setLocation(negativey, lastx);
return result;
}
/** Accepts an (x,y) location in the VN neighbourhood and returns the corresponding index. */
public int unVNify(int x, int y) {
double nx = Math.abs(x);
double ny = Math.abs(y);
if (nx + ny == 0) return 0;
double quartWidth = Math.abs(x) + Math.abs(y);
double tempResult = 0.0;
if ( y >= 0) tempResult = x + quartWidth;
else tempResult = 2.0*quartWidth + (quartWidth - x);
tempResult += 1.0 + 4.0*( (quartWidth)*(quartWidth-1)/2.0 );
return (int) Math.round(tempResult);
}
/** Accepts an index and returns an Int2D location in the cross neighbourhood*/
public Int2D crucify(int i) {
Int2D result = new Int2D(0,0);
double sign = Math.pow(-1.0, Math.floor((i%4)/2.0));
double mag = Math.ceil(i/4.0);
int val = (int) Math.round(sign*mag);
if (i%4 ==0 || i%4 == 2) result.setLocation(0, val);
else result.setLocation(val, 0);
return result;
}
/** Accepts an (x,y) location in the cross neighbourhood and returns the corresponding index. (Note: garbage in, garbage out :) */
public int resurrect(int x, int y) {
int result = 0;
double tempResult = 4.0*Math.max(Math.abs(x),Math.abs(y));
if (x > 0) tempResult -= 3;
if (y < 0) tempResult -= 2;
if (x < 0) tempResult -= 1;
result = (int) Math.round(tempResult);
return result;
}
/** Accepts an index and returns an Int2D location in the Moore neighbourhood*/
public Int2D Moorify(int n) {
Int2D result = new Int2D(0,0);
if (n == 0) return result;
int k = 0;
for (int i=1; i<n+1; i++)
if ( (2*i+1)*(2*i+1) <= n ) k = i;
int S = (2*k+1)*(2*k+1);
int nprime = n - S;
int diam = 2*(k+1) + 1;
int m = k + 1;
if (nprime < diam) result.setLocation(-m + nprime, m);
else if (nprime < 2*diam-1) result.setLocation(m, m - (nprime - diam + 1));
else if (nprime < 3*diam-2) result.setLocation(m - (nprime - 2*diam + 2), -m);
else result.setLocation(-m, -m + (nprime -3*diam +3));
return result;
}
public class Int2D {
int x;
int y;
public int getX() { return x; }
public int getY() { return y; }
public void setX(int v) { x = v; }
public void setY(int v) { y = v; }
public void setLocation(int xT, int yT) { x = xT; y = yT; }
public Int2D() {;}
public Int2D(int x, int y) {
this.x = x; this.y = y;
}
public Int2D clone() {
return new Int2D(x,y);
}
public String toString() {
return "("+x+","+y+")";
}
public boolean equals(Int2D p) {
return (this.getX() == p.getX() && this.getY() == p.getY());
}
public double distance(Int2D that) {
return Math.sqrt((this.getX() - that.getX())*(this.getX() - that.getX()) + (this.getY() - that.getY())*(this.getY() - that.getY()));
}
}