001/* 002 * BioJava development code 003 * 004 * This code may be freely distributed and modified under the 005 * terms of the GNU Lesser General Public Licence. This should 006 * be distributed with the code. If you do not have a copy, 007 * see: 008 * 009 * http://www.gnu.org/copyleft/lesser.html 010 * 011 * Copyright for this code is held jointly by the individual 012 * authors. These should be listed in @author doc comments. 013 * 014 * For more information on the BioJava project and its aims, 015 * or to join the biojava-l mailing list, visit the home page 016 * at: 017 * 018 * http://www.biojava.org/ 019 * 020 */ 021package org.biojava.nbio.structure.contact; 022 023 024import org.biojava.nbio.structure.Atom; 025 026 027/** 028 * A grid to be used for calculating atom contacts through geometric hashing algorithm. 029 * 030 * The grid is composed of cells of size of the cutoff so that the distances that need to be calculated 031 * are reduced to those within each cell and to the neighbouring cells. 032 * 033 * @author duarte_j 034 * 035 */ 036public class Grid { 037 038 /** 039 * The scale: we use units of hundredths of Angstroms (thus cutoffs can be specified with a maximum precision of 0.01A) 040 */ 041 private static final int SCALE=100; 042 043 private GridCell[][][] cells; 044 045 private double cutoff; 046 private int cellSize; 047 048 private Atom[] iAtoms; 049 private Atom[] jAtoms; 050 051 // the bounds in int grid coordinates 052 private int[] bounds; 053 054 // the i and j bounding boxes in original double coordinates 055 private BoundingBox ibounds; 056 private BoundingBox jbounds; 057 058 private boolean noOverlap; // if the 2 sets of atoms are found not to overlap then this is set to true 059 060 /** 061 * Creates a <code>Grid</code>, the cutoff is in Angstroms and can 062 * be specified to a precision of 0.01A 063 * @param cutoff 064 */ 065 public Grid(double cutoff) { 066 this.cutoff = cutoff; 067 this.cellSize = (int) Math.floor(cutoff*SCALE); 068 this.noOverlap = false; 069 } 070 071 private int getFloor(double number) { 072 return (cellSize*((int)Math.floor(number*SCALE/cellSize))); 073 } 074 075 private int xintgrid2xgridindex(int xgridDim) { 076 return (xgridDim-bounds[0])/cellSize; 077 } 078 079 private int yintgrid2ygridindex(int ygridDim) { 080 return (ygridDim-bounds[1])/cellSize; 081 } 082 083 private int zintgrid2zgridindex(int zgridDim) { 084 return (zgridDim-bounds[2])/cellSize; 085 } 086 087 /** 088 * Adds the i and j atoms and fills the grid. Their bounds will be computed. 089 * @param iAtoms 090 * @param jAtoms 091 */ 092 public void addAtoms(Atom[] iAtoms, Atom[] jAtoms) { 093 addAtoms(iAtoms, null, jAtoms, null); 094 } 095 096 /** 097 * Adds the i and j atoms and fills the grid, passing their bounds (array of size 6 with x,y,z minima and x,y,z maxima) 098 * This way the bounds don't need to be recomputed. 099 * @param iAtoms 100 * @param icoordbounds 101 * @param jAtoms 102 * @param jcoordbounds 103 */ 104 public void addAtoms(Atom[] iAtoms, BoundingBox icoordbounds, Atom[] jAtoms, BoundingBox jcoordbounds) { 105 this.iAtoms = iAtoms; 106 107 if (icoordbounds!=null) { 108 this.ibounds = icoordbounds; 109 } else { 110 this.ibounds = new BoundingBox(iAtoms); 111 } 112 113 this.jAtoms = jAtoms; 114 115 if (jAtoms==iAtoms) { 116 this.jbounds=ibounds; 117 } else { 118 if (jcoordbounds!=null) { 119 this.jbounds = jcoordbounds; 120 } else { 121 this.jbounds = new BoundingBox(jAtoms); 122 123 } 124 } 125 126 fillGrid(); 127 } 128 129 /** 130 * Adds a set of atoms, subsequent call to getContacts will produce the interatomic contacts. 131 * The bounding box of the atoms will be computed based on input array 132 * @param atoms 133 */ 134 public void addAtoms(Atom[] atoms) { 135 addAtoms(atoms, (BoundingBox) null); 136 } 137 138 /** 139 * Adds a set of atoms, subsequent call to getContacts will produce the interatomic contacts. 140 * The bounds calculated elsewhere can be passed, or if null they are computed. 141 * @param atoms 142 * @param bounds 143 */ 144 public void addAtoms(Atom[] atoms, BoundingBox bounds) { 145 this.iAtoms = atoms; 146 147 if (bounds!=null) { 148 this.ibounds = bounds; 149 } else { 150 this.ibounds = new BoundingBox(iAtoms); 151 } 152 153 this.jAtoms = null; 154 this.jbounds = null; 155 156 fillGrid(); 157 } 158 159 /** 160 * Creates the grid based on the boundaries defined by all atoms given (iAtoms and jAtoms) 161 * and places the atoms in their corresponding grid cells. 162 * Checks also if the i and j grid overlap, i.e. the enclosing bounds of 163 * the 2 grids (i and j) are no more than one cell size apart. If they don't 164 * overlap then they are too far apart so there's nothing to calculate, we set 165 * the noOverlap flag and then {@link #getContacts()} will do no calculation at all. 166 */ 167 private void fillGrid() { 168 169 if (jbounds!=null && !ibounds.overlaps(jbounds, cutoff)) { 170 //System.out.print("-"); 171 noOverlap = true; 172 return; 173 } 174 175 findFullGridIntBounds(); 176 177 cells = new GridCell[1+(bounds[3]-bounds[0])/cellSize] 178 [1+(bounds[4]-bounds[1])/cellSize] 179 [1+(bounds[5]-bounds[2])/cellSize]; 180 181 int i = 0; 182 for (Atom atom:iAtoms) { 183 184 int xind = xintgrid2xgridindex(getFloor(atom.getX())); 185 int yind = yintgrid2ygridindex(getFloor(atom.getY())); 186 int zind = zintgrid2zgridindex(getFloor(atom.getZ())); 187 if (cells[xind][yind][zind]==null) { 188 cells[xind][yind][zind] = new GridCell(); 189 } 190 cells[xind][yind][zind].addIindex(i); 191 i++; 192 } 193 194 if (jAtoms==null) return; 195 196 int j = 0; 197 for (Atom atom:jAtoms) { 198 199 int xind = xintgrid2xgridindex(getFloor(atom.getX())); 200 int yind = yintgrid2ygridindex(getFloor(atom.getY())); 201 int zind = zintgrid2zgridindex(getFloor(atom.getZ())); 202 if (cells[xind][yind][zind]==null) { 203 cells[xind][yind][zind] = new GridCell(); 204 } 205 cells[xind][yind][zind].addJindex(j); 206 j++; 207 } 208 209 } 210 211 /** 212 * Calculates an int array of size 6 into member variable bounds: 213 * - elements 0,1,2: minimum x,y,z of the iAtoms and jAtoms 214 * - elements 3,4,5: maximum x,y,z of the iAtoms and jAtoms 215 */ 216 private void findFullGridIntBounds() { 217 int[] iIntBounds = getIntBounds(ibounds); 218 219 bounds = new int[6]; 220 if (jbounds==null) { 221 bounds = iIntBounds; 222 } else { 223 int[] jIntBounds = getIntBounds(jbounds); 224 bounds[0] = Math.min(iIntBounds[0],jIntBounds[0]); 225 bounds[1] = Math.min(iIntBounds[1],jIntBounds[1]); 226 bounds[2] = Math.min(iIntBounds[2],jIntBounds[2]); 227 bounds[3] = Math.max(iIntBounds[3],jIntBounds[3]); 228 bounds[4] = Math.max(iIntBounds[4],jIntBounds[4]); 229 bounds[5] = Math.max(iIntBounds[5],jIntBounds[5]); 230 } 231 } 232 233 /** 234 * Returns an int array of size 6 : 235 * - elements 0,1,2: minimum x,y,z (in grid int coordinates) of the given atoms 236 * - elements 3,4,5: maximum x,y,z (in grid int coordinates) of the given atoms 237 * @return 238 */ 239 private int[] getIntBounds(BoundingBox coordbounds) { 240 int[] bs = new int[6]; 241 bs[0] = getFloor(coordbounds.xmin); 242 bs[1] = getFloor(coordbounds.ymin); 243 bs[2] = getFloor(coordbounds.zmin); 244 bs[3] = getFloor(coordbounds.xmax); 245 bs[4] = getFloor(coordbounds.ymax); 246 bs[5] = getFloor(coordbounds.zmax); 247 return bs; 248 } 249 250 /** 251 * Returns all contacts, i.e. all atoms that are within the cutoff distance. 252 * If both iAtoms and jAtoms are defined then contacts are between iAtoms and jAtoms, 253 * if jAtoms is null, then contacts are within the iAtoms. 254 * @return 255 */ 256 public AtomContactSet getContacts() { 257 258 AtomContactSet contacts = new AtomContactSet(cutoff); 259 260 // if the 2 sets of atoms are not overlapping they are too far away and no need to calculate anything 261 // this won't apply if there's only one set of atoms (iAtoms), where we would want all-to-all contacts 262 if (noOverlap) return contacts; 263 264 265 for (int xind=0;xind<cells.length;xind++) { 266 for (int yind=0;yind<cells[xind].length;yind++) { 267 for (int zind=0;zind<cells[xind][yind].length;zind++) { 268 // distances of points within this cell 269 GridCell thisCell = cells[xind][yind][zind]; 270 if (thisCell==null) continue; 271 272 contacts.addAll(thisCell.getContactsWithinCell(iAtoms, jAtoms, cutoff)); 273 274 // distances of points from this box to all neighbouring boxes: 26 iterations (26 neighbouring boxes) 275 for (int x=xind-1;x<=xind+1;x++) { 276 for (int y=yind-1;y<=yind+1;y++) { 277 for (int z=zind-1;z<=zind+1;z++) { 278 if (x==xind && y==yind && z==zind) continue; 279 280 if (x>=0 && x<cells.length && y>=0 && y<cells[x].length && z>=0 && z<cells[x][y].length) { 281 if (cells[x][y][z] == null) continue; 282 283 contacts.addAll(thisCell.getContactsToOtherCell(cells[x][y][z], iAtoms, jAtoms, cutoff)); 284 } 285 } 286 } 287 } 288 } 289 } 290 } 291 292 return contacts; 293 } 294 295 public double getCutoff() { 296 return cutoff; 297 } 298 299 /** 300 * Tells whether (after having added atoms to grid) the i and j grids are not overlapping. 301 * Overlap is defined as enclosing bounds of the 2 grids being no more than one cell size apart. 302 * @return true if the 2 grids don't overlap, false if they do 303 */ 304 public boolean isNoOverlap() { 305 return noOverlap; 306 } 307 308}