Mamy prostokąt N razy M oraz k linii długości L. Jaka będzie szacowana
liczba przecięć? Dla uproszczenia można by przyjąć kołowy zakres.
Przypomina to
https://en.wikipedia.org/wiki/Percolation_theory
Występowała tam jakaś stała matematyczna o której chyba można by
powiedzieć że to jeszcze jedna stała oprócz Pi i e.

do góry

On 12.12.2014 00:07, Borneq wrote:
> Mamy prostokąt N razy M oraz k linii długości L. Jaka będzie szacowana
> liczba przecięć?

k linii rozrzuconych na powierzchni 3Nx3M czy na powierzchni
100000Nx1000000M? ;-)

Liczy się gęstość linii.
Nie piszesz, czy przecięć z brzegiem, czy takżę wnętrzem prostokąta.

> Dla uproszczenia można by przyjąć kołowy zakres.

??

> Przypomina to
> https://en.wikipedia.org/wiki/Percolation_theory

Nie. To co opisałeś w niczym nie przypomina perkolacji,
może poza tym, żę jest popularny model perkolacji ciągłęj, gdzie
rzuca się losowo na płaszczyznę takie patyczki.

Zajmujesz się tym mozę poważniej i masz przypadkiem nmier,
gdzie opisano wykłądniki 'korekcyjne' dla skalowania
punktu przejśćia i szerokośći przejśćia wraz z wielkością
siatki?


> Występowała tam jakaś stała matematyczna o której chyba można by
> powiedzieć że to jeszcze jedna stała oprócz Pi i e.

To zrykły rachunek prawdopodobieństwa.

Mając N0,M0, \ro0 i L0
prawdopodobieństwo się nie zmieni, jeśli wszytko przeskalujemy:

N = NL/L
M = M0/L
L = 1
\ro = \ro*L^2

A zawsze jedna stałą mniej.

Najpierw, jakie jest prawdopodobieństwo, że trafisz patyczkiem,
jeśli patyczek ma określoną orientację alfa.
Musisz trafić pierwszym końcem patyczka w prostokąt, albo w obszar
oddalone od prostokąta o co najwyżej 1 _w kierunku alfa_.
Pierwszy koniec musi więc trafić w figurę będącą rozciagnięciem
prostokąta o L (1) w kierunku alfa.
Ta figura ma pole M*N + L * szer(alfa)
gdzie szer(alfa) to szerokość prostokąta w rzucie na protą
prostopadłą do lafas (szerokość cienia rzucanego w tym kierunku).

Trochę trygonometrii, rzut, dostaniesz wzorek.

Teraz musisz to uśrednić po dowolnym alfa (zakładam rówmonierny
rozkałd kątów). A więc 1/2pi Całka_0^2pi powierzchnia (alfa).

W przypadku gęstości liczba przecieć zadana ejst rozkłądem
poisona i ma wartość oczekiwaną jak przed chwilą policzona.

pzdr
bartekltg

do góry

W dniu 2014-12-12 o 01:08, bartekltg pisze:
> On 12.12.2014 00:07, Borneq wrote:
>> Mamy prostokąt N razy M oraz k linii długości L. Jaka będzie szacowana
>> liczba przecięć?
>
> k linii rozrzuconych na powierzchni 3Nx3M czy na powierzchni
> 100000Nx1000000M? ;-)

Nie, jedynie NxM ;) podczas gdy N może być 300 a M 200.

> Liczy się gęstość linii.
> Nie piszesz, czy przecięć z brzegiem, czy takżę wnętrzem prostokąta.

W ogóle nie z prostokątem, tylko wzajemna ilość przecięć się
"patyczków", przy czym patyczek ma zerową grubość.
Może leżeć na brzegu prostokąta, prostokąt 200x300 rozciąga się od
0..199 do 0..299, dla "uproszczenia" można zakładać całkowite
współrzędne końców odcinka, ale niecałkowite współrzędne przecięć i to
matematycznie zapewne wcale by nie uprościło.

> > Dla uproszczenia można by przyjąć kołowy zakres.

BO prostokąt a nawet kwadrat, ma taką cechę, że inaczej przycina gdy
wierzchołek wychodzi dołem a inaczej gdy trochę przesunięty i już
obcinanie bokiem. Z resztą dla kół też będą sieczne.
Najbardziej matematyczny problem to była by zapewne nieograniczona
powierzchnia i losowania nie równomierne, ale np. z rozkładu Gaussa.

Gdy punkt padnie wewnątrz - OK, ale co gdy padnie poza obrysem? Bo nie
chodzi mi o prostszy problem niezależnego losowania punktów (a czy jest
wzór przecięć dla tego?) tylko losowania pierwszego i losowania kąta
względnego drugiego punktu przy zadanej długości. To możemy przyciąć i
otrzymamy już inną długość albo przesunąć równolegle w stronę pierwszego
punktu, wtedy otrzymamy pierwszy inny niż losowaliśmy, oba zaburzają
matematykę.

> Ta figura ma pole M*N + L * szer(alfa)
> gdzie szer(alfa) to szerokość prostokąta w rzucie na protą
> prostopadłą do lafas (szerokość cienia rzucanego w tym kierunku).
>
> Trochę trygonometrii, rzut, dostaniesz wzorek.
>
> Teraz musisz to uśrednić po dowolnym alfa (zakładam rówmonierny
> rozkałd kątów). A więc 1/2pi Całka_0^2pi powierzchnia (alfa).
>
> W przypadku gęstości liczba przecieć zadana ejst rozkłądem
> poisona i ma wartość oczekiwaną jak przed chwilą policzona.

Czyli da się uzyskać wzór? Potrzebny zwłaszcza wzór odwrotny.
Było by dobrze do testowania szybkości algorytmów przecinania się linii
i nie tylko, które zależą od n odcinków i k przecięć. Funkcja f(n,k,
rozmiar kwadratu) dawała by wymaganą długość linii dla wybranych n i
rozmiar kwadratu.

Pozdrawiam

do góry

Zrobiłem zliczanie przecięć dla prostego przypadku zliczania
x0 = random(n)
y0 = random(n)
x1 = random(n)
y1 = random(n)

i co otrzymałem?
n^2/Pi/e

Pi i e w jednym równaniu

do góry