Describe non-convex region with linear inequality constraints
조회 수: 7 (최근 30일)
이전 댓글 표시
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
Bruno Luong
2022년 4월 25일
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.
답변 (2개)
John D'Errico
2022년 4월 25일
편집: John D'Errico
2022년 4월 25일
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
Gustavo Lunardon
2022년 5월 24일
편집: Gustavo Lunardon
2022년 5월 24일
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
2022년 4월 25일
편집: Matt J
2022년 4월 25일
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
Bruno Luong
2022년 4월 25일
"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.
참고 항목
카테고리
Help Center 및 File Exchange에서 Bounding Regions에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!