我想在 2D 平面中创建一大组非退化的随机点云（整个集合中没有 3 个点在一条直线上）。我有一个简单的解决方案，它生成一个随机浮点对 P_new(x,y) 并检查到目前为止生成的每对点 (P1, P2) 是否位于同一行。这需要 O(n^2) 检查添加到列表中的每个新点，使得整个复杂性为 O(n^3)，如果我想生成超过 4000 个点（需要超过 40 分钟），这会非常慢。
有没有更快的方法来生成这些非退化点集？
您可以计算和比较线性方程的系数，而不是在每个循环迭代中检查可能的点共线性。该系数应存储在可快速搜索的容器中。我考虑使用 std::set，但 unordered_map 可以适合其中任何一个，并且可以带来更好的结果。
总而言之，我建议使用以下算法：
- 生成随机点
p;
- Compute 系数 http://en.wikipedia.org/wiki/Linear_equation交叉线数
p和现有的点（我的意思是通常A,B&C）。这里你需要做的n计算；
- 尝试在先前计算的集合中找到新计算的值。这一步需要
n*log(n^2)最大程度地进行操作。
- 如果搜索结果为负，则添加新值并将其系数添加到相应的集合中。其成本约为
O(log(n)) too.
整个复杂度降低为O(n^2*log(n))。
该算法需要额外存储n^2*sizeof(Coefficient)记忆。但如果您只想计算 4000 个点，这似乎没问题。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
