Autor Wątek: Quadtree a figury geometryczne  (Przeczytany 995 razy)

Offline Furry

  • Użytkownik
    • DevBlog

# Grudzień 08, 2011, 19:31:55
Witam, zastanawiam się ostatnio nad wstawianiem konkretnych figur geometrycznych do drzewa czwórkowego i mam pytanie czy moja koncepcja jest dobra(dotąd wystarczało mi przechowywanie punktów ale jak to bywa, już mi nie wystarcza):
- punkt - wiadomo, dzielimy obszar drzewa na 4 części(tak długo jak trzeba) i wrzucamy go w docelowy prostokąt
- odcinek- nie bardzo mam pomysł jak to zrealizować. Myślałem nad podziałem odcinka na punkty co daną odległość. Czyli jak np mamy odcinek 10px to co 2 px bym wstawiał punkt do drzewa(który byłby jakimś wskaźnikiem na odcinek(?)). A później po wyszukaniu w danym obszarze zrobiłbym jakieś "unique" żeby na liście znalezionych odcinków nie było takich samych obiektów.
- okrąg - podobnie jak odcinek?
- koło/prostokąt - zrobić to samo co dla odcinka tylko z podziałem na x,y ?

Może jest jakieś lepsze rozwiązanie?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline _OskaR

  • Użytkownik

# Grudzień 08, 2011, 19:41:33
Jak chcesz rysować cały odcinek, to nie lepiej umieścić go trochę wyżej w drzewie (nie na liściu)? Co do figur etc. - bounding box.

Offline Furry

  • Użytkownik
    • DevBlog

# Grudzień 08, 2011, 20:02:13
Ale co mi daje to że umieszczę go wyżej? zawsze znajdzie się jakiś odcinek który przecina krawędzie "podziałek". Z resztą chciałbym rozpatrywać taki przypadek gdzie mam prawie same odcinki na przykład, czyli jest ich dużo i powinny być "głębiej" w drzewie

Co do bouding box - przecież to się właśnie sprowadza do wypełnionego prostokąta tak? I z tym też nie wiem czy koncepcyjnie dobrze kombinuję.

Offline Kos

  • Użytkownik
    • kos.gd

# Grudzień 08, 2011, 20:23:05
Hej, do czego Ci ma być potrzebne to drzewo? Co chcesz nim robić? Optymalizować przecięcia samych odcinków? Czy czego?


Offline Furry

  • Użytkownik
    • DevBlog

# Grudzień 08, 2011, 21:41:57
potrzebne mi jest to do optymalizacji znajdowania przecięcia danych odcinków lub okręgów(to jeszcze nie dokońca jestem pewny czy będzie sens ale dowiedzieć się jak to zrobić nie zaszkodzi) z daną figurą 2D (którą można uprościć do sprawdzenia kolizii kilku odcinków)