Kolize bodu s úsečkami

[micky]

Zdravím, píšu takový menší program... Na scéně jsou rozmístěny body, které lze různě propojit úsečkami. Průšvih nastává ve chvíli, kdy mám uživateli umožnit jejich odstranění. I přes nějaké ty optimalizace, že nejprve kontroluju rámeček vytyčený dvěma body, a pak teprve rovnici přímky, jsem stále na složitosti O(N*N/2). Při větším množství bodů na scéně výběr úsečky začne lagovat...

Napadlo mě tedy:
1/ mít jakousi bitmapu, do které by se úsečky předrenderovaly a pak už jen přečíst po kliknutí hodnotu pixelu - to mi přijde jako řešení z nouze
2/ rozsekat scénu do stromu - tady si nevím rady, s body bych si poradil, z úseček mám obavy...

Jen bych dodal, že scéna je 2D. S kolizí samotnou nemám problém, spíš bych potřeboval odkaz na nějaké poučné pojednání o kolizích s velkým množstvím úseček. Díky mockrát za případné rady a postřehy.

[michalferko]

Na to by sa hodil quadtree alebo nejaka podobna hierarchicka struktura
_________________
Moje minihry a ine projekty

[micky]

Jak do quadtree zahrnu dvojice bodů? Stačí mi to jen nastínit

EDIT: Úsečka = dva body + to mezi nimi... tak bych to zjednodušeně viděl

[nou]

mas to cele v 2D. a vyberas jednotlive body pomocou obdlznikovych oblasti. ved to sa da riesit v linearnom case. a usecku vyberiem akonahle je tam len jeden z koncvich bodov.

neviem co ti tam tvory tu O(N^2) zlozitost.
_________________
Najjednoduchšie chyby sa najtažšie hľadajú.

[micky]

[pcmaster]

Quadtree je len specialny pripad Octree. Podobne vztahy su celkovo medzi kD-tree, BSP-tree, Octree atd.

Keby si chcel riesit aj taku moznost, ze mas body a niektore su pospojovane useckami a user ma mat moznost oznacovat usecky a pripadne usecky aj odstranovat (s useckami aj ich konce, pripadne nie), tak mas viacero moznosti.

Nielen tieto problemy riesi vypoctova geometria. Nad useckami existuje kopec typov stromov, ktore ti poskytuju logaritmicku zlozitost dotazov, presne ako by si ocakaval. Koho to zaujima, moze skusit pohladat pojmy ako "segment trees", "interval trees", "segment windowing", ale mozem povedat, ze dana problematika je dost narocna, a preto ju mame na FEL CVUT napriklad az v poslednom (5.) rocniku a ja este skusku furt nemam. Tento problem sa vsak da pohodlne riesit aj pomocou BVH (bounding volume hierarchies).

Keby si chcel riesit aj problem vyberu useciek ci trojuholnikov a inych objektov, mozem sa tu o tom skusit trochu rozpisat.
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[micky]

Možná jen tak zlehka, spíš mě odkázat na to, co mám hledat. Pro ten prográmek, co jsem vyrobil, nakonec lineární složitost bude i stačit. Je pravda, že na střední škole toho člověk o octree moc neuslyší.

Nu, mám se co učit.
_________________
https://www.bluepulsar.cz/
https://twitter.com/11thDream_Game/

[Marek]

Na VŠ o octree taky neuslyšíš, pokud si nezapíšeš předmět o optimalizaci grafiky. To jsou věci, na které ti stačí net.
_________________
AMD Open Source Graphics Driver Developer

[pcmaster]

[OT]Tak neviem, my sme mali na akceleracne datove struktury v PG povinny predmet a na vypoctovu geometriu druhy povinny predmet
[ÜBER-OT]S ktorymkolvek computer engineering Bc. sa zapiste na magistersky (Ing.) program FEL CVUT elektrotechnika a informatika - vypoctova technika - pocitacova grafika, odporucam [/ÜBER-OT][/OT]

Eo ma pravdu, quadtree/octree vpoho vygooglis a naimplementujes (po spravnom pochopeni) z netu. Zacni kludne na wikipedii, tam je kopec odkazov.
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Mantharis]

[OT]
Dovolim si nesouhlasit, na skolach informatickyho zamereni by se IMHO rozhodne o zakladnich datovych strukturach pro praci ve vice rozmerech rozhodne mluvit melo v ramci nejakyho povinnyho predmetu uz v BC. studiu.

Skoro bych rekl ze spolecne s algoritmy je to ta uplne nejstezejnejsi cast informatiky...co jinyho pak na informatickych oborech v porovnani s matematickyma oborama ucit nez prave takovyhle veci???

[OT2]
(tim netvrdim ze nekde se to mozna skutecne neuci, ale pak bych na takovy skole teda studovat nechtel )
[/OT2]

[/OT]
_________________
If the God gave us the source code we could bug the world.

[Houp]

[Marek]

[micky]

[Mantharis]