Convex set: Finding the A and b matrices from Ax=b when the points of the convex set is known.
6 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Henrik Rohde Nordhus
el 17 de Oct. de 2022
Respondida: Matt J
el 14 de Mayo de 2023
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?
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:
but is it possible to solve it the other way?
Appriciate any help!
Thanks
0 comentarios
Respuesta aceptada
John D'Errico
el 17 de Oct. de 2022
Editada: John D'Errico
el 17 de Oct. de 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 comentarios
Matt J
el 12 de Mayo de 2023
Editada: Matt J
el 12 de Mayo de 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,
Más respuestas (2)
Matt J
el 14 de Mayo de 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 comentarios
Ver también
Categorías
Más información sobre Computational Geometry 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!