c++ - 生成二维非退化点集 - C++

Question

我想在 2D 平面中创建一大组非退化的随机点云(整组中直线上没有 3 个点)。我有一个天真的解决方案，它生成一个随机浮点对 P_new(x,y) 并检查到目前为止生成的每一对点 (P1, P2) 是否点 (P1, P2, P) 位于同一条线上。这需要 O(n^2) 检查添加到列表中的每个新点，使得整个复杂度为 O(n^3) 如果我想生成超过 4000 个点(需要超过 40 分钟)，这将非常慢。 有没有更快的方法来生成这组非退化点？

Answer 1

您可以计算和比较线性方程的系数，而不是在每个循环迭代中检查可能的点共线性。该系数应存储在容器中以进行快速搜索。我考虑使用 std::set，但 unordered_map 可以适合其中任何一个，并可能导致更好的结果。

总而言之，我建议使用以下算法:

1. 生成随机点p;
2. 计算 coefficients穿过 p 和现有点的线(我的意思是通常的 A、B 和 C)。这里需要做n次计算；
3. 尝试在先前计算的集合中找到新计算的值。此步骤最多需要 n*log(n^2) 操作。
4. 如果搜索结果为负，则添加新值并将其系数添加到相应的集合中。它的成本也是大约 O(log(n))。

整个复杂度降低到O(n^2*log(n))。 该算法需要额外存储 n^2*sizeof(Coefficient) 内存。但如果您只想计算 4000 个点，这似乎没问题。