构造凸包的算法

我们正在考虑用Julia语言在二维空间中构造一组点的凸包（凸包）的算法的实现。

导言

凸包构造算法是一种几何算法，它找到包含所有指定点的最小凸多边形。简单地说，想象一下你在一块板上有一组钉子，你在它们周围拉一个松紧带—这个松紧带的形状将是一个凸包。

该算法用于许多领域：计算机图形学，模式识别，优化，机器人等。在这个例子中，我们使用库 Polyhedra.jl 使用多面体，即用点的V表示（顶点表示）来构建点的凸包。

主要部分

安装必要的软件包（如果尚未安装）

import Pkg; Pkg.add(["Polyhedra", "CDDLib"])

连接图书馆

Polyhedra —使用多面体的主要图书馆

CDDLib -使用双重描述方法计算多面体的库

using Polyhedra, CDDLib, Makie

将一组点定义为顶点表示（V-表示）。

每个点都是坐标[x,y]

Dots = [
    [16,3],  [12,17], [0,6],  [-4,-6], [16,6],
    [16,-7], [16,-3], [17,-4], [5,19], [19,-8],
    [3,16],  [12,13], [3,-4], [17,5],  [-3,15],
    [-3,-9], [0,11],  [-9,-3], [-4,-2], [12,10]
];

vrep —这是一个创建对象的函数 Vertex Representation 从点的列表

A = vrep(Dots)

V-representation Polyhedra.PointsHull{Int64, Vector{Int64}, Int64}:
20-element iterator of Vector{Int64}:
 [16, 3]
 [12, 17]
 [0, 6]
 [-4, -6]
 [16, 6]
 [16, -7]
 [16, -3]
 [17, -4]
 [5, 19]
 [19, -8]
 [3, 16]
 [12, 13]
 [3, -4]
 [17, 5]
 [-3, 15]
 [-3, -9]
 [0, 11]
 [-9, -3]
 [-4, -2]
 [12, 10]

从V表示创建多面体对象

后端正在使用 CDDLib 执行所有计算

P = polyhedron(A, CDDLib.Library())

Polyhedron CDDLib.Polyhedron{Float64}:
20-element iterator of Vector{Float64}:
 [16.0, 3.0]
 [12.0, 17.0]
 [0.0, 6.0]
 [-4.0, -6.0]
 [16.0, 6.0]
 [16.0, -7.0]
 [16.0, -3.0]
 [17.0, -4.0]
 [5.0, 19.0]
 [19.0, -8.0]
 [3.0, 16.0]
 [12.0, 13.0]
 [3.0, -4.0]
 [17.0, 5.0]
 [-3.0, 15.0]
 [-3.0, -9.0]
 [0.0, 11.0]
 [-9.0, -3.0]
 [-4.0, -2.0]
 [12.0, 10.0]

让我们构造点和凸多面体:

# 从多面体P创建网格
m = Polyhedra.Mesh(P);

# 从点矢量中提取X和Y坐标
X = [dot[1] for dot in Dots]  # 第一个元素是X坐标
Y = [dot[2] for dot in Dots]  # 第二个元素是Y坐标

# 为图形创建形状和轴
fig = Figure()
ax = Axis(fig[1, 1])

# 在图形上绘制点
Makie.scatter!(ax, X, Y, markersize=8, color=:red)

# 以半透明蓝色绘制多面体网格
Makie.mesh!(m, color=(:blue,0.5))

# 显示形状
fig

多面体凸包的构造 P 与我自己（事实上，我们得到相同的凸包）

此操作创建一个新对象，表示两个多面体的凸包。

Pch = convexhull(P, P)

Polyhedron CDDLib.Polyhedron{Float64}:
40-element iterator of Vector{Float64}:
 [16.0, 3.0]
 [12.0, 17.0]
 [0.0, 6.0]
 [-4.0, -6.0]
 [16.0, 6.0]
 [16.0, -7.0]
 [16.0, -3.0]
 [17.0, -4.0]
 [5.0, 19.0]
 [19.0, -8.0]
 [3.0, 16.0]
 [12.0, 13.0]
 [3.0, -4.0]
 [17.0, 5.0]
 [-3.0, 15.0]
 [-3.0, -9.0]
 [0.0, 11.0]
 [-9.0, -3.0]
 [-4.0, -2.0]
 [12.0, 10.0]
 [16.0, 3.0]
 [12.0, 17.0]
 [0.0, 6.0]
 [-4.0, -6.0]
 [16.0, 6.0]
 [16.0, -7.0]
  ⋮

从视图中删除冗余点/顶点

也就是说，只剩下真正需要描述凸多边形边界的顶点。

removevredundancy!(Pch)

在屏幕上显示结果-关于多面体的信息（顶点，边等）)

println("$Pch")

convexhull([5.0, 19.0], [19.0, -8.0], [17.0, 5.0], [-3.0, 15.0], [-9.0, -3.0], [12.0, 17.0], [-3.0, -9.0])

一步一步发生了什么？

我们在平面上定义一组点。
使用这些点，我们形成一个V表示，这是一种通过其顶点描述形状的方式。
创建一个"多面体"类型的对象，该对象存储在库的内部格式中。 Polyhedra.
我们建立一个凸包（在这种情况下，我们实际上复制它，因为我们将多面体与自身结合起来）。
从生成的对象中删除多余的点，只留下那些实际定义形状边界的点。
我们打印结果：将显示有关凸多边形顶点的信息。

结论

我们回顾了一个使用库的简单示例。 Polyhedra.jl 用于构造凸包点集合的Julia编程语言。由于该库的强大功能和各种后端的支持，多面体结构可以很容易地构建、分析和可视化。这在解决线性规划、计算机图形学和解析几何中的问题时非常有用。

总之，这个例子允许初学者理解在Julia中处理几何数据和多面体的原则。

该示例是使用[罗塞塔代码]的材料开发的（https://rosettacode.org/wiki/Convex_hull ）