4
我已经开始研究凸包算法,并且想知道我可以使用什么方法来平滑多边形边缘。船体轮廓不平滑。我想要做的是通过顶点的线条变得更平滑,以免它们成角度。Smooth Convex Hull
我曾尝试推行贝济耶(只实现了形状是不一样的船体形状)和B样条(同样的形状是不一样的,其实我不能做的B轮廓封闭的形状)。
我失败了,希望有人能提供指导。
我已经开始研究凸包算法,并且想知道我可以使用什么方法来平滑多边形边缘。船体轮廓不平滑。我想要做的是通过顶点的线条变得更平滑,以免它们成角度。Smooth Convex Hull
我曾尝试推行贝济耶(只实现了形状是不一样的船体形状)和B样条(同样的形状是不一样的,其实我不能做的B轮廓封闭的形状)。
我失败了,希望有人能提供指导。
(注意!不是解决)
我试图找到确切的解决方案,在极坐标Lagrange polynomial,但找出来,那somtimes“平滑曲线”位于凸多边形内部。通过在theta in [0:2 * pi]
区间外添加额外的可移动不可见点,基本上可以解决一阶导数匹配条件(在起点)。但上述问题在我的脑海里无法解决。
这里是的Lua脚本与我attemptions(使用qhull,rbox(从qhull工具链)和gnuplot的公用事业):
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()
第二端子包含拉格朗日多项式近似。
我觉得catmull rom样条线通常用于图形平滑。它们连续直至并包括一阶。 – Bathsheba
@Bathsheba感谢您的回复......我发现这种方法也可能会创建一条线,该线非常靠近我的凸包,如果两个点适当地靠近 - 这也是一些其他方法的问题看到。我的方法是最好的吗?我不是来自图形背景,所以没有参考点 - 多边形的外边缘如何平滑? – beliskna
我不是图形专家;只是一个不起眼的数学家。但也许你可以考虑从头开始创建一个解决方案:将外围缩小一定的量;通过拼接椭圆的一部分(匹配值和渐变并通过圆点)来修剪角落 - 椭圆的大小是放气量的函数。虽然需要一些时间来弄清楚数学,但它会很顺利,通过所有的点,永远不会在船体外。 – Bathsheba