Convex set: Finding the A and b matrices from Ax=b when the points of the convex set is known.
4 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
Henrik Rohde Nordhus
il 17 Ott 2022
Background:
I want to create convex sets from points given in a map. E.g. if I have some points distinguishing land and water in a harbor and create a convex set from this. Then I would use the convex set to solve a optimaztion problem.
Specific:
Is there a generic way of finding the A and b matrices from the equation Ax=b where the points of the convex set is known?
Say I have the convex set below with points:
P =
0 0
1.0000 -1.0000
1.5000 -0.5000
1.5000 0.5000
1.0000 1.0000
0 0
How could I extract the matrices A and b such that I could make ineqalities for an opimization problem?
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1159873/image.png)
I've already created a convex set with A = [-1,0; 1,0; -1,1; -1, -1/2]; and b = [300,200,300,600]'; which gave me the convex set below:
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1159878/image.png)
but is it possible to solve it the other way?
Appriciate any help!
Thanks
0 Commenti
Risposta accettata
John D'Errico
il 17 Ott 2022
Modificato: John D'Errico
il 17 Ott 2022
@Matt J has a set of tools for working with such objects.
In there, he has the utility vert2lcon, which can convert a set of vertices from the polytope into a set of linear constraints.
Or, you can go further back, and use the @Michael Kleder code, vert2con, which is less sophisticated, but should still work fine on a simple convex hull in 2-d.
5 Commenti
Matt J
il 12 Mag 2023
Modificato: Matt J
il 12 Mag 2023
I don't know if there's any ready-made Python equivalent to vert2lcon, but it should be possible to make one for someone willing to put in the effort. Everything used internally by vert2lcon are just standard linear algebra tools and convhulln, which does appear to have a scipy equivalent,
You also have the option of calling specific Matlab functions from Python,
Più risposte (2)
Matt J
il 14 Mag 2023
If you only need to address the 2D case, then you can use this:
function [A,b]=vert2ineq2D(a)
%Finds the expression of a 2D convex polygon as a set of linear inequalities from
%a set of vertices
%
% [A,b]=vert2ineq2D(a)
%
%in:
%
% a: Nx2 matrix whos rows are polygon vertex coordinates. The rows must
% must be ordered so that adjacent rows correspond to adjacent vertices
% (which will trivially be the case for triangles).
%
%out:
%
% [A,b]: Nx1 vector and Nx2 matrix such that A*x<=b if and only if x is a point
% inside the polygon
%
%
%Example: Detect whether a point is in a triangle
%
% %%%data
% Vertices=[0 0; 1 0; 0 1]; %vertices of a triangle
% p1=[.5;.25]; %a point inside the triangle
% p2=[.5;-.25];%a point outside the triangle
%
% [A,b]=vert2ineq2D(Vertices);
%
% >>all(A*p1<=b) %Test if p1 is in the triangle.
%
% ans =
%
% 1
%
% >>all(A*p2<=b) %Test if p2 in the triangle.
%
% ans =
%
% 0
centroid=mean(a).';
R=[0 1; -1 0];
A=diff([a;a(1,:)])*R;
b=sum(A.*a,2);
ii=(A*centroid>=b);
b(ii)=-b(ii);
A(ii,:)=-A(ii,:);
0 Commenti
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!