computational geometry - Approximation of a solid by a union of spheres -


i've got 3d solid, represented union of set of polyhedral convex hulls. (or single convex, if makes things easier.) i'd approximate solid union of set of spheres, in way minimizes both number of spheres in set , error in approximation. (the latter objective deliberately vague: reasonable error metric do. likewise, way in objectives combined in air; either number of spheres or error metric constrained, or function of 2 minimized. don't want specify myself corner.)

the approximation not need entirely contain or entirely contained original set. each sphere may have arbitrary radius.

this feels sort of problem that's np-complete, , in case unlikely practical using exact methods, i'm assuming solution lies in realm of stochastic optimization. feels variant of k-means might fit (assigning uncovered locations closest spheres, , refining spheres cover of them), i'm not sure how handle multiply-covered locations, or how find local, not-necessarily-covering-everything optimum single sphere. also, iterative methods efficiency important, , doing 3d boolean operations not going efficient.

the problem not simple, has been studied previously. central concept medial axis, can viewed representation of object infinite union of balls. key paper addressing question is:

"the power crust, unions of balls, , medial axis transform." nina amenta, sunghee choi, ravi krishna kolluri. computational geometry. volume 19, issues 2–3, july 2001, pages 127–153. (journal link.)

footballs   shellballs
(images source: from point clouds power crusts.)

a second paper is

cazals, frédéric, et al. "greedy geometric algorithms collection of balls, applications geometric approximation , molecular coarse‐graining." computer graphics forum. vol. 33. no. 6. 2014. (pdf download.)

whose 1st sentence "choosing balls best approximate 3d object non-trivial problem."! primary application molecular models, might far interests.


Comments

Post a Comment

Popular posts from this blog

Email notification in google apps script -

https://support.google.com/docs/answer/91588?hl=en i have sheet the cells filled in data pulled via apps script, website. pull in exact same data, not. on old sheets version use able emails when data "changes" different value. new sheets, email when new data pasted cells, though exact same data......and, can't set @ ranges anymore, entire document. there easy way watch cells when data changes, , email myself? this looks lot you're trying do. for checking whether value has changed after edit, this gives necessary information it. hence, know whether new value same 1 or not. implementing "workaround" talked in second link, able compare , send email myself if value changed. initiate onedit trigger goes off onedit function uses these lines after checks in place have passed. var email = "xyz@whatever.com"; mailapp.sendemail(email, "triggermail", "a change has occurred in sheet"); note: sends "notification...
Read more

c++ - Difference between pre and post decrement in recursive function argument -

i have following sample code used pre-decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(--c); cout << c << endl; return; } } this function give output input 4 : dp3 dp2 dp1 dp0 0 1 2 3 but when use post decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(c--); cout << c << endl; return; } } output goes in infinite loop dp4 can explain me in detail why happens ? this happens because function(c--) called same value of c , when finishes c decremented. recursively called, hence called same value no chance of return , hit stack overflow error. assume this, int x = 1, y = 0; y = x++ result y == 1 , x == 2. if y = ++x , bot x , y 2.
Read more

javascript - IE11 incompatibility with jQuery's 'readonly'? -

the code i'm running has no issues in firefox, or chrome. user typing 1 textbox, tabs next , can continue typing that. when run webpage on ie11, user tabs next textbox , can't type in. textbox has double-clicked before user can insert anything. i've googled , seems ie give problems when using older jquery (i.e. prefers 'prop' 'attr' ). in code below jquery's readonly keyword being used in way ie11 no longer recognise/accept? i assume issue readonly , removeclass('ignore') working expected. //when focus on textbox 1 $("#field1").focus(function() { //remove readonly property textbox 1 $('#field1').prop('readonly', false).removeclass('ignore'); //add readonly property other textboxes $('#field2, #field3, #field4') .prop('readonly', 'readonly').addclass('ignore').val(''); }); i'm using jquery 2.1.3 ...
Read more