Source code

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}