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