Cestou domu jsem nad tim jeste premyslel a myslim, ze jsem prisel na to jak ten sweep udelat v podstate efektivneji nez ten KD, protoze by se automaticky rusily nemozne varianty v nejakem mezikruzi hledane vzdalenosti. Mohlo by to byt tedy takto:
1. Udelat si ten soubor jak jsem rikal, ale serazeny dle BUCKET_X a pote dle PT_Y. BUCKET_X se da delat dvema zpusoby:
a) floor(PT_X / BUCKET_SIZE) (zde muze byt kybl ridky anebo naopak nacpany). Da se to napsat jako SQL dotaz order by ...
b) Variabilni sirka tak, aby se naplnil do nejake velikosti (treba 10000 bodu), to uz asi v SQL nepujdea budes muset sesortovat rucne.
2. Ten sweep by jel uplne stejne, jen s tim rozdilem, ze bys mel pointery i na kyble do kterych jeste zasahuje. V nejhorsi variante, bys kontroloval o N (treba tech 10000) bodu vice.
3. Zde prichazi ta hlavni vyhoda, proc ti ty body navic nevadi. Muzes pouzit binarni hledani mezi, ktere body kontrolovat na ose Y. Napr. vis, ze pro bod ke kteremu prave vyhledavas ma Y=1000. Delka kterou hledas je napr 50. Pote hledas v mezich od 950-1050 (cili najdes binarne 950 a traverzujes do 1050) v kazdem kyblu. Pro velke vzdalenosti naopak muzes vyhodit i prostredek a navic vzdalene kybly omezujes rozsah dle nejhorsi kruznice co opisuje hledany bod (980-1020). Pro nekonecne male buckety timto vlastne kontrolujes pouze spravne body na hrane kruznice. 10000 bodu pres tvuj rozsah, ale bude dostatecne uzke a navic nebudes muset delat tolik hledani pro vetsi vzdalenosti. Pro vzdalenost pres celou plochu pak mas nejhorsi variantu 1G / BUCKET_SIZE hledani pro kazdy bod, ale to je asi hodne extremni hledat takove vzdalenosti. Musis holt spravne urcit tu sirku na zaklade vzdalenosti co budes asi hledat.
Vypada to jako pekna cvicna uloha. mozna si to nekdy zkusim
