给定 3d 空间中的一组点，找到彼此距离内的所有点集

Question

我有一组 3d 点S。我需要找到S中所有点集的集合X，这些点在曼哈顿距离d之内。

即对于X中的每个集合Y，在 3d 空间中至少存在一个点在Y中所有点的距离d内

集合S的长度永远不会 >20，但我将不得不对以每秒约 10 个新集合的速度生成的集合流运行此分析，因此无论我使用什么解决方案，都必须相当有效。

一个帮助可视化问题的示例，给出以下内容：

输出将是 ((A,B), (B,C,E), (B,D,E))

我们只关心最大可能的集合，因此集合 (B,C)、(B,D)、(B,E)、(C,E) 和 (D,E) 在给定参数内不在给定它们是X中其他集合的子集的输出

这也是我在 java 中做的，但是任何关于算法或伪代码的指针都将不胜感激，在此先感谢。

Answer 1

伪代码的解决方案是：calculate_intersections(areas):&nbsp; &nbsp; intersections = calculate every two intersecting areas&nbsp; &nbsp; combinations = combine_intersections(intersections)&nbsp; &nbsp; reduced = remove all sets in combinations that are included in bigger setscombine_intersections(intersections):&nbsp; &nbsp; do:&nbsp; &nbsp; &nbsp; &nbsp; combinations = new HashSet&nbsp; &nbsp; &nbsp; &nbsp; for s1 in intersections:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for s2 in intersections:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; diff_1_2 = s1 \ s2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; diff_2_1 = s2 \ s1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if diff_1_2.len == 1 && diff_2_1.len == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; union = diff_1_2 + diff_2_1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if union in intersections:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; union2 = s1 + s2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if !union2 in intersections:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combinations.add(union)&nbsp; &nbsp; while (combinations not empty)Java 中的实现可能如下所示：import java.util.Arrays;import java.util.HashSet;import java.util.Iterator;import java.util.Set;import org.apache.commons.collections4.SetUtils;public class IntersectionSetCalculation {&nbsp; &nbsp; private static class ManhattanDistanceArea {&nbsp; &nbsp; &nbsp; &nbsp; private String id;&nbsp; &nbsp; &nbsp; &nbsp; private Vector3D center;&nbsp; &nbsp; &nbsp; &nbsp; private double distance;&nbsp; &nbsp; &nbsp; &nbsp; public ManhattanDistanceArea(Vector3D center, double distance, String id) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.center = center;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.distance = distance;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.id = id;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return id;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public int hashCode() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; final int prime = 31;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int result = 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = prime * result + ((center == null) ? 0 : center.hashCode());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long temp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp = Double.doubleToLongBits(distance);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = prime * result + (int) (temp ^ (temp >>> 32));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = prime * result + ((id == null) ? 0 : id.hashCode());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public boolean equals(Object obj) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this == obj)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (obj == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (getClass() != obj.getClass())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea other = (ManhattanDistanceArea) obj;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (center == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (other.center != null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (!center.equals(other.center))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (Double.doubleToLongBits(distance) != Double.doubleToLongBits(other.distance))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (id == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (other.id != null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (!id.equals(other.id))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public boolean intersects(ManhattanDistanceArea other) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double maxDist = distance + other.distance;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return center.distance(other.center, 1) < maxDist;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Calculate the intersection of all areas (maximum of 2 areas in an intersection)&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public static Set<Set<ManhattanDistanceArea>> getIntersectingAreas(Set<ManhattanDistanceArea> areas) {&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> intersections = new HashSet<Set<ManhattanDistanceArea>>();&nbsp; &nbsp; &nbsp; &nbsp; for (ManhattanDistanceArea area : areas) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (ManhattanDistanceArea area2 : areas) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!area.equals(area2) && area.intersects(area2)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; HashSet<ManhattanDistanceArea> intersection = new HashSet<ManhattanDistanceArea>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; intersection.add(area);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; intersection.add(area2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; intersections.add(intersection);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> combined = combineIntersections(intersections);&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> reduced = reduceIntersections(combined);&nbsp; &nbsp; &nbsp; &nbsp; return reduced;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Combine the small intersections (with a maximum of 2 areas in an intersection) to bigger intersections&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public static Set<Set<ManhattanDistanceArea>> combineIntersections(Set<Set<ManhattanDistanceArea>> inters) {&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> intersections = new HashSet<Set<ManhattanDistanceArea>>(inters);&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> combinations;&nbsp; &nbsp; &nbsp; &nbsp; do {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combinations = new HashSet<Set<ManhattanDistanceArea>>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Set<ManhattanDistanceArea> intersecting1 : intersections) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Set<ManhattanDistanceArea> intersecting2 : intersections) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> diff_1_2 = SetUtils.difference(intersecting1, intersecting2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> diff_2_1 = SetUtils.difference(intersecting2, intersecting1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (diff_1_2.size() == 1 && diff_2_1.size() == 1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> union_1_2 = SetUtils.union(diff_1_2, diff_2_1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (intersections.contains(union_1_2)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> union = SetUtils.union(intersecting1, intersecting2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!intersections.contains(union)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combinations.add(union);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; intersections.addAll(combinations);&nbsp; &nbsp; &nbsp; &nbsp; } while (!combinations.isEmpty());&nbsp; &nbsp; &nbsp; &nbsp; return intersections;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Remove the small intersections that are completely covered by bigger intersections&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public static Set<Set<ManhattanDistanceArea>> reduceIntersections(Set<Set<ManhattanDistanceArea>> inters) {&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> intersections = new HashSet<Set<ManhattanDistanceArea>>(inters);&nbsp; &nbsp; &nbsp; &nbsp; Iterator<Set<ManhattanDistanceArea>> iter = intersections.iterator();&nbsp; &nbsp; &nbsp; &nbsp; while (iter.hasNext()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> intersection = iter.next();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Set<ManhattanDistanceArea> intersection2 : inters) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (intersection2.size() > intersection.size() && intersection2.containsAll(intersection)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; iter.remove();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return intersections;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; final double dist = 2d;//the manhattan distance d&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea A = new ManhattanDistanceArea(new Vector3D(0, -3, 0), dist, "A");&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea B = new ManhattanDistanceArea(new Vector3D(0, 0, 0), dist, "B");&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea C = new ManhattanDistanceArea(new Vector3D(3.5, 0, 0), dist, "C");&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea D = new ManhattanDistanceArea(new Vector3D(0, 3.5, 0), dist, "D");&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea E = new ManhattanDistanceArea(new Vector3D(1, 1, 0), dist, "E");&nbsp; &nbsp; &nbsp; &nbsp; ManhattanDistanceArea F = new ManhattanDistanceArea(new Vector3D(-1, 1, 0), dist, "F");&nbsp; &nbsp; &nbsp; &nbsp; //test the example you provided&nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> abcde = new HashSet<ManhattanDistanceArea>();&nbsp; &nbsp; &nbsp; &nbsp; abcde.addAll(Arrays.asList(new ManhattanDistanceArea[] {A, B, C, D, E}));&nbsp; &nbsp; &nbsp; &nbsp; //test another example&nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> abcdef = new HashSet<ManhattanDistanceArea>();&nbsp; &nbsp; &nbsp; &nbsp; abcdef.addAll(abcde);&nbsp; &nbsp; &nbsp; &nbsp; abcdef.add(F);&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> intersectionsABCDE = getIntersectingAreas(abcde);&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<ManhattanDistanceArea>> intersectionsABCDEF = getIntersectingAreas(abcdef);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(intersectionsABCDE);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(intersectionsABCDEF);&nbsp; &nbsp; &nbsp; &nbsp; //test the runntime for 1000 calculation&nbsp; &nbsp; &nbsp; &nbsp; double startTime = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; final int calculations = 1000;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < calculations; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<ManhattanDistanceArea> areas = new HashSet<ManhattanDistanceArea>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < 20; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; areas.add(new ManhattanDistanceArea(new Vector3D(Math.random() * 10 - 5, Math.random() * 10 - 5, Math.random() * 10 - 5), dist,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "A" + j));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; getIntersectingAreas(areas);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("\nTime used for " + calculations + " intersection calculations (with sets of size 20): "&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + (System.currentTimeMillis() - startTime) + "ms");&nbsp; &nbsp; }}对于我使用此类 Vector3D 的实现：public class Vector3D {&nbsp; &nbsp; public double x;&nbsp; &nbsp; public double y;&nbsp; &nbsp; public double z;&nbsp; &nbsp; public static final Vector3D NAN_VEC = new Vector3D(Double.NaN, Double.NaN, Double.NaN);&nbsp; &nbsp; public static final Vector3D NULL_VEC = new Vector3D(0, 0, 0);&nbsp; &nbsp; public enum Axis {&nbsp; &nbsp; &nbsp; &nbsp; X, Y, Z;&nbsp; &nbsp; }&nbsp; &nbsp; public Vector3D() {&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Crate a new Vector2D with x and y components.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D(double x, double y, double z) {&nbsp; &nbsp; &nbsp; &nbsp; this.x = x;&nbsp; &nbsp; &nbsp; &nbsp; this.y = y;&nbsp; &nbsp; &nbsp; &nbsp; this.z = z;&nbsp; &nbsp; }&nbsp; &nbsp; public Vector3D(double... val) {&nbsp; &nbsp; &nbsp; &nbsp; x = val[0];&nbsp; &nbsp; &nbsp; &nbsp; y = val[1];&nbsp; &nbsp; &nbsp; &nbsp; z = val[2];&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Create a Vector3D by two angles (in degree).&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* The first angle is in XY direction. The second angle is the Z direction.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* An angle (XY) of 0° results in (x, y) = (1, 0); 90° in (x, y) = (0, 1); ... An angle (Z) of 0° results in (x, y, z) = (x, y, 0); 90° in (x, y,&nbsp; &nbsp; &nbsp;* z) = (x, y, 1); -90° in (x, y, z) = (x, y, -1)&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* The resulting vector has a length of 1.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param angleXY&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The angle of the new vector (in degree) for the XY direction (from 0 to 360).&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param angleZ&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The angle of the new vector (in degree) for the Z direction (from -90 to 90).&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D(double angleXY, double angleZ) {&nbsp; &nbsp; &nbsp; &nbsp; x = Math.cos(angleXY * Math.PI / 180) * Math.cos(angleZ * Math.PI / 180);&nbsp; &nbsp; &nbsp; &nbsp; y = Math.sin(angleXY * Math.PI / 180) * Math.cos(angleZ * Math.PI / 180);&nbsp; &nbsp; &nbsp; &nbsp; z = Math.sin(angleZ * Math.PI / 180);&nbsp; &nbsp; &nbsp; &nbsp; double len = length();&nbsp; &nbsp; &nbsp; &nbsp; x /= len;&nbsp; &nbsp; &nbsp; &nbsp; y /= len;&nbsp; &nbsp; &nbsp; &nbsp; z /= len;&nbsp; &nbsp; }&nbsp; &nbsp; private Vector3D(Vector3D clone) {&nbsp; &nbsp; &nbsp; &nbsp; this.x = clone.x;&nbsp; &nbsp; &nbsp; &nbsp; this.y = clone.y;&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public Vector3D clone() {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(this);&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; return "Vector3D[x: " + x + " y: " + y + " z:" + z + "]";&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public boolean equals(Object obj) {&nbsp; &nbsp; &nbsp; &nbsp; if (obj instanceof Vector3D) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Vector3D v = (Vector3D) obj;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return Math.abs(x - v.x) < 1e-8 && Math.abs(y - v.y) < 1e-8 && Math.abs(z - v.z) < 1e-8;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Get this vector as 3D-Array.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double[] asArray() {&nbsp; &nbsp; &nbsp; &nbsp; return new double[] {x, y, z};&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* The (euclidean) length of the Vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double length() {&nbsp; &nbsp; &nbsp; &nbsp; return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2) + Math.pow(z, 2));&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* The length of this vector in a given norm.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param norm&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The norm of the vector length.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The length of this vector in the given norm.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double length(int norm) {&nbsp; &nbsp; &nbsp; &nbsp; if (norm == Integer.MAX_VALUE) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return Math.max(Math.max(x, y), z);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return Math.pow(Math.pow(x, norm) + Math.pow(y, norm) + Math.pow(z, norm), 1.0 / norm);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Rotate this vector an angle (in degrees) around an axis resulting in a new Vector that is returned.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param degrees&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The angle to return the vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param axis&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The axis around which the vector is rotated.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new created vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D rotate(double degrees, Axis axis) {&nbsp; &nbsp; &nbsp; &nbsp; double cos = Math.cos(degrees * Math.PI / 180);&nbsp; &nbsp; &nbsp; &nbsp; double sin = Math.sin(degrees * Math.PI / 180);&nbsp; &nbsp; &nbsp; &nbsp; switch (axis) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case X:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x, cos * y - sin * z, sin * y + cos * z);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case Y:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(cos * x + sin * z, y, -sin * x + cos * z);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case Z:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(cos * x - sin * y, sin * x + cos * y, z);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; default:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Project the vector given as parameter on this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The vector that is to be projected on this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The projected vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D project(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return mult(scalar(vec) / Math.pow(length(), 2));&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Add another Vector3D to this vector resulting in a new Vector that is returned.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The vector added to this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new created vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D add(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x + vec.x, y + vec.y, z + vec.z);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Subtract another Vector3D from this vector resulting in a new Vector that is returned.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The vector subtracted from this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new created vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D sub(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x - vec.x, y - vec.y, z - vec.z);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Multiply this vector with a scalar resulting in a new Vector that is returned.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param scalar&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The scalar to multiply this vector with.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new created vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D mult(double scalar) {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x * scalar, y * scalar, z * scalar);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Check whether this vector is linearly dependent to the parameter vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The checked vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return True if the vectors are linearly dependent. False otherwise.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public boolean isLinearlyDependent(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; double t1 = (x == 0 ? 0 : vec.x / x);&nbsp; &nbsp; &nbsp; &nbsp; double t2 = (y == 0 ? 0 : vec.y / y);&nbsp; &nbsp; &nbsp; &nbsp; double t3 = (z == 0 ? 0 : vec.z / z);&nbsp; &nbsp; &nbsp; &nbsp; return Math.abs(t1 - t2) < 1e-5 && Math.abs(t1 - t3) < 1e-5 && t1 != 0;//all parameters t are equal and != 0&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Calculate the scalar product of this vector and the parameter vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The vector to calculate the scalar with this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The scalar of the vectors.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double scalar(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return this.x * vec.x + this.y * vec.y + this.z * vec.z;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Calculate the cross product of this vector with another vector (resulting vector = this X parameter vector)&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The second vector for the cross product calculation.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The cross product vector of the two vectors.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D cross(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(y * vec.z - z * vec.y, z * vec.x - x * vec.z, x * vec.y - y * vec.x);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Create a new vector with the same direction but a different length as this vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param length&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The length of the new vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new vector with a new length.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D setLength(double length) {&nbsp; &nbsp; &nbsp; &nbsp; double len = length();&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x * length / len, y * length / len, z * length / len);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Get the distance of this point's position vector to another point's position vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param p&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The second point's position vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The distance between the points.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double distance(Vector3D p) {&nbsp; &nbsp; &nbsp; &nbsp; return Math.sqrt((this.x - p.x) * (this.x - p.x) + (this.y - p.y) * (this.y - p.y) + (this.z - p.z) * (this.z - p.z));&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Get the distance of this point's position vector to another point's position vector in a given norm.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param p&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The second point's position vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param norm&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The norm in which the distance is calculated (1 -> manhattan, 2 -> euclide, ...)&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The distance between the points in the given norm.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double distance(Vector3D p, int norm) {&nbsp; &nbsp; &nbsp; &nbsp; return Math.pow((Math.pow(Math.abs(this.x - p.x), norm) + Math.pow(Math.abs(this.y - p.y), norm) + Math.pow(Math.abs(this.z - p.z), norm)),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1d / norm);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Change this vector to the new coordinates.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public void move(double x, double y, double z) {&nbsp; &nbsp; &nbsp; &nbsp; this.x = x;&nbsp; &nbsp; &nbsp; &nbsp; this.y = y;&nbsp; &nbsp; &nbsp; &nbsp; this.z = z;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Move a point's position vector in a direction (by a vector) and a distance.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param p&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The direction vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param distance&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The distance to move the new vector&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The new created vector.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D moveTo(Vector3D p, double distance) {&nbsp; &nbsp; &nbsp; &nbsp; double d = distance(p);&nbsp; &nbsp; &nbsp; &nbsp; double dx = p.x - x;&nbsp; &nbsp; &nbsp; &nbsp; double dy = p.y - y;&nbsp; &nbsp; &nbsp; &nbsp; double dz = p.z - z;&nbsp; &nbsp; &nbsp; &nbsp; double coef = distance / d;&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(x + dx * coef, y + dy * coef, z + dz * coef);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Get the angle difference of this vector to another vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The other vector.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The angle difference of the two vectors (from 0° to 180°).&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public double getAngleTo(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; double angle = Math.acos(scalar(vec) / (length() * vec.length())) * 180 / Math.PI;&nbsp; &nbsp; &nbsp; &nbsp; if (angle > 180) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; angle = 360 - angle;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return angle;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Get the vector from this point to another.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param vec&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The point to which the vector is calculated.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return The vector from this points position vector to the other point.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public Vector3D vectorTo(Vector3D vec) {&nbsp; &nbsp; &nbsp; &nbsp; return new Vector3D(vec.x - x, vec.y - y, vec.z - z);&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Checks whether a point (by its position vector) is in a given range of this point.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param p&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The point that is checked.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @param range&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp; &nbsp; The range used for the check.&nbsp; &nbsp; &nbsp;*&nbsp;&nbsp; &nbsp; &nbsp;* @return True if the point is in the range of this point (distance <= range).&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public boolean isInRange(Vector3D p, double range) {&nbsp; &nbsp; &nbsp; &nbsp; return p != this && distance(p) <= range;&nbsp; &nbsp; }}和apache 公共库中的SetUtils类。我还添加了一些测试：你的问题的测试另一个具有更大交叉集的测试运行时测试结果是：[[A, B], [B, E, C], [B, E, D]][[A, B], [B, E, C], [D, E, F, B]]用于 1000 个交点计算的时间（大小为 20 的集合）：791.0ms所以结果似乎是正确的，你可以在一秒钟内计算出 1000 多个交叉点。

Answer 2

20 个点之间的详尽距离计算，即 190 个距离对于 PC 来说毫无意义。时间将以微秒为单位。您可以从矩阵中编码的“接近”关系中提取所需信息。