c++ - Best data structure for point traversal -


looking c++ solution.

i had thoughts whether ask question on here or mathexchange etc. since it's more of programming based question posting here.

real problem:

i have xml field as:

<part name='01' x='351' y='151'/>

where x , y, storing qpointf object. also, require name=01 value mapping qpointf object create map.

now there operations need on map :

  • first need points(qpointf) , draw on image.
  • second, modify x , y value of points getting points gui.
  • when points gui, need check x , y value in each qpointf inside map.

problem in simpler form:

i looking data structure such instead of having map of key , qpointf, makes parsing , looking x , y value of points(qpointf) easier. qpointf , key should form unique pair each other, parsing through entire list of points find (x,y) , modifying faster , when x , y value of qpointf modified key attached same.

ps: hope clear problem, if there unclear please edit/comment question can improved.

my guess here important aspect finding set of x , y points when user uses ui. there many acceleration structures possible, recommend point index grid. is, partition indices of points 2d buckets. when user chooses point in ui, can quick look-up on bucket point in, , can iterate on points present in bucket find actual point.

as data, store in array:

struct namepoint {     int name, x, y; }; std::vector<namepoint> points;

now create point index grid refers points array. implementing 1 might worthwhile, otherwise know there exists openvdb version works.

i made small dirty implementation can see principle. have no checks inputs, if you're not careful access out of bounds of vector (e.g., calling pointindexgrid.indicesforpoint(5, 5) gives segmentation fault). 

#include <iostream> #include <vector> #include <limits>  struct namepoint {     int name, x, y; };  template <typename t> // array type can work struct pointindexgrid {     using arraytype = t;     using size_type = typename arraytype::size_type;      pointindexgrid(const arraytype& points, int gridsize)         : mgridsize(gridsize)      {         // find domain. create 2d vector contain vector indices.         maxx = maxy = std::numeric_limits<int>::min();         minx = miny = std::numeric_limits<int>::max();         (const auto& p : points) {             maxx = p.x > maxx ? p.x : maxx;             maxy = p.y > maxy ? p.y : maxy;             minx = p.x < minx ? p.x : minx;             miny = p.x < miny ? p.x : miny;         }          // create buckets         int nbrxbuckets = (maxx - minx)/mgridsize + 1; // due integer arithmetics round down -- lets add 1 in case         int nbrybuckets = (maxy - miny)/mgridsize + 1;         (int n = 0; n < nbrxbuckets; ++n) {             mbuckets.emplace_back(std::vector<std::vector<size_type>>(nbrybuckets));         }          // partition points         (size_type = 0; < points.size(); ++i) {             int xbucket = (points[i].x - minx)/mgridsize; // method how calculate bucket. pure arithmetics -- goes fast             int ybucket = (points[i].y - miny)/mgridsize;             mbuckets[xbucket][ybucket].emplace_back(i);         }     }      std::vector<size_type> indicesforpoint(int x, int y)      {         int xbucket = (x - minx)/mgridsize; // same above         int ybucket = (y - miny)/mgridsize;         return mbuckets[xbucket][ybucket];     }  private:     int mgridsize;     int maxx, minx;     int maxy, miny;     std::vector<std::vector<std::vector<size_type>>> mbuckets; };  int main() {     std::vector<namepoint> points;     points.emplace_back(namepoint{1, 1, 1});     points.emplace_back(namepoint{2, 1, 2});     points.emplace_back(namepoint{3, 1, 2});     points.emplace_back(namepoint{4, 2, 2});     points.emplace_back(namepoint{5, 3, 3});      pointindexgrid<std::vector<namepoint>> pointindexgrid(points, 2);      std::cout << "indices (1, 1): " << std::endl;     (const auto& : pointindexgrid.indicesforpoint(1, 1)) {         std::cout << " " << << std::endl;     }      std::cout << "indices (3, 3): " << std::endl;     (const auto& : pointindexgrid.indicesforpoint(3, 3)) {         std::cout << " " << << std::endl;     } }

this prints out: 

indices (1, 1):   0  1  2  3 indices (3, 3):   4

so find point @ specific (x, y):

  1. partition points using pointindexgrid.
  2. use pointindexgrid.indicesforpoint(x, y).
  3. iterate through indices there (and points in points-array).
  4. grab point want.

Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj
Read more

performance - Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures? -

i'm doing micro-optimization on performance critical part of code , came across sequence of instructions (in at&t syntax): add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx i thought had use case xchg allow me shave instruction , write: add %rbx, %rax xchg %rax, %rdx however, dimay found agner fog's instruction tables , xchg 3 micro-op instruction 2 cycle latency on sandy bridge, ivy bridge, broadwell, haswell , skylake. 3 whole micro-ops , 2 cycles of latency! 3 micro-ops throws off 4-1-1-1 cadence , 2 cycle latency makes worse original in best case since last 2 instructions in original might execute in parallel. now... cpu might breaking instruction micro-ops equivalent to: mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx where tmp anonymous internal register , suppose last 2 micro-ops run in parallel latency 2 cycles. given register renaming occurs on these micro-architectures, though, doesn't make sense me done way. why wouldn't register renamer
Read more

jquery - Responsive Navbar with Sub Navbar -

good day, forgive me nav vocabulary not best. if question confusing apologize. i'm working on navigation bar needs centered on page @ 768px , above. items in nav open (or perhaps toggle) subnav lives directly below. these nav should appear centered on page. i have been able work through responsive portion of nav bar, having main items align vertically , sub nav menu of each item roll out below, , gave them indent separation. working well. however, issue not responsive side, behavior @ width greater 768px. happens toggling menu's sub navigation pushes other main items down page below sub nav. here's code: $(document).ready(function () { //stick in fixed 100% height behind navbar don't wrap $('#slide-nav.navbar-inverse').after($('<div class="inverse" id="navbar-height-col"></div>')); $('#slide-nav.navbar-default').after($('<div id="navbar-height-col"></d
Read more