# Mesh/grid over convex polytope

**URL:** <https://discourse.julialang.org/t/mesh-grid-over-convex-polytope/36047>\
**Category:** Numerics\
**Tags:** question, polygons, convex-hull\
**Created:** [March 16, 2020, 4:30pm UTC](https://discourse.julialang.org/t/mesh-grid-over-convex-polytope/36047 "2020-03-16T16:30:24Z")\
**Posts on this page:** 1\
**Showing post:** 11

<div class="post-metadata">

**Author:** ![mforets](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mforets/32/298_2.png) [@mforets](https://discourse.julialang.org/u/mforets)\
**Post date:** [March 17, 2020, 11:08am UTC](https://discourse.julialang.org/t/mesh-grid-over-convex-polytope/36047/11 "2020-03-17T11:08:53Z")

</div>

> [@Tamas\_Papp](#):
>
> I am totally fine with whatever approximation/definition of “equispaced” and "nearest’ that make this problem easy.

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:

 ![Screenshot from 2020-03-17 07-56-51](https://global.discourse-cdn.com/julialang/original/3X/a/5/a5cdbd855e9fec0a024836e34fe6782e12c634d6.png)

Below is an implementation using [LazySets.jl](https://github.com/JuliaReach/LazySets.jl/). I used 2D to simplify, but it can be generalized straightforwardly.

```julia
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:

```julia
V = rand(VPolygon, num_vertices=5)
plot(V, color=:orange)
U = UnionSetArray(mesh(V))
plot!(U, color=:red)

```

 ![Screenshot from 2020-03-17 08-07-04](https://global.discourse-cdn.com/julialang/original/3X/c/3/c3790e175e46e99a553eadb542cb8297dfcbf9f7.png)

---

_[View the full topic](https://discourse.julialang.org/t/mesh-grid-over-convex-polytope/36047)._