Создать невырожденный набор точек в 2D - C ++

Question

Я хочу создать большой набор случайных облаков точек в 2D-плоскости, которые не являются вырожденными (нет 3 точек на прямой линии во всем наборе). У меня есть наивное решение, которое генерирует случайную пару с плавающей точкой P_new (x, y) и проверяет каждую пару точек (P1, P2), сгенерированных до сих пор, если точки (P1, P2, P) лежат на одной линии или нет. Это требует O (n ^ 2) проверок для каждой новой точки, добавленной в список, что делает всю сложность O (n ^ 3) очень медленной, если я хочу создать более 4000 точек (занимает более 40 минут). Есть ли более быстрый способ генерации этого множества невырожденных точек?

Answer 1

Алгоритм

O (n ^ 2 log n) можно легко построить следующим образом:

Для каждой точки P в наборе:

1. Сортировка других точекпо полярному углу (перекрестное произведение в качестве функции сравнения, стандартная идея, см., например, алгоритм упаковки подарков двумерной выпуклой оболочки).На этом шаге вы должны рассмотреть только точки Q, которые удовлетворяют

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

2. Итерировать по отсортированному списку, равные точки лежат на одной линии.

Сортировка выполняется в O (n log n), шаг 2. - O (n).Это дает O (n ^ 2 log n) для удаления вырожденных точек.

Answer 2

Вместо проверки возможной коллинеарности точек на каждой итерации цикла, вы можете вычислять и сравнивать коэффициенты линейных уравнений.Эти коэффициенты должны храниться в контейнере с быстрым поиском.Я рассматриваю возможность использования std :: set, но unordered_map может подойти и для получения лучших результатов.

Чтобы подвести итог, я предлагаю следующий алгоритм:

1. Генерация случайной точкиp;
2. Вычислить коэффициенты линий, пересекающих p и существующие точки (я имею в виду обычные A, B & C).Здесь необходимо выполнить n вычисления;
3. Попытка найти недавно вычисленные значения внутри ранее вычисленного набора.Этот шаг требует максимум 1018 * операций.
4. В случае отрицательного результата поиска, добавьте новое значение и добавьте его коэффициенты к соответствующим наборам.Его стоимость тоже около O(log(n)).

Вся сложность уменьшена до O(n^2*log(n)).Этот алгоритм требует дополнительного хранения n^2*sizeof(Coefficient) памяти.Но, похоже, это нормально, если вы пытаетесь вычислить только 4000 баллов.

Answer 3

Определение, является ли набор точек вырожденным, является 3SUM-трудной задачей .(Самая первая из перечисленных проблем состоит в том, чтобы определить, содержит ли три линии общую точку; эквивалентная проблема в проективной двойственности состоит в том, принадлежат ли три точки общей линии.) Таким образом, нет оснований надеяться, что решение для генерации и проверки будетбыть значительно быстрее, чем n ² .

Каковы ваши требования для распространения?

Answer 4

1. генерирует случайную точку Q

2. для предыдущих точек P вычислить (dx, dy) = P - Q

3. и B = (asb(dx) > abs(dy) ? dy/dx : dx/dy)

4. отсортировать список точек P по значению B, чтобы точки, образующие линию с 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 ++, вероятно, сделает его на два порядка быстрее.

Answer 5

O (n) решение:

1. Выберите случайное число r из 0..1
2. Точка, добавленная к облаку, равна P(cos(2 × π × r), sin(2 × π × r))