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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

• для предыдущих точек P calc (dx, dy) = P - Q

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

• сортировать список точек P по его значению B, так что точки, которые образуют линию с Q, будут находиться в ближайших позициях внутри отсортированного списка.

• пройдите по отсортированному списку, где 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/С++, вероятно, сделает его на два порядка быстрее.

Ответ 5

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

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