Describe non-convex region with linear inequality constraints
12 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/977875/image.jpeg)
I want to describe this non-convex region with linear inequality constraints defined by matrix A and vector B. I tried "VERT2CON" function
But it didn't work because it works only for convex regions.
1 comentario
Bruno Luong
el 25 de Abr. de 2022
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.
Respuestas (2)
John D'Errico
el 25 de Abr. de 2022
Editada: John D'Errico
el 25 de Abr. de 2022
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)
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])
PStri = PS.triangulation
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))
1 comentario
Gustavo Lunardon
el 24 de Mayo de 2022
Editada: Gustavo Lunardon
el 24 de Mayo de 2022
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?
Matt J
el 25 de Abr. de 2022
Editada: Matt J
el 25 de Abr. de 2022
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.
4 comentarios
Bruno Luong
el 25 de Abr. de 2022
"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.
Ver también
Categorías
Más información sobre Bounding Regions en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!