Przyciąganie obiektów do jednego nieruchomego (zachowanie kolizji)

0

Witam!

Szukam już dłuższy czas, celowałem głównie w zagraniczne źródła, ale albo nie wiem jak pytać. Na stacoverflow zero zainteresowania (może algorytmów nie lubią). A może po prostu źle szukam gdyż nie wiem jak znaleźć to co mnie nurtuje. Już tłumacze o co mi chodzi:

Otóż załóżmy że mamy 20 obiektów (okręgi), teraz załóżmy ze wskazujemy sobie jeden z tych 20 obiektów. Teraz ostaje się tylko ten 1 wybrany a do okołą niego powinny pojawić się okręgi mu odpowiadające (dzieci), załóżmy że też 20. Każdy okrąg dziecka ma różny promień, między nimi nie mogą zachodzić kolizje (Trzeba je obsłużyć, niech się odpychają itp).

Efektem końcowym jest okrąg rodzic po środku (nie może się ruszyć nawet na chwile), oraz przyczepione do okoła niego różnych rozmiarów okręgi dzieci, żaden nie zachodzi na inny. Możliwie największy ścisk i równomierne rozłożenie.

Próbowałem robić wyżej wymieniony algorytm na własną rękę bez żadnych materiałów pomocniczych i to co mi wyszło bardzo mnie zmartwiło, gdyż mój algorytm ma duża złożoność nawet powyżej n^2 i trzeba go wykonywać albo do uzyskania pożądanego efektu albo przez ileść tam iteracji, np 200. Jednym słowem jest kiepski.

Czy mógłby ktoś podrzucić jakaś mądrą książkę, artykuł, kod źródłowy jakiś przykład cokolwiek co pomogło mnie naprowadzić na poprawny tor? Dodam że chodzi mi o odtworzenie trochę fizyki z http://bubblebrowserapp.com/

0

ale co to za algorytm? Ja tu nie widzę żadnego problemu do rozwiązania. Masz kółko, chcesz doczepić do niego inne kółka - w czym jest problem? Co ma złożoność n^2?

0

jeśli masz dużo kulek to podziel sobie przestrzeń na części i sprawdzaj kolizje tylko w tych fragmentach przez które przechodzi dana kulka podczas ruchu

0

Wszystko masz tu http://pl.wikipedia.org/wiki/Ci%C4%99ciwa

EDIT:
Środki twoich kręgów lezą na innym kręgu. Prosta łącząca środki dwóch sąsiednich kręgów jest cięciwą tego "innego" kręgu. Długość tej cięciwy równa sumie promieni dwóch sąsiednich kręgów (bo się stykają). Dalej - prosta matematyka.

0

Chyba nawet przez chwile nikt z was się nie zastanowił jaki to problem jeżeli kółka maja różne (losowe) rozmiary... I co cięciwa ma do zagadnienia? Wyobraz sobie ze 20 kołek jest obok siebie częsciowo sie nakładają i teraz chcemy by kółko numer 1 zostało na swojej pozycji a kółka od nr 2 do nr 20 możliwie przyczepiły się do okoła kółka nuemr 1 tak jakby ono było środkiem nawigacji, ale kółka musza dodatkowo unikać kolizji.

Nie mówcie że to banalne, bo słyszałem już podobne opinie od "znawców", a jak mieli napisać algorytm to utknęli na złożoności sporo większej od n^2. Jeżeli chcecie pomóc ( a mam nadzieje że chcecie ) to musicie dostrzec gdzie tu jest problem, problem jest z unikaniem kolizji i rózno wymiarowych bąblach, i tego że środek grawitacji nie jest punktem a okregiem z którym tez nie można kolidować. Ja naprawde mam taki algorytm sam go napisałem ale jego złożoność jest za duża dla JavaScriptu i rysowanych obiektów

EDIT:
W załączniku o to o co mi chodziło bo nikomu nie łaska przeczytać z zrozumieniem, tylko zaraz hejcic że nie myśle -.-

0

Po pierwsze mylisz się. Środkiem grawitacji jest punkt - środek okręgu. Tylko musisz sprawdzać czy pozostałe okręgi nie zbliżyły się bardziej niż na długość promienia.
Co do utrzymania tego konkretnego okręgu w bezruchu, to nie wiem co masz za problem, że kilka razy o tym wspominasz. Wystarczy przecież wywalić ten okrąg z kolekcji okręgów i trzymać gdzieś indziej, nie zmieniając jego statusu.
Pozostałe okręgi - dzieci możesz trzymać w R-drzewie (najlepiej imo w wariancie R+). A zamiast prostokątów, które są w opisie takiego drzewa, masz okręgi. Będziesz miał dużo lepszą złożoność.

0
Choody91 napisał(a):

one mają się stykać a nie nachodzić na siebie. Nie ma tutaj sytuacji że środki okręgów znajdują się na innym okręgu bo w sytuacji gdzie każdy krąg ma inny promień, nie da się wyznaczyć takowego.
Po włączeniu myślenia - da się.

Hasło RAR'a: 1234

tmp.jpg

0

Są jakieś problemy z programami w win 7 produkowane w Delphi?
Wydawało mi się że exe nie specjalnie zależy od użytego języka, czy kompilatora...

A sam problem nadaje się chyba do liczenia metodami Monte Carlo - wyżarzanie lub coś w tym stylu.

Bezpośrednie liczenie tego jest raczej mało sensowne.

1 użytkowników online, w tym zalogowanych: 0, gości: 1