在2D-C中生成非退化点集

发布时间：2020-12-16 02:59:00 所属栏目：百科来源：网络整理

导读：我想在2D平面中创建一个非退化的整套随机点云(整个集合中没有3点).我有一个天真的解决方案,它产生一个随机浮点对P_new(x,y),并检查如果点(P1,P2,P)位于同一行中,直到现在生成的每对点(P1,P2).这需要对添加到列表中的每个新点进行O(n ^ 2)检查,从而使整个复杂

我想在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点,这似乎是确定的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!