我想在2D平面中创建一个非退化的整套随机点云(整个集合中没有3点).我有一个天真的解决方案,它产生一个随机浮点对P_new(x,y),并检查如果点(P1,P2,P)位于同一行中,直到现在生成的每对点(P1,P2).这需要对添加到列表中的每个新点进行O(n ^ 2)检查,从而使整个复杂度O(n ^ 3)非常慢,如果我想生成超过4000点(需要40分钟以上).
有没有更快的方法来生成这些非退化点？
有没有更快的方法来生成这些非退化点？
解决方法
您可以计算和比较线性方程组的系数,而不是检查每个循环迭代中可能的点共线性.该系数应该存储在容器中快速搜索.我考虑使用std :: set,但是unordered_map可以适合,也可能导致更好的结果.
总结一下,我建议以下算法：
>生成随机点p;
>计算coefficients线穿过p和现有点(我的意思是平均A,B和C).在这里你需要做n个计算;
>尝试在先前计算的集合中查找新计算的值.此步骤最多需要n * log(n ^ 2)操作.
>如果是负搜索结果,请添加新值并将其系数添加到相应的集合中.其成本约为O(log(n)).
整个复杂度降低到O(n ^ 2 * log(n)).该算法需要额外存储n ^ 2 * sizeof(系数)存储器.但是,如果您只想计算4000点,这似乎是确定的.
