Mám mapu a je na nej zobrazených veľa značiek. Niekedy sú značky tak blízko pri sebe, že sa prekrývajú. Aby som to napravil, implementoval som knižnicu spiderfier, ktorá túto situáciu napraví.
Cieľom je zoskupiť značky, ktoré sú dostatočne blízko nahor na obrazovke (matematicky nadol), tak, aby sa navzájom nepretínali.
Značky sa zobrazujú ako obdĺžniky.
realizácie:
- prechádza značkami a značkami, ktoré sa pretínajúkaždý ďalší je zahrnutý do skupiny so stredom ((minX + maxX) / 2, maxY) a polomer je dostatočne veľký na to, aby zobrazoval značky na periférii bez vzájomného pretínania
- zatiaľ čo existujú polkruhy, ktoré sa navzájom pretínajú, zlúčime ich do väčšieho polkruhu
- značky roztriedime podľa komparátora, pričom „menšie“ značky umiestnime doľava na perifériu kruhu v porovnaní s ich „väčšími“ náprotivkami.
- zobrazujeme značky v hornej polovici kruhu, ale zobrazujeme čiaru z ich upraveného umiestnenia do ich skutočného umiestnenia
Zatiaľ je všetko dobré.
Problém: Tieto priamky sa navzájom pretínajú príliš často a potrebujeme komparačnú funkciu, pomocou ktorej je počet priesečníkov značkových čiar minimalizovaný.
pokúsi:
P1.x <= P2.x => P1 <= P2
arktán ((P1.y - Cy) / (R * (P1.x - Cx))) <= arktán ((P2.y - Cy) / (R * (P2.x - Cx))) => P1 < = P2
Do druhého pokusu som vkladal veľké nádeje, ale maluznať, že to nie je dobrý nápad, pretože prekladová čiara a čiara medzi skutočným umiestnením a stredom kruhu nie sú nevyhnutne kolineárne, v skutočnosti môže byť ich uhol dosť veľký, ak existuje veľa značiek s ich skutočným umiestnením veľmi blízko seba, zatiaľ čo povrch polkruhu okrem tejto podoblasti je dosť neúrodný. Vedie to tiež ku križovatkám a je to oveľa zložitejšie ako pri prvom pokuse. Verím, že Javascript Math.atan sa implementuje buď pomocou Taylorov rad alebo Fourierova séria, ktorá v prvom prípade zahŕňa derivátya integrálne v druhom prípade. Alebo môže existovať tretí prístup, ktorý je tiež veľmi zložitý. Premýšľal by som o optimalizáciách a podobných veciach, ak by tento druhý prístup výrazne znížil počet križovatiek, ale keďže zlepšenie je sotva pozorovateľné, ak vôbec, vrátil som sa k prvému prístupu.
Mám na mysli nasledujúci prístup:
- vypočítať umiestnenie štrbín pre značkovače na periférii
- pokúste sa preložiť všetky značky do ich najbližšej možnej pozície
- nájsť konfliktné skupiny a vyriešiť všetky konflikty nájdením optima, ktorým je sada prekladov s najmenším celkovým prekladom
Vedie táto myšlienka k stavu, keď je číslo križovatky spider line minimalizované, a ak nie, ako by som mohol minimalizovať počet takýchto križovatiek?
odpovede:
1 pre odpoveď č. 1Jedná sa o zložitý problém, ktorý je už dlho študovaný. Niekedy sa tomu hovorí automatické umiestnenie štítku. Ďalej uvedená práca je typická pre to, čo je dostupné v literatúre.
/>
/>
Van Kreveld, Marc, Tycho Strijk a Alexander Wolff. "Označenie množiny bodov s posuvnými štítkami." Zborník referátov zo štrnásteho ročníka sympózia o výpočtovej geometrii. ACM, 1998. Odkaz ACM.