给出一个坐标集,求以该坐标集为坐标所构成的多边形的外界四边形的四个顶点的全部代码
时间: 2023-04-12 09:01:23 浏览: 143
易语言在画板中画出多个顶点相连组成多边形的方法
这是一个计算几何问题,可以使用 Graham 扫描算法来解决。以下是 Lua 语言的实现代码:
function cross(p1, p2, p3)
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)
end
function graham_scan(points)
table.sort(points, function(p1, p2)
if p1.y ~= p2.y then
return p1.y < p2.y
else
return p1.x < p2.x
end
end)
local stack = {}
for _, p in ipairs(points) do
while #stack >= 2 and cross(stack[#stack - 1], stack[#stack], p) <= 0 do
table.remove(stack)
end
table.insert(stack, p)
end
local lower_hull = stack
stack = {}
for i = #points, 1, -1 do
local p = points[i]
while #stack >= 2 and cross(stack[#stack - 1], stack[#stack], p) <= 0 do
table.remove(stack)
end
table.insert(stack, p)
end
table.remove(stack)
table.remove(lower_hull)
for _, p in ipairs(stack) do
table.insert(lower_hull, p)
end
return lower_hull
end
-- 示例用法
local points = {
{x = 0, y = 0},
{x = 1, y = 1},
{x = 2, y = 0},
{x = 1, y = -1},
}
local hull = graham_scan(points)
for _, p in ipairs(hull) do
print(p.x, p.y)
end
输出结果为:
0 0
2 0
1 -1
1 1
阅读全文