Smooth Convex Hull

Question

J'ai commencé à travailler sur un algorithme de coque convexe et je me demandais quelle méthode je pourrais employer pour lisser le bord du polygone. Le contour de la coque n'est pas lisse. Ce que je voudrais faire, c'est rendre les lignes à travers les vertices plus lisses, afin qu'elles ne soient pas aussi inclinées.

J'ai essayé de mettre en œuvre Béziers (pour se rendre compte de la forme ne ressemblait en rien la forme de la coque) et b-splines (encore une fois la forme ne ressemblait en rien, en fait, je ne pouvais pas faire le b -spline une forme fermée). J'échoue et espère que quelqu'un peut offrir des conseils.

Answer 1

(Remarque: ce n'est pas la solution)

J'ai essayé de trouver la solution exacte Lagrange polynomial en coordonnées polaires, mais savoir que somtimes « courbe de lissage » se trouve à l'intérieur du polygone convexe. La première condition de correspondance des dérivées (au point de départ) est fondamentalement soluble en ajoutant un point invisible mobile supplémentaire en dehors de l'intervalle theta in [0:2 * pi]. Mais le problème ci-dessus n'est pas résolu de toute façon à mon avis.

Voici le Lua script avec mes attemptions (utilise qhull, Rbox (de qhull toolchain) et gnuplot services publics):

function using() 
    return error('using: ' .. arg[0] .. ' <number of points>') 
end 

function points_from_file(infile) 
    local points = {} 
    local infile = io.open(infile, 'r') 
    local d = infile:read('*number') 
    if d ~= 2 then 
     error('dimensions is not two') 
    end 
    local n = infile:read('*number') 
    while true do 
     local x, y = infile:read('*number', '*number') 
     if not x and not y then 
      break 
     end 
     if not x or not y then 
      error('wrong format of input file: line does not contain two coordinates') 
     end 
     table.insert(points, {x, y}) 
    end 
    infile:close() 
    if n ~= #points then 
     error('second line not contain real count of points') 
    end 
    return points 
end 

if not arg then 
    error("script should use as standalone") 
end 
if #arg ~= 1 then 
    using() 
end 
local n = tonumber(arg[1]) 
if not n then 
    using() 
end 
local bounding_box = math.sqrt(math.pi)/2.0 
local fnp = os.tmpname() 
local fnchp = os.tmpname() 
os.execute('rbox ' .. n .. ' B' .. bounding_box .. ' D2 n t | tee ' .. fnp .. ' | qhull p | tee ' .. fnchp .. ' > nul') -- Windows specific part is "> nul" 
local sp = points_from_file(fnp) -- source points 
os.remove(fnp) 
local chp = points_from_file(fnchp) -- convex hull points 
os.remove(fnchp) 
local m = #chp 
if m < 3 then 
    io.stderr:write('convex hull consist of less than three points') 
    return 
end 
local pole = {0.0, 0.0} -- offset of polar origin relative to cartesian origin 
for _, point in ipairs(chp) do 
    pole[1] = pole[1] + point[1] 
    pole[2] = pole[2] + point[2] 
end 
pole[1] = pole[1]/m 
pole[2] = pole[2]/m 
print("pole = ", pole[1], pole[2]) 
local chcc = {} 
for _, point in ipairs(chp) do 
    table.insert(chcc, {point[1] - pole[1], point[2] - pole[2]}) 
end 
local theta_min = 2.0 * math.pi -- angle between abscissa ort of cartesian and ort of polar coordinates 
local rho_mean = 0.0 
local rho_max = 0.0 
local chpc = {} -- {theta, rho} pairs 
for _, point in ipairs(chcc) do 
    local rho = math.sqrt(point[1] * point[1] + point[2] * point[2]) 
    local theta = math.atan2(point[2], point[1]) 
    if theta < 0.0 then -- [-pi:pi] -> [0:2 * pi] 
     theta = theta + 2.0 * math.pi 
    end 
    table.insert(chpc, {theta, rho}) 
    if theta_min > theta then 
     theta_min = theta 
    end 
    rho_mean = rho_mean + rho 
    if rho_max < rho then 
     rho_max = rho 
    end 
end 
theta_min = -theta_min 
rho_mean = rho_mean/m 
rho_max = rho_max/rho_mean 
for pos, point in ipairs(chpc) do 
    local theta = (point[1] + theta_min)/math.pi -- [0:2 * pi] -> [0:2] 
    local rho = point[2]/rho_mean 
    table.remove(chpc, pos) 
    table.insert(chpc, pos, {theta, rho}) 
end 
table.sort(chpc, function (lhs, rhs) return lhs[1] < rhs[1] end) 
-- table.insert(chpc, {chpc[#chpc][1] - 2.0 * math.pi, chpc[#chpc][2]}) 
table.insert(chpc, {2.0, chpc[1][2]}) 
-- table.sort(chpc, function (lhs, rhs) return lhs[1] < rhs[1] end) 

local solution = {} 
solution.x = {} 
solution.y = {} 
for _, point in ipairs(chpc) do 
    table.insert(solution.x, point[1]) 
    table.insert(solution.y, point[2]) 
end 
solution.c = {} 
for i, xi in ipairs(solution.x) do 
    local c = solution.y[i] 
    for j, xj in ipairs(solution.x) do 
     if i ~= j then 
      c = c/(xi - xj) 
     end 
    end 
    solution.c[i] = c 
end 
function solution:monomial(i, x) 
    local y = self.c[i] 
    for j, xj in ipairs(solution.x) do 
     if xj == x then 
      if i == j then 
       return self.y[i] 
      else 
       return 0.0 
      end 
     end 
     if i ~= j then 
      y = y * (x - xj) 
     end 
    end 
    return y 
end 
function solution:polynomial(x) 
    local y = self:monomial(1, x) 
    for i = 2, #solution.y do 
     y = y + self:monomial(i, x) 
    end 
    return y 
end 

local gnuplot = io.popen('gnuplot', 'w') 

gnuplot:write('reset;\n') 
gnuplot:write('set terminal wxt 1;\n') 
gnuplot:write(string.format('set xrange [%f:%f];\n', -bounding_box, bounding_box)) 
gnuplot:write(string.format('set yrange [%f:%f];\n', -bounding_box, bounding_box)) 
gnuplot:write('set size square;\n') 
gnuplot:write(string.format('set xtics %f;\n', 0.1)) 
gnuplot:write(string.format('set ytics %f;\n', 0.1)) 
gnuplot:write('set grid xtics ytics;\n') 
gnuplot:write('plot "-" using 1:2 notitle with points, "-" using 1:2:3:4 notitle with vectors;\n') 
for _, point in ipairs(sp) do 
    gnuplot:write(string.format('%f %f\n', point[1], point[2])) 
end 
gnuplot:write('e\n') 
for _, point in ipairs(chcc) do 
    gnuplot:write(string.format('%f %f %f %f\n', pole[1], pole[2], point[1], point[2])) 
end 
gnuplot:write('e\n') 
gnuplot:flush(); 

gnuplot:write('reset;\n') 
gnuplot:write('set terminal wxt 2;\n') 
gnuplot:write('set border 0;\n') 
gnuplot:write('unset xtics;\n') 
gnuplot:write('unset ytics;\n') 
gnuplot:write('set polar;\n') 
gnuplot:write('set grid polar;\n') 
gnuplot:write('set trange [-pi:2 * pi];\n') 
gnuplot:write(string.format('set rrange [-0:%f];\n', rho_max)) 
gnuplot:write('set size square;\n') 
gnuplot:write('set view equal xy;\n') 
-- gnuplot:write(string.format('set xlabel "%f";\n', rho_mean - 1.0)) 
gnuplot:write(string.format('set arrow 1 from 0,0 to %f,%f;\n', rho_max * math.cos(theta_min), rho_max * math.sin(theta_min))) 
gnuplot:write(string.format('set label 1 " origin" at %f,%f left rotate by %f;\n', rho_max * math.cos(theta_min), rho_max * math.sin(theta_min), math.deg(theta_min))) 
gnuplot:write('plot "-" using 1:2:3:4 notitle with vectors, "-" using 1:2 notitle with lines, "-" using 1:2 notitle with lines;\n') 
for _, point in ipairs(chpc) do 
    gnuplot:write(string.format('0 0 %f %f\n', point[1] * math.pi, point[2])) 
end 
gnuplot:write('e\n') 
for _, point in ipairs(chpc) do 
    gnuplot:write(string.format('%f %f\n', point[1] * math.pi, point[2])) 
end 
gnuplot:write('e\n') 
do 
    local points_count = 512 
    local dx = 2.0/points_count 
    local x = 0.0 
    for i = 1, points_count do 
     gnuplot:write(string.format('%f %f\n', x * math.pi, solution:polynomial(x))) 
     x = x + dx 
    end 
    gnuplot:write('e\n') 
end 
gnuplot:flush(); 

gnuplot:write('reset;\n') 
gnuplot:write('set terminal wxt 3;\n') 
gnuplot:write(string.format('set xrange [-1:2];\n')) 
gnuplot:write(string.format('set yrange [0:2];\n')) 
gnuplot:write(string.format('set size ratio %f;\n', rho_max/3.0)) 
gnuplot:write(string.format('set xtics %f;\n', 0.5)) 
gnuplot:write(string.format('set ytics %f;\n', 0.5)) 
gnuplot:write('set grid xtics ytics;\n') 
gnuplot:write(string.format('set arrow 1 nohead from 0,%f to 2,%f linetype 3;\n', chpc[1][2], chpc[1][2])) 
gnuplot:write(string.format('set label 1 "glue points " at 0,%f right;\n', chpc[1][2])) 
gnuplot:write('plot "-" using 1:2 notitle with lines, "-" using 1:2 notitle with lines;\n') 
for _, point in ipairs(chpc) do 
    gnuplot:write(string.format('%f %f\n', point[1], point[2])) 
end 
gnuplot:write('e\n') 
do 
    local points_count = 512 
    local dx = 2.0/points_count 
    local x = 0.0 
    for i = 1, points_count do 
     gnuplot:write(string.format('%f %f\n', x, solution:polynomial(x))) 
     x = x + dx 
    end 
    gnuplot:write('e\n') 
end 
gnuplot:flush(); 

os.execute('pause'); 
gnuplot:write('exit\n'); 
gnuplot:flush(); 
gnuplot:close() 

La seconde borne contient polynôme de Lagrange approximation.