View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0006641||Source patches||Server||public||2011-11-04 22:18||2011-11-09 08:47|
|Target Version||1.2||Fixed in Version||1.2|
|Summary||0006641: patch: CZoneNames speedup - from O(n) to O(n^c), 0<c<1|
Currently, CZoneNames::GetZone(vecPosition) iterates over every defined zone and selects smallest one that is bounding the point given as argument. Lookup takes O(n) time.
It can be brought down to O(n^c), 0<c<1 by simply sorting zones by their volume, and updating algorithm to return first zone matching.
Attached patch contains updated GetZone() method and new (sorted) zone definitions. Number format differs slightly, but are values all exact the same, included those given in scientific notation.
Patch applies both to client and server copies of CZoneNames.
|Tags||No tags attached.|