Potrzeba wygenerowania dużej ilości losowych, ale najlepiej
wyglądających realistycznie wielokątów do pomiaru czasu algorytmów
przecinania, aby zobaczyć od jakiej wielkości wybrać metodę zamiatania
czy inną a do jakiej zostawić brute-force.
Jeden sposób to: generuję losowy punkt jako pierwszy wierzchołek, drugi
punkt jako drugi itd. Powstają samoprzecinające się figury z dużą
ilością przecięć, może nie maksymalną, ale większą niż "naturalne"
wielokąty. Drugi, przeciwny sposób to wygenerowanie dwóch wieloboków
foremnych przecinających się w dwóch punktach, otrzymamy figury wypukłe.
A czy jest jakaś metoda pośrednia? Niekoniecznie wypukły ale nie
samoprzecinający się, większa ilość przecięć niż dwa, ale nie za duża ?

do góry

W dniu 2014-12-07 o 16:57, Borneq pisze:
> A czy jest jakaś metoda pośrednia? Niekoniecznie wypukły ale nie
> samoprzecinający się, większa ilość przecięć niż dwa, ale nie za duża ?

Dobrze by było aby generował najróżniejsze przypadki, w tym złośliwe.
Ale z generowaniem losowym jest tak, że można nawet milion razy
wygenerować a nie będzie złośliwego, bo tak są rzadko. Choć w realnym
danych o wiele częściej.

do góry

On Sunday, December 7, 2014 4:58:14 PM UTC+1, Borneq wrote:
> Potrzeba wygenerowania dużej ilości losowych, ale najlepiej
> wyglądających realistycznie wielokątów do pomiaru czasu algorytmów
> przecinania, aby zobaczyć od jakiej wielkości wybrać metodę zamiatania
> czy inną a do jakiej zostawić brute-force.
> Jeden sposób to: generuję losowy punkt jako pierwszy wierzchołek, drugi
> punkt jako drugi itd. Powstają samoprzecinające się figury z dużą
> ilością przecięć, może nie maksymalną, ale większą niż "naturalne"
> wielokąty. Drugi, przeciwny sposób to wygenerowanie dwóch wieloboków
> foremnych przecinających się w dwóch punktach, otrzymamy figury wypukłe.
> A czy jest jakaś metoda pośrednia? Niekoniecznie wypukły ale nie
> samoprzecinający się, większa ilość przecięć niż dwa, ale nie za duża ?

Nie wiem... może wygenerować najpierw N jakiś 'prostych' figur? Mogą
to być prostokąty, sześciany, itd. Potem wygenerować punkty losowe, ale
w pobliżu wygenerowanych wcześniej. Losowymi zastępujemy oryginalne.
Metodę trzeba M razy zapętlić. Odległość losowania od oryginalnych punktów
trzeba uzależnić od rozmiaru prostej figury. Trzeba także pamiętać początkową
figurę - to będzie w przybliżeniu obrys tej losowej. Potem można przybliżać
do siebie figury, uzależniając odległość od rozmiaru 'prostych'. Przykładowo
jeśli prostą figurą był kwadrat o boku x, to odległość środków ustawiamy na
0.75 * x. Do tego jeszcze jakieś obroty... Jak się dobrze dobierze proste
figury i parametry, to powinny wyjść 'realistyczne' wielokąty :D

Pozdrawiam

do góry

W dniu 2014-12-09 o 11:44, M.M. pisze:
> trzeba uzależnić od rozmiaru prostej figury. Trzeba także pamiętać początkową
> figurę - to będzie w przybliżeniu obrys tej losowej. Potem można przybliżać
> do siebie figury, uzależniając odległość od rozmiaru 'prostych'. Przykładowo
> jeśli prostą figurą był kwadrat o boku x, to odległość środków ustawiamy na
> 0.75 * x. Do tego jeszcze jakieś obroty... Jak się dobrze dobierze proste
> figury i parametry, to powinny wyjść 'realistyczne' wielokąty :D

Czyli różne modyfikacje zadanych figur. Aby wielokąt miał więcej
punktów, można najpierw wygenerować 40-bok foremny a potem poprzesuwać
więcej lub mniej te wierzchołki.

Pozdrawiam

do góry

W dniu 2014-12-10 o 15:29, Borneq pisze:
> Czyli różne modyfikacje zadanych figur. Aby wielokąt miał więcej
> punktów, można najpierw wygenerować 40-bok foremny a potem poprzesuwać
> więcej lub mniej te wierzchołki.

Możemy się ograniczyć do zbioru nie powiązanych odcinków. Gdy generujemy
przez losowe wybranie początku i końca, odcinki będą raczej długie i
będą miały dużo przecięć. Można sparametryzować ich długość, od której
będzie zależała ilość przecięć. Wybieramy pierwszy punkt odcinka oraz
kąt w zakresie 0..2Pi drugiego punktu. Tu pewna niedogodność że odcinki
będą wychodziły poza zakres; gdy odcinek wyjdzie poza zakres (pierwszy
punkt będzie w zakresie a drugi nie), należy go przesunąć w stronę
pierwszego punktu.

do góry