logo标签列表

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

c++algorithmcomputational-geometry
10

我希望创建一个2D平面内的大量随机点云，这些点不能退化（集合中不存在三个共线点）。我有一个天真的解决方案，它生成一个随机的浮点数对P_new(x,y)，并检查直到现在生成的每一对点(P1,P2)，看看点(P1,P2,P)是否在同一条直线上。这需要对每个新增加到列表中的点进行O(n^2)次检查，使得整个复杂度为O(n^3)，如果我想生成超过4000个点，就会非常慢(需要超过40分钟)。是否有更快的方法来生成这些非退化点集？

1
这个点云需要遵循什么样的随机分布，如果有的话？它应该是白噪声、粉色噪声、布朗噪声还是其他类型的噪声？设计一个算法比较容易，例如任何新添加的点都保证不会落在与另外两个点共线的位置上（只需沿着任何正曲率曲线的周长分布它们，例如圆形），但这种随机点云可能并不完全符合您的要求。 - Martin Sojka
如果您正在生成实数 2D 平面上的点，则在包含有限数量的点的云中，随机对齐三个点的可能性在理论上为零。 - Tugrul Ates
2
@junjanes：实际上，对于浮点数（三个点），它大约是1/组合（2 ^（尾数位数+1），3）（有关更多信息，请参见->生日悖论）。 - Martin Sojka
我明白了，实际上可能性非常低，但我想检查一下可能性，以避免我的点集退化。 - alpha_cod
5个回答
4

不必在每个循环迭代中检查可能的点共线性，而是可以计算并比较线性方程的系数。这些系数应存储在具有快速搜索功能的容器中。我考虑使用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个点，这似乎是可以接受的。

1
@unkulunkulu，@grep。实际上，竖线并不是非常严重的问题，因为我建议使用线性方程形式Ax+By+C=0，而不是kx+b=0。竖线方程是Ax+C=0（B=0），这里没有无限数量。 - eugene_che
1
每行都有几种表示方式，我猜你必须进行规范化处理，否则搜索可能会很困难。 - Tobias Langner
2
@Aditya。集合中最多有n ^ 2个元素。因此，每个模式的二分搜索复杂度为log(n * n)。有n个模式。因此，总体复杂度为O(n * log(n))。 - eugene_che
1
规范化是个不好的主意，因为它会引入平方根，从而导致非常棘手的精度问题。 - unkulunkulu
1
使用哈希表来消除O(N*log(N))的搜索。这将使整个算法变为O(N^2)。 - salva
显示剩余10条评论
4

可以通过以下方式轻松构建O(n^2 log n)算法：

对于集合中的每个点P：

  1. Sort other points by polar angle (cross-product as a comparison function, standard idea, see 2D convex hull gift-wrapping algorithm for example). In this step you should consider only points Q that satisfy 

    Q.x > P.x || Q.y >= P.y

  2. Iterate over sorted list, equal points are lying on the same line.

排序的时间复杂度为O(n log n)，第二步是O(n)。这将使去除退化点的时间复杂度为O(n^2 log n)。

@salva，你是如何使用基数排序算法按极角对向量进行排序的？ - unkulunkulu
简而言之，您将双精度浮点数转换为字符串形式进行比较，然后执行最高位数字基数排序。实际上，递归变体可能更快。请参阅维基百科页面及其链接部分。 - salva
@salva，抱歉，但这应该是某种玩笑，因为将双精度转换为字符串会破坏基数提供的一切。此外，在这个特定的算法中，我们没有明确的双精度数进行比较：叉积符号作为广义比较函数，因此我们必须使用仅使用比较的通用排序之一，这就是我想知道基数在这个任务中的适用性的原因。 - unkulunkulu
你不需要将双精度数转换为字符串表示，而是应用一种变换，使它们可以按字节进行比较。实际上，这意味着对双精度数的本机二进制表示执行一些基本操作（例如and、or、not、neg）。 - salva
@salva，好的，你能给我一个链接到某个人做这件事的论文或网页吗？无论如何，我没有任何需要排序的双倍数，所以这对于这个特定的答案没有帮助。 - unkulunkulu
谷歌是你的朋友！无论如何，看看这个：https://dev59.com/T2445IYBdhLWcg3w6eRo。我自己回复了OP并提到了一个实现它的Perl模块。 - salva
3
确定一组点是否退化是一个3SUM难问题。（列出的第一个问题是确定三条线是否包含共同点；在射影对偶下等价的问题是三个点是否属于一条公共线。）因此，期望产生和测试解决方案比n2快得多是不合理的。
您对分发的要求是什么？
2

  1. 生成随机点Q。

  2. 对于之前的点P，计算(dx, dy) = P - Q。

  3. 并且B = (abs(dx) > abs(dy) ? dy/dx : dx/dy)。

  4. 按照其B值对点P的列表进行排序，以便与Q形成线条的点在排序后的列表中靠近位置。

  5. 遍历排序后的列表，检查Q与当前考虑的P值以及一些比给定距离更近的下一个值形成线条的位置。

Perl实现：

#!/usr/bin/perl

use strict;
use warnings;
use 5.010;

use Math::Vector::Real;
use Math::Vector::Real::Random;
use Sort::Key::Radix qw(nkeysort);

use constant PI => 3.14159265358979323846264338327950288419716939937510;

@ARGV <= 2 or die "Usage:\n  $0 [n_points [tolerance]]\n\n";

my $n_points = shift // 4000;
my $tolerance = shift // 0.01;

$tolerance = $tolerance * PI / 180;
my $tolerance_arctan = 3 / 2 * $tolerance;
#     I got to that relation using no so basic maths in a hurry.
#     it may be wrong!

my $tolerance_sin2 = sin($tolerance) ** 2;

sub cross2d {
    my ($p0, $p1) = @_;
    $p0->[0] * $p1->[1] - $p1->[0] * $p0->[1];
}

sub line_p {
    my ($p0, $p1, $p2) = @_;
    my $a0 = $p0->abs2 || return 1;
    my $a1 = $p1->abs2 || return 1;
    my $a2 = $p2->abs2 || return 1;
    my $cr01 = cross2d($p0, $p1);
    my $cr12 = cross2d($p1, $p2);
    my $cr20 = cross2d($p2, $p0);
    $cr01 * $cr01 / ($a0 * $a1) < $tolerance_sin2 or return;
    $cr12 * $cr12 / ($a1 * $a2) < $tolerance_sin2 or return;
    $cr20 * $cr20 / ($a2 * $a0) < $tolerance_sin2 or return;
    return 1;
}

my ($c, $f1, $f2, $f3) = (0, 1, 1, 1);

my @p;
GEN: for (1..$n_points) {
    my $q = Math::Vector::Real->random_normal(2);
    $c++;
    $f1 += @p;
    my @B = map {
        my ($dx, $dy) = @{$_ - $q};
        abs($dy) > abs($dx) ? $dx / $dy : $dy / $dx;
    } @p;

    my @six = nkeysort { $B[$_] } 0..$#B;

    for my $i (0..$#six) {
        my $B0 = $B[$six[$i]];
        my $pi = $p[$six[$i]];
        for my $j ($i + 1..$#six) {
            last if $B[$six[$j]] - $B0 > $tolerance_arctan;
            $f2++;
            my $pj = $p[$six[$j]];
            if (line_p($q - $pi, $q - $pj, $pi - $pj)) {
                $f3++;
                say "BAD: $q $pi-$pj";
                redo GEN;
            }
        }
    }
    push @p, $q;
    say "GOOD: $q";
    my $good = @p;
    my $ratiogood = $good/$c;
    my $ratio12 = $f2/$f1;
    my $ratio23 = $f3/$f2;
    print STDERR "gen: $c, good: $good, good/gen: $ratiogood, f2/f1: $ratio12, f3/f2: $ratio23                                  \r";
}
print STDERR "\n";

公差指当考虑三个点是否在一条直线上时的可接受误差，其表示为π-max_angle(Q, Pi, Pj)中的角度。

它并没有考虑到在减去向量时可能出现的数值不稳定性（即|Pi-Pj|可能比|Pi|小几个数量级）。消除该问题的简单方法是还要要求任意两个给定点之间的最小距离。

将公差设置为1e-6，程序只需几秒钟即可生成4000个点。将其转换为C/C++可能会使其快两个数量级。

1

O(n)解决方案：

  1. 从0..1中选择一个随机数r
  2. 添加到云中的点是P(cos(2 × π × r), sin(2 × π × r))
它们中的两个最终可能会相同。 - unkulunkulu
@unkulunkulu：如果进行检查，整个过程最多只需要O(n log n)的时间。:)尽管如此，我仍然怀疑当alpha_cod要求“随机点云”时，结果是否完全符合他的想法，但问题有点不太明确。 - Martin Sojka
@Martin Sojka：如果使用哈希或基数排序来消除重复项，则其时间复杂度为O(N)。 - salva
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接