[K.....1]

#optymalizacja #algorytmy #cpp #programowanie #programowaniegrafiki #gamedevelopment Mireczki, da się jakoś zoptymalizować poniższy problem?

1. Mamy zbiór punktów w 3d (x,y,z) np. 100
2. Punkty nie sa statyczne, w każdej kolejnej klatce trochę się przesuwają w różnych kierunkach

Zadanie:
Wybieramy kilka punktów, np. dziesięć. Dla każdego z tych punktów musimy wyznaczyć dwa najbliższe jemu punkty.

No i teraz pytanie czy da się to jakoś optymalniej zrobić niż tak:
https://pastebin.com/z8WRZ7tU

for (int i = 0; i < wybranepunkty; i++)
{
for (int j = 0; j < iloscpunktow; j++)
{
dodaj do listy dlugosc(i,j);
}
sortuj liste;

dwa najblizsze punkty to lista(0) i lista(1)
}

[K.....1]

@Kopytko1: dla kilku punktow nie bedzie roznicy ale dla wiekszej ilosci punktow juz bedzie duzy spadek szybkosci, w koncu w trzeba wiele razy wykonac sortowanie

[tell_me_more]

@Kopytko1: oczywiście, że się da, sortowanie jest niepotrzebne, zamiast tego przechowuj 2 dotychczas najbliższe punkty i ich odległości dla każdego wybranego punktu (czyli w sumie 20 punktów i 20 odległości) - i jak przelatujesz tablicę wszystkich punktów to aktualizuj tylko te 2 punkty.

To jak algorytm liczenia maksimum czy minimum w tablicy, tylko nie przechowujesz 1 wartości wg 1 kryterium, a 20 wartości wg 10 kryteriów.

Punkt najblizszyPunktNr1Od[10];
Punkt najblizszyPunktNr2Od[10];
float

[K.....1]

@tell_me_more: tak, faktycznie.. tzn dla dwóch to spoko bo to mozna po prostu porownaniem zrobic w tej calej iteracji.. ale nie wiem czy do konca rozumiem to co napisaleś, bo jakbym mial znalesc np. 20 najblizszych punktów no to i tak bym musiał jeszcze jednego fora zrobić żeby porównywać z resztą..

[JimHalpert]

@Kopytko1: Możesz spróbować podzielić przestrzeń 3d na podobszary 3d o jakimś rozmiarze i przyporządkować do nich wszystkie punkty. Później szukając najbliższego sąsiada dla jakiegoś punktu nie musisz przechodzić przez wszystkie istniejące punkty - zaczynasz od obszaru w którym ten punkt się znajduje, następnie przechodzisz przez 26 obszarów dookoła niego, jeśli tam nie znajdziesz żadnego sąsiedniego punktu, to idziesz do kolejnej warstwy itd. Powinno być to wydajne rozwiązanie dla dużej ilości punktów.

[K.....1]

@tell_me_more: hm w kazdym razie dzięki, musze sie temu przyjrzeć

[K.....1]

@JimHalpert: teoretycznie tak, ale trzeba by budowac taka strukture albo jakeis drzewko binarne chyba w kazdej klatce animacji (bo punkty sie przemieszczają), wiec budowa takiej struktury w kazdej klatce + wyszukiwanie to raczej tez spadnie performance..

[tell_me_more]

@Kopytko1: zamiast trzymać w tablicach możesz zrobić mapę:

struct DaneKandydata {
Punkt punkt;
float odleglosc;
};

struct Klucz {
int numerWybranegoPunktu;
int kolejnosc;
};

std::map dotychczasowiNajlepsiKandydaciDlaPunktuIKolejnosci;

i wypelniac mape dla kolejnosc = 1,...,K gdzie K to ile najbliższych punktów chcesz dla każdego wybranego.

Możesz też to zoptymalizować indeksowaniem przestrzeni, ale jeśli punkty mogą się ruszać, to jest spora szansa że nie przyśpieszysz (zależy, czy mogą się ruszać dowolnie, czy np. tylko

[K.....1]

@tell_me_more: ok, spoko.. map raczej nie uzyje, kiedys testowalem bylo to dosc wolne, robilem tez testy z duza iloscia punktów przy uzyciu std:sort i w sumie bylo nawet całkiem szybko.. przyjrze się jeszcze tej metodzie którą wypisałem wczesniej..

[surlin]

@Kopytko1: Możesz spróbować podzielić przestrzeń 3d na podobszary 3d o jakimś rozmiarze i przyporządkować do nich wszystkie punkty. Później szukając najbliższego sąsiada dla jakiegoś punktu nie musisz przechodzić przez wszystkie istniejące punkty -

@JimHalpert: Dla 100 punktów szkoda wysiłku. Dla większej ilości ja bym zrobił tak:
Mamy punkt k którego najbliższego sąsiada poszukujemy więc:
1. Ustalamy promień sfery - r.
( Na bazie doświadczenia, lub jeżeli punkty są losowe w

[K.....1]

@surlin: hmm aby sprawdzić czy jakiś punkt znajduje się w sferze trzeba i tak przejść przynajmniej raz przez wszystkie, jeśli sfera będzie za małą to trzeba będzie przejść kilka razy zanim się punkt znajdzie, no ciekawe rozwiązanie w każdym razie

[surlin]

@Kopytko1: Ewentualnie nieco prostsza metoda (cały czas mowa o wielu punktach):
Zmieniasz układ odniesienia tak, aby punkt do którego odległości chcesz mierzyć miał współrzędne... początku układu współrzędnych.
np. (2,4,10) - zmieniasz na (0,0,0) - czyli, dla każdego punktu wykonujesz operację (x,y,z)=(x-2,y-4,z-10).

Teraz pytanie, czy chcesz mierzyć konkretnie tę odległość, czy tylko wskazać punkt najbliższy.
Aby bowiem zmierzyć dokładnie musisz dla każdego z punktów spierwiastkować wynik x^2+y^2+z^2, jeżeli nie - wystarczy ta

[surlin]

@surlin: hmm aby sprawdzić czy jakiś punkt znajduje się w sferze trzeba i tak przejść przynajmniej raz przez wszystkie, jeśli sfera będzie za małą to trzeba będzie przejść kilka razy zanim się punkt znajdzie, no ciekawe rozwiązanie w każdym razie

@Kopytko1: W sumie masz rację :)
W drugiej metodzie, gdy punkt ma odległość np. 100 - możesz od razu odrzucać wszystkie punkty w których dowolna ze współrzędnych jest większa niż

[surlin]

@surlin: hmm aby sprawdzić czy jakiś punkt znajduje się w sferze trzeba i tak przejść przynajmniej raz przez wszystkie, jeśli sfera będzie za małą to trzeba będzie przejść kilka razy zanim się punkt znajdzie, no ciekawe rozwiązanie w każdym razie

@Kopytko1: Po kilku sekundach stwierdzam, że jednak nie do końca :P
Możesz rozważyć sześcian wpisany i opisany na takiej sferze. Wtedy gdy punkt leży w sześcianie wpisanym a w opisanym

[m4cias]

@Kopytko1: na pewno możesz zamiast odległości liczyć kwadrat odległości, mniej obliczeń (odchodzi pierwiastkowanie) a do porównania z innymi odległościami wynik jest ten sam. Może wiele nie da ale zawsze coś.

[michal951]

@Kopytko1: dla 100 punktów nie ma co kombinować, cokolwiek byś nie zrobił uzysk będzie minimalny. Jeżeli natomiast będziesz miał w swoim zbiorze "nieskończenie wiele" punktów to ja bym się wtedy zainteresował jakąś strukturą drzewiastą, pierwsze co mi przyszło do głowy to octree ale żeby to dobrze działało to musisz mieć jakiś zasięg. Ostatnio w pracy miałem podobny problem (ostatecznie jeszcze go nie ruszyłem) i zastanawiałem się nad zastosowaniem BST.

[s.....1]

@Kopytko1: To jedyny sposób bo musisz przebrnąć przez wszystkie punkty. A jeżeli chcesz możesz zrobić drzewo i wyszukiwać elementów w drzewie.