在2D - 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. 计算线交叉和现有点的系数p（我的意思是通常A, B& C）。这里需要进行n计算；
3. 尝试在先前计算的集合中找到新计算的值。此步骤需要n*log(n^2)最多操作。
4. 如果搜索结果为负，则添加新值并将其系数添加到相应的集合中。其成本O(log(n))也大约是。

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