java - 查找列表中两个元素的所有组合的最有效方法

Question

所以我有三门课。一方面有 Point 类:

public class Point {
    public float x;
    public float y;

    // Every point has a list of connections to other points indicated
    // by their position in the list of points in the main class.
    public List<Integer> connections = new ArrayList<>();

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }
}

另一方面，有 Line 类:

public class Line {
    public Point start;
    public Point end;

    public Line(Point start, Point end) {
        this.start = start;
        this.end = end;
    }
}

以及组合类:

public class Combination {
    public Line a;
    public Line b;

    public Combination(Line a, Line b) {
        this.a = a;
        this.b = b;
    }
}

我想要一种方法根据给定点生成的线返回所有可能组合的列表。我目前的方法如下:

public static List<Combination> findCombinations(List<Point> points) {
    List<Combination> combinations = new ArrayList<>();
    List<Line> lines = new ArrayList<>();

    for (Point a : points) {
        for (int p : a.connections) {
            lines.add(new Line(a, points.get(p)));
        }
    }

    for (Line a : lines) {
        for (Line b : lines) {
            if (a == b) continue;
            combinations.add(new Combination(a, b));
        }
    }

    return combinations;
}

我有一个包含点列表的基类。对于该类的每个实例，我只调用上面的方法一次。但是，会创建大量实例，此方法会减慢进程速度。

我需要找到组合，以便测试每个 Combination 实例中的两条线(线段)是否存在交集。我基本上想找到相交线的所有组合。为了实现这一点，我需要获取组合，然后检查交集在哪里。

交点的计算不是问题。

Answer 1

在这样的图表中，由点和线(通常称为节点和边)形成，所需的组合通常是动态迭代的。 因此，通常不应生成包含所有此类组合的显式列表。

如果您坚持创建所有组合，那么没有比迭代所有组合更快的方法了。 (更新:如果您的任务是找到所有线的交点，那么有更快的众所周知的算法。该领域称为计算几何)

如果图表是固定的，您可以加快一点速度，这样它在创建后就不会再改变。
在这种情况下，您可以替换

 public List<Integer> connections = new ArrayList<>();

使用更快的 int 数组，它也使用四分之一的内存:

public int[] connections.

这种优化通常需要两个步骤。使用 ArrayList 构建图表，然后在准备就绪后，使用 int[]

将所有图表转换为静态图表

您还提到了“效率”。尤其是在这里，人们必须在内存效率(例如，用于嵌入式导航系统)或计算速度(如具有大量内存时使用)之间做出选择。

你的解决方案和我的答案都与计算速度有关。