Since the dimension (n) is low, I think that rejection sampling should work pretty well for subproblem 1: start with an equally-spaced grid over the bounding box of the polytope, then do membership tests to reject those points that are outside. The following picture is an example in 2D:
Below is an implementation using LazySets.jl. I used 2D to simplify, but it can be generalized straightforwardly.
using LazySets, Plots
using LazySets: center
function mesh(V::VPolygon{N, VN}, Δ=0.2) where {N, VN<:AbstractVector{N}}
B = overapproximate(V, BallInf) # bounding box
c = center(B)
r = radius(B)
# equally spaced mesh
mesh_x = range(c[1] - r, c[1] + r, step=Δ)
mesh_y = range(c[2] - r, c[2] + r, step=Δ)
# set union of singletons
U = UnionSetArray([Singleton([mx, my]) for mx in mesh_x for my in mesh_y])
inner_points = Vector{Singleton{N, VN}}()
for s in array(U)
p = element(s)
if p ∈ V
push!(inner_points, s)
end
end
return inner_points
end
Example:
V = rand(VPolygon, num_vertices=5)
plot(V, color=:orange)
U = UnionSetArray(mesh(V))
plot!(U, color=:red)
