[Gumaa]

Mam kilka okręgów i znam ich położenie środka oraz promień. W jaki najbardziej wydajny sposób mogę sprawdzić, czy na siebie nachodzą?

#pytanie #pytaniedoeksperta #programowanie #matematyka

[a.....y]

@Gumaa: współrzędne biegunowe

[S.....s]

@Gumaa: dużo to jest kilka?
chyba najprościej każdy z każdym sprawdzić cy suma promieni jest mniejsza niż odległość pomiędzy środkami

[Gumaa]

dużo to jest kilka?

@SuppressWarnings: co? ( ͡° ͜ʖ ͡°)
Dostaję od kilku do kilkunastu takich okręgów ponad 30 razy na sekundę. Typowe obliczanie odległości zawierające potęgi może trochę spowolnić działanie.

współrzędne biegunowe

@adgebworthy: coś więcej na ten temat?

[M.....k]

@Gumaa:
No ze wzoru Pitagorasa liczysz sobie odległość między środkami:

d = sqrt((x0-x1)^2 + (y0-y1)^2)

I potem sprawdzasz czy ta odległość, jest w przedziale:

|p1-p2| <= d <= p1+p2

Jak chcesz zrobić to wydajniej, to podnosisz obie strony do kwadratu dzięki czemu unikniesz kosztowanego obliczeniowo pierwiastkowania:

(p1-p2)^2 <= (x0-x1)^2 + (y0-y1)^2 <= (p0+p1)^2

Potęgę ^2 możesz zastąpić przesunięciem bitowym o jeden to będzie jeszcze szybciej:

((p1-p2) << 1) <= ((x0-x1) <<

[YuiMizuno]

Potęgę ^2 możesz zastąpić przesunięciem bitowym o jeden to będzie jeszcze szybciej.

@MDobak: raczej mnożenie przez 2, a nie potęgę

[S.....s]

@Gumaa: serio? xd
no to liczmy 20 okręgów 50 razy na sekundę:
każdy z każdym to 9500 obliczeń na sekundę, czyli wychodzi trochę ponad 10 milisekund na jedno
a w rzeczywistości to się liczy około 0,0001 ms

[M.....k]

@YuiMizuno: Masz rację, rozpędziłem się ;)

[Mr_Przyjemny]

@Gumaa: Ale liczysz to na embedded czy jednak na normalnym pc? jak na pc to @SuppressWarnings Ci odpowiedzial.

co do embedded zalezy od procka ale znam kilka sposobow optymalizacji tego typu algorytmow

[Gumaa]

@Mr_Przyjemny: w JavaScripcie który do najszybszych nie należy ( ͡° ͜ʖ ͡°)

No i do tego dochodzi sporo innych obliczeń, dlatego chciałem to ładnie zoptymalizować.

[T.....y]

@Gumaa: spokojnie da radę z różnicy odległości nawet jakbyś liczył to nieoptymalnie

[Mr_Przyjemny]

@Gumaa: Hmm to biorac pod uwage ze to pc to mozna rozwazyc: stablicowanie tego pierwiastka:
d = sqrt((x0-x1)^2 + (y0-y1)^2)
tzn raz sobie deklarujesz duza tablice z wynikami i porownujesz zamiast liczyc w locie:
https://pl.wikipedia.org/wiki/Tablicowanie

ale nie wiem czy to nie overkill troche

[nilphilus]

@Gumaa: js jest dosyć szybkie wbrew pozora, zla opinie dostal bo się używało go z DOM

A jak masz dużo okręgów to możesz poszukać jak z tym sobie gamedev radzi ;-) trochę rozwiązań będzie

[fizyk20]

każdy z każdym to 9500 obliczeń na sekundę, czyli wychodzi trochę ponad 10 milisekund na jedno

@SuppressWarnings: Trochę ponad 0,1 ms na jedno. Ale i tak nie powinno to sprawiać problemów, 0,1 ms to kupa czasu dla procesora.

[S.....s]

@fizyk20: rzeczywiście jebłem się

[Minemaniak1]

@Gumaa: Powinno się tu sprawdzić zamiatanie, chociaż dla tak małej ilości danych jest to raczej bez znaczenia.