Describe non-convex region with linear inequality constraints
13 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
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
But it didn't work because it works only for convex regions.
1 Commento
Bruno Luong
il 25 Apr 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.
Risposte (2)
John D'Errico
il 25 Apr 2022
Modificato: John D'Errico
il 25 Apr 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 Commento
Gustavo Lunardon
il 24 Mag 2022
Modificato: Gustavo Lunardon
il 24 Mag 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
il 25 Apr 2022
Modificato: Matt J
il 25 Apr 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 Commenti
Bruno Luong
il 25 Apr 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.
Vedere anche
Categorie
Scopri di più su Bounding Regions in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!