生成非退化点集2D - C ++ [英] Generate Non-Degenerate Point Set in 2D - C++

问题描述

我想创建一个大组随机点云在二维平面是不变质（NO 3点在整套直线）。我有一个天真的溶液，其生成随机浮点对P_new（X，Y），并检验与每对点（P1，P2）到现在是否点（P1，P2，P）位于同一行或不产生。这需要为O（n ^ 2）检查添加到列表，使整个复杂度为O（n ^ 3）每一个新的起点，这是非常缓慢的，如果我想产生超过4000点（时间超过40分钟）。 有没有更快的方法来生成这些组非退化点？

I want to create a large set of random point cloud in 2D plane that are non-degenerate (no 3 points in a straight line in the whole set). I have a naive solution which generates a random float pair P_new(x,y) and checks with every pair of points (P1, P2) generated till now if point (P1, P2, P) lie in same line or not. This takes O(n^2) checks for each new point added to the list making the whole complexity O(n^3) which is very slow if I want to generate more than 4000 points (takes more than 40 mins). Is there a faster way to generate these set of non-degenerate points?

推荐答案

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

Instead of checking the possible points collinearity on each cycle iteration, you could compute and compare coefficients of linear equations. This coefficients should be store in container with quick search. I consider using std::set, but unordered_map could fit either and could lead to even better results.

要概括起来讲，我建议如下算法：

To sum it up, I suggest the following algorithm:

1. 生成随机点 P ;
2. 在计算系数线交叉 P 和现有点（我指的是通常的 A ， B ＆安培; C ）。在这里，你需要做的 N 计算;
3. 在试图找到pviously计算设定新计算值$ P $内。这一步需要 N *的log（n ^ 2）操作最大。
4. 在案件的负面搜索结果，增加新的价值，并增加其系数为相应配套。它的成本大约是 O（日志（N））了。

1. Generate random point p;
2. Compute coefficients of lines crossing p and existing points (I mean usual A,B&C). Here you need to do n computations;
3. Trying to find newly computed values inside of previously computed set. This step requires n*log(n^2) operations at maximum.
4. In case of negative search result, add new value and add its coefficients to corresponding sets. Its cost is about O(log(n)) too.

全复杂度降低到为O（n ^ 2 *的log（n））。 该算法需要的 N ^ 2 * sizeof的（系数）附加存储内存。但是，这似乎是确定的，如果你想计算4000点而已。

The whole complexity is reduced to O(n^2*log(n)). This algorithm requires additional storing of n^2*sizeof(Coefficient) memory. But this seems to be ok if you are trying to compute 4000 points only.

这篇关于生成非退化点集2D - C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！