1 // ******************************************************************************
2 //
3 // Title: Force Field X.
4 // Description: Force Field X - Software for Molecular Biophysics.
5 // Copyright: Copyright (c) Michael J. Schnieders 2001-2025.
6 //
7 // This file is part of Force Field X.
8 //
9 // Force Field X is free software; you can redistribute it and/or modify it
10 // under the terms of the GNU General Public License version 3 as published by
11 // the Free Software Foundation.
12 //
13 // Force Field X is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 // FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
16 // details.
17 //
18 // You should have received a copy of the GNU General Public License along with
19 // Force Field X; if not, write to the Free Software Foundation, Inc., 59 Temple
20 // Place, Suite 330, Boston, MA 02111-1307 USA
21 //
22 // Linking this library statically or dynamically with other modules is making a
23 // combined work based on this library. Thus, the terms and conditions of the
24 // GNU General Public License cover the whole combination.
25 //
26 // As a special exception, the copyright holders of this library give you
27 // permission to link this library with independent modules to produce an
28 // executable, regardless of the license terms of these independent modules, and
29 // to copy and distribute the resulting executable under terms of your choice,
30 // provided that you also meet, for each linked independent module, the terms
31 // and conditions of the license of that module. An independent module is a
32 // module which is not derived from or based on this library. If you modify this
33 // library, you may extend this exception to your version of the library, but
34 // you are not obligated to do so. If you do not wish to do so, delete this
35 // exception statement from your version.
36 //
37 // ******************************************************************************
38 package ffx.potential.utils;
39
40 import ffx.numerics.quickhull.QuickHull3D;
41 import ffx.potential.bonded.Atom;
42 import ffx.utilities.Constants;
43
44 import java.util.Arrays;
45 import java.util.logging.Logger;
46 import java.util.stream.IntStream;
47
48 import static ffx.numerics.math.DoubleMath.dist2;
49 import static java.lang.String.format;
50 import static java.lang.System.arraycopy;
51 import static org.apache.commons.math3.util.FastMath.max;
52 import static org.apache.commons.math3.util.FastMath.sqrt;
53
54 /**
55 * This ConvexHullOps class uses the QuickHull3D package by John E. Lloyd to construct and operate on
56 * 3D convex hulls: the minimal convex polyhedron that contains all points in a set of points. This
57 * is especially useful for max-dist operations, as the most distant points in a set are guaranteed
58 * to be part of the convex polyhedron.
59 *
60 * <p>The QuickHull3D package website is at quickhull3d.github.io/quickhull3d/ The algorithm it uses
61 * is described in Barber, Dobkin, and Huhdanpaa, "The Quickhull Algorithm for Convex Hulls" (ACM
62 * Transactions on Mathematical Software, Vol. 22, No. 4, December 1996), and the code is based on
63 * the C package qhull.
64 *
65 * @author Jacob M. Litman
66 * @author Michael J. Schnieders
67 * @since 1.0.0
68 */
69 public class ConvexHullOps {
70
71 private static final Logger logger = Logger.getLogger(ConvexHullOps.class.getName());
72
73 /**
74 * Constructs a convex hull from a set of atoms.
75 *
76 * @param atoms Atoms to build a convex hull for.
77 * @return A QuickHull3D implementation of convex hulls.
78 */
79 public static QuickHull3D constructHull(Atom[] atoms) {
80 int nAts = atoms.length;
81 if (nAts < 4) {
82 throw new IllegalArgumentException(
83 format(" 3D convex hull ill-defined for less than 4 points, found %d", nAts));
84 }
85 double[] xyz = new double[nAts * 3];
86 for (int i = 0; i < nAts; i++) {
87 Atom at = atoms[i];
88 int i3 = 3 * i;
89 xyz[i3] = at.getX();
90 xyz[i3 + 1] = at.getY();
91 xyz[i3 + 2] = at.getZ();
92 }
93 return new QuickHull3D(xyz);
94 }
95
96 /**
97 * UNTESTED: Identifies atoms forming the convex hull.
98 *
99 * @param quickHull3D A QuickHull3D.
100 * @param allAtoms Atoms used in building the QuickHull3D.
101 * @return Atoms forming the convex hull.
102 */
103 public static Atom[] identifyHullAtoms(QuickHull3D quickHull3D, Atom[] allAtoms) {
104 int[] indices = quickHull3D.getVertexPointIndices();
105 return Arrays.stream(indices).mapToObj((int i) -> allAtoms[i]).toArray(Atom[]::new);
106 }
107
108 /**
109 * Find the maximum pairwise distance between vertex points on a convex hull.
110 *
111 * @param quickHull3D A QuickHull3D object.
112 * @return Maximum vertex-vertex distance.
113 */
114 public static double maxDist(QuickHull3D quickHull3D) {
115 long time = -System.nanoTime();
116 int nVerts = quickHull3D.getNumVertices();
117 if (nVerts < 2) {
118 return 0;
119 }
120 double[] vertPoints = new double[3 * nVerts];
121 quickHull3D.getVertices(vertPoints);
122 double maxDist = IntStream.range(0, nVerts).parallel().mapToDouble((int i) -> {
123 double[] xyz = new double[3];
124 arraycopy(vertPoints, 3 * i, xyz, 0, 3);
125 double mij = 0;
126 for (int j = i + 1; j < nVerts; j++) {
127 double[] xyzJ = new double[3];
128 arraycopy(vertPoints, 3 * j, xyzJ, 0, 3);
129 double distIJ = dist2(xyz, xyzJ);
130 mij = max(mij, distIJ);
131 }
132 return mij;
133 }).max().getAsDouble();
134 maxDist = sqrt(maxDist);
135 time += System.nanoTime();
136 if (time > 1E9) {
137 logger.warning(format(" Required %12.6g sec to find max distance on a convex hull."
138 + " It may be time to further optimize this!", Constants.NS2SEC * time));
139 }
140 return maxDist;
141 }
142
143 /**
144 * Maximum pairwise distance between atoms in an array. Uses either the convex hull method (more
145 * than 10 atoms), or a brute-force loop (10 atoms or fewer).
146 *
147 * @param atoms Atoms to check max pairwise distance for.
148 * @return Max pairwise distance in Angstroms, or 0 (0 or 1 atoms given).
149 */
150 public static double maxDist(Atom[] atoms) {
151 int nAts = atoms.length;
152 if (nAts < 2) {
153 return 0;
154 } else if (nAts > 10) {
155 return maxDist(constructHull(atoms));
156 } else {
157 double maxDist = 0;
158 for (int i = 0; i < nAts - 1; i++) {
159 Atom atI = atoms[i];
160 double[] xyzI = new double[3];
161 xyzI = atI.getXYZ(xyzI);
162 for (int j = i + 1; j < nAts; j++) {
163 Atom atJ = atoms[j];
164 double[] xyzJ = new double[3];
165 xyzJ = atJ.getXYZ(xyzJ);
166 double dist = dist2(xyzI, xyzJ);
167 maxDist = max(dist, maxDist);
168 }
169 }
170 return sqrt(maxDist);
171 }
172 }
173 }