Describe non-convex region with linear inequality constraints

I have a non-convex region defined by 11 vertices. Vertices=[-10 -10;1.5917 -3.0124; 1.7397 -2.7681;3.593 0.0829; 3.6007 0.2915; 10 10; 1.8083 2.7011; 1.4453 2.6976; 1.2086 2.6874; 0.8259 2.7114; -10 -10 ] as shown in the following figure

I want to describe this non-convex region with linear inequality constraints defined by matrix A and vector B. I tried "VERT2CON" function

https://www.mathworks.com/matlabcentral/fileexchange/7895-vert2con-vertices-to-constraints

But it didn't work because it works only for convex regions.

[Bruno Luong]

May be not the most efficient, but if you goal is to optimize some function on your (non-convex) polygon. Decompose it a set of triangles, optimize a subproblems of your function on each triangle (now it is a convex domain), then take the best of all subsolutions.

Answer 1

[John D'Errico]

Nothing stops you from dissecting a polygonal region into triangles, even if not convex. As Matt said, you CANNOT use a set of linear inequalities to describe a non-convex domain. But you can still work with non-convex domains.

Vertices=[-10 -10;1.5917 -3.0124; 1.7397 -2.7681;3.593 0.0829; 3.6007 0.2915; 10 10; 1.8083 2.7011; 1.4453 2.6976; 1.2086 2.6874; 0.8259 2.7114; -10 -10 ];
PS = polyshape(Vertices)

PS = 
  polyshape with properties:

      Vertices: [10×2 double]
    NumRegions: 1
      NumHoles: 0

plot(PS)

So a simple non-convex domain. If all you need to do is test to see if a pointlies inside it, then isinterior solves the problem immediately and directly. (inpolygon would have solved the problem without even generating a polyshape, but I have no idea why you think you need to solve this problam as you think you want.)

PS.isinterior([.1 .1;0 10])

ans = 2×1 logical array
   1
   0

PStri = PS.triangulation

PStri = 
  triangulation with properties:

              Points: [10×2 double]
    ConnectivityList: [8×3 double]

8 triangles are the result, at least as generated by the methods employed by the triangulation tool for polyshapes.

trimesh(PStri.ConnectivityList,PStri.Points(:,1),PStri.Points(:,2))

[Gustavo Lunardon]

Interesting. My question is directly related to OP's but in a slightly different context. What if x and y represent experimental conditions and we plan to execute, say, 4 experiments?

Meaning, 8 variables to optimize in four sets of 2, in an optimal experimental design problem.

We cannot know a priori in which of those triangles in the feasible space those 4 experiments lie. Is there an intelligent way of solving the problem, without passing nonlinear constraints filled with a long list with elseif's to the solver but rather using this triangulation strategy? Maybe using PS.isinterior as a nonlinear constraint?

Answer 2

[Matt J]

You cannot. A system of linear (in)equalities always corresponds to a convex region. However, you can use inpolygon() to test whether a point is inside a non-convex polygon.

If this is being done for optimization purposes, you can use delauny() to divide the polygon into triangles (which are convex) and then you can optimize over each triangle separately.

[Amna Mazen]

Thank you for your response.

Yes, this is done for optimization purposes.

If I use delaunay function it includes triangles that outside my region as shown in the following figure

Since system of linear (in)equalities always corresponds to a convex region, I need linear inequality constraints that describe the maximum convex region inside my nonconvex region.

[Matt J]

If I used delaunay function it includes triangles that outside my region as shown in the following figure

OK, but if you compute the centroids of all the delaunay triangles, you can then use inpolygon() to see if the centroid lies inside the original polygon. If it doesn't, you can discard that triangle.

I need linear inequality constraints that describe the maximum convex region inside my nonconvex region.

Didn't understand that part. Don't you need to optimize over the total region?

[Matt J]

If I used delaunay function it includes triangles that outside my region as shown in the following figure

It looks like there is a polyshape method that will also avoid this problem,

T = triangulation(polyshape(Vertices));

[Bruno Luong]

"I need linear inequality constraints that describe the maximum convex region inside my nonconvex region. "

You need it to have less sub-problems. Granted it's might be speed up your optimization. But you can always optimize in the triangles (after all you have less then 10 of them).

I'm not so sure finding a largest convex embeded within a non convex shape is a trivial task and it requires a side optimization problem on its own.

Another idea is that you can map you non-convex 2D polygon in a convex one using conformal mapping. Then do optimization on the convex domain.