Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to define if the point lies on a face of the convex hull?

Subject: How to define if the point lies on a face of the convex hull?

From: Liana

Date: 14 Apr, 2011 08:09:04

Message: 1 of 17

Hello!

There is a 3D convex hull defined as:
K = convhulln(X);

And there is point P = [x y z];

Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.

Thanks.

Subject: How to define if the point lies on a face of the convex hull?

From: Rune Allnor

Date: 14 Apr, 2011 08:38:43

Message: 2 of 17

On Apr 14, 10:09 am, "Liana " <liananapalk...@email.arizona.edu>
wrote:
> Hello!
>
> There is a 3D convex hull defined as:
> K = convhulln(X);
>
> And there is point P = [x y z];
>
> Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.

The brute-force approach is simple:

Loop over all faces:
   1) Test to see if the point lies in the plane
      spanned by the three vertices
   2) If 'yes', test to see if the point is inside
      the vertices
end

However, this approach will take time if there are
many faces. Even more, if you need to do this for
many points.

Rune

Subject: How to define if the point lies on a face of the convex hull?

From: John D'Errico

Date: 14 Apr, 2011 12:26:05

Message: 3 of 17

"Liana" wrote in message <io6a30$li0$1@fred.mathworks.com>...
> Hello!
>
> There is a 3D convex hull defined as:
> K = convhulln(X);
>
> And there is point P = [x y z];
>
> Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.
>
> Thanks.

No matter what you do, you cannot be sure that a point lies
EXACTLY on a face of the hull. Numerical issues will prevent
you from ever determining that a points lies EXACTLY in the
plane, unless you are working with integers and rational
fractions, which you are NOT!

At best, you can test if a point lies within some specified
tolerance of a facet of the hull.

Since you have the points, convhulln gives you the facets
in the form of the triangular faces, so I'm not sure what
your problem is though.

John

Subject: How to define if the point lies on a face of the convex hull?

From: Matt J

Date: 14 Apr, 2011 12:41:05

Message: 4 of 17

"Liana" wrote in message <io6a30$li0$1@fred.mathworks.com>...
> Hello!
>
> There is a 3D convex hull defined as:
> K = convhulln(X);
>
> And there is point P = [x y z];
>
> Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.
=====================

You can use my vert2lcon tool

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities

applied both to X and [X;P].

[A,b,Aeq,beq]=vert2lcon(X,tol);
[A,b,Aeq,beq]=vert2lcon([X;P],tol);

If the output of both are the same, it means that P is within a distance of tol to convhulln(X).

Subject: How to define if the point lies on a face of the convex hull?

From: Matt J

Date: 14 Apr, 2011 13:03:04

Message: 5 of 17

"Matt J" wrote in message <io6q11$qss$1@fred.mathworks.com>...
>
> You can use my vert2lcon tool
>
> http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
>
> applied both to X and [X;P].
>
> [A,b,Aeq,beq]=vert2lcon(X,tol);
> [A,b,Aeq,beq]=vert2lcon([X;P],tol);
>
> If the output of both are the same, it means that P is within a distance of tol to convhulln(X).
========================

Forget that. It won't exclude the case of P being in the interior of the polyhedron.
Just do

 [A,b, Aeq, beq]=vert2lcon(X);

Then test to see whether

(1) A*P'<=b+tolerance

(2) min(abs(A*P'-b))<=tolerance

and if Aeq and beq are non-empty

(3) norm(Aeq*P'-beq)<=tolerance


If there are satisfied, then P will be at the surface of the polyhedron up to the numerical tolerance that you specify. If Aeq and beq are non-empty, then
convhulln(X) is approximately some 1D or 2D polygon floating in 3D space and the test will tell you if P lies at the edge of this polygon.

Subject: How to define if the point lies on a face of the convex hull?

From: Sandro

Date: 14 Apr, 2011 16:14:05

Message: 6 of 17

Hey Liana,

I think vert2lcon function is what you need and if you check online carefully you will find pretty limited (I will say almost no other matlab resource, except the old version of the function) functions directly gives you A,b etc as vert2lcon

When you have a large data set, it is usually hard to see a case that your new pt lie exactly on one hyperplane. Add a tol will make your check meaningful.

Hope that helps a little bit.

Sandro
"Liana" wrote in message <io6a30$li0$1@fred.mathworks.com>...
> Hello!
>
> There is a 3D convex hull defined as:
> K = convhulln(X);
>
> And there is point P = [x y z];
>
> Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.
>
> Thanks.

Subject: How to define if the point lies on a face of the convex hull?

From: Liana

Date: 14 Apr, 2011 17:43:05

Message: 7 of 17

Thank you all for the ideas. I'll check them out.
John: yes, I just missed that K represent indices of exactly triangular facets. I thought that K produce unsorted points.

"Sandro" wrote in message <io76gd$gbn$1@fred.mathworks.com>...
> Hey Liana,
>
> I think vert2lcon function is what you need and if you check online carefully you will find pretty limited (I will say almost no other matlab resource, except the old version of the function) functions directly gives you A,b etc as vert2lcon
>
> When you have a large data set, it is usually hard to see a case that your new pt lie exactly on one hyperplane. Add a tol will make your check meaningful.
>
> Hope that helps a little bit.
>
> Sandro
> "Liana" wrote in message <io6a30$li0$1@fred.mathworks.com>...
> > Hello!
> >
> > There is a 3D convex hull defined as:
> > K = convhulln(X);
> >
> > And there is point P = [x y z];
> >
> > Is it possible to define if the point P lies on a face of the convex hull (not inside)? I know how to implement it if indices of triangular faces are known. However, I know only vertices that constitute the hull.
> >
> > Thanks.

Subject: How to define if the point lies on a face of the convex hull?

From: Liana

Date: 14 Apr, 2011 21:47:04

Message: 8 of 17

I've tried to apply 'vert2lcon' to a simple case, i.e.:

Vertices=[0 0 0; 1 0 0; 0 0 1]; % triangular facet
p = [0.5; 0; 0]; % the point DOES NOT lie on a triangular facet
[A,b, Aeq, beq]=vert2lcon(Vertices);
all(A*p<=b+1e-10)
all(min(abs(A*p2-b))<=1e-10)
% ~isempty(Aeq) && ~isempty(beq)
all(norm(Aeq*p2-beq)<=1e-10)

I received 'true' (1) for all conditions, which means that the point lies on the facet, but it doesn't. I'm sure that I missed something. Please explain me my error. Thanks.

"Matt J" wrote in message <io6ra8$n83$1@fred.mathworks.com>...
> "Matt J" wrote in message <io6q11$qss$1@fred.mathworks.com>...
> >
> > You can use my vert2lcon tool
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
> >
> > applied both to X and [X;P].
> >
> > [A,b,Aeq,beq]=vert2lcon(X,tol);
> > [A,b,Aeq,beq]=vert2lcon([X;P],tol);
> >
> > If the output of both are the same, it means that P is within a distance of tol to convhulln(X).
> ========================
>
> Forget that. It won't exclude the case of P being in the interior of the polyhedron.
> Just do
>
> [A,b, Aeq, beq]=vert2lcon(X);
>
> Then test to see whether
>
> (1) A*P'<=b+tolerance
>
> (2) min(abs(A*P'-b))<=tolerance
>
> and if Aeq and beq are non-empty
>
> (3) norm(Aeq*P'-beq)<=tolerance
>
>
> If there are satisfied, then P will be at the surface of the polyhedron up to the numerical tolerance that you specify. If Aeq and beq are non-empty, then
> convhulln(X) is approximately some 1D or 2D polygon floating in 3D space and the test will tell you if P lies at the edge of this polygon.

Subject: How to define if the point lies on a face of the convex hull?

From: Liana

Date: 15 Apr, 2011 04:36:04

Message: 9 of 17

Sorry, everything works perfectly with 'vert2lcon'.

"Liana" wrote in message <io7q0o$sk2$1@fred.mathworks.com>...
> I've tried to apply 'vert2lcon' to a simple case, i.e.:
>
> Vertices=[0 0 0; 1 0 0; 0 0 1]; % triangular facet
> p = [0.5; 0; 0]; % the point DOES NOT lie on a triangular facet
> [A,b, Aeq, beq]=vert2lcon(Vertices);
> all(A*p<=b+1e-10)
> all(min(abs(A*p2-b))<=1e-10)
> % ~isempty(Aeq) && ~isempty(beq)
> all(norm(Aeq*p2-beq)<=1e-10)
>
> I received 'true' (1) for all conditions, which means that the point lies on the facet, but it doesn't. I'm sure that I missed something. Please explain me my error. Thanks.
>
> "Matt J" wrote in message <io6ra8$n83$1@fred.mathworks.com>...
> > "Matt J" wrote in message <io6q11$qss$1@fred.mathworks.com>...
> > >
> > > You can use my vert2lcon tool
> > >
> > > http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
> > >
> > > applied both to X and [X;P].
> > >
> > > [A,b,Aeq,beq]=vert2lcon(X,tol);
> > > [A,b,Aeq,beq]=vert2lcon([X;P],tol);
> > >
> > > If the output of both are the same, it means that P is within a distance of tol to convhulln(X).
> > ========================
> >
> > Forget that. It won't exclude the case of P being in the interior of the polyhedron.
> > Just do
> >
> > [A,b, Aeq, beq]=vert2lcon(X);
> >
> > Then test to see whether
> >
> > (1) A*P'<=b+tolerance
> >
> > (2) min(abs(A*P'-b))<=tolerance
> >
> > and if Aeq and beq are non-empty
> >
> > (3) norm(Aeq*P'-beq)<=tolerance
> >
> >
> > If there are satisfied, then P will be at the surface of the polyhedron up to the numerical tolerance that you specify. If Aeq and beq are non-empty, then
> > convhulln(X) is approximately some 1D or 2D polygon floating in 3D space and the test will tell you if P lies at the edge of this polygon.

Subject: How to define if the point lies on a face of the convex hull?

From: Jay Berger

Date: 18 Apr, 2011 00:09:04

Message: 10 of 17

Hi Matt,

How can I use this in fmincon?

Jay.

"Matt J" wrote in message <io6ra8$n83$1@fred.mathworks.com>...
> "Matt J" wrote in message <io6q11$qss$1@fred.mathworks.com>...
> >
> > You can use my vert2lcon tool
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
> >
> > applied both to X and [X;P].
> >
> > [A,b,Aeq,beq]=vert2lcon(X,tol);
> > [A,b,Aeq,beq]=vert2lcon([X;P],tol);
> >
> > If the output of both are the same, it means that P is within a distance of tol to convhulln(X).
> ========================
>
> Forget that. It won't exclude the case of P being in the interior of the polyhedron.
> Just do
>
> [A,b, Aeq, beq]=vert2lcon(X);
>
> Then test to see whether
>
> (1) A*P'<=b+tolerance
>
> (2) min(abs(A*P'-b))<=tolerance
>
> and if Aeq and beq are non-empty
>
> (3) norm(Aeq*P'-beq)<=tolerance
>
>
> If there are satisfied, then P will be at the surface of the polyhedron up to the numerical tolerance that you specify. If Aeq and beq are non-empty, then
> convhulln(X) is approximately some 1D or 2D polygon floating in 3D space and the test will tell you if P lies at the edge of this polygon.

Subject: How to define if the point lies on a face of the convex hull?

From: Matt J

Date: 18 Apr, 2011 03:05:21

Message: 11 of 17

"Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iofvf0$gtn$1@fred.mathworks.com>...
> Hi Matt,
>
> How can I use this in fmincon?
>

use it to do what?

Subject: How to define if the point lies on a face of the convex hull?

From: Jay Berger

Date: 18 Apr, 2011 03:39:04

Message: 12 of 17

Use these constraints (i.e. the point to lie on the boundary of the convex hull) for constrained optimization using fmincon. Thanks a bunch for your quickly reply.

"Matt J" wrote in message <iog9ph$ge4$1@fred.mathworks.com>...
> "Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iofvf0$gtn$1@fred.mathworks.com>...
> > Hi Matt,
> >
> > How can I use this in fmincon?
> >
>
> use it to do what?

Subject: How to define if the point lies on a face of the convex hull?

From: Jay Berger

Date: 18 Apr, 2011 04:04:05

Message: 13 of 17

Or the point to lie on the boundary of the convex hull +/- eps. I appreciate any pointers.

To fix the question, a parallel example is to constrain the point p with coordinates (x, y) to lie on a circle s.t. x^2 + y^2 - r^2 = 0. Can we do this for a triangular region (a reduced case of convex hull), s.t. the point p lies on one of the edges of the triangle?

-J

"Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iogboo$m26$1@fred.mathworks.com>...
> Use these constraints (i.e. the point to lie on the boundary of the convex hull) for constrained optimization using fmincon. Thanks a bunch for your quickly reply.
>
> "Matt J" wrote in message <iog9ph$ge4$1@fred.mathworks.com>...
> > "Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iofvf0$gtn$1@fred.mathworks.com>...
> > > Hi Matt,
> > >
> > > How can I use this in fmincon?
> > >
> >
> > use it to do what?

Subject: How to define if the point lies on a face of the convex hull?

From: Matt J

Date: 18 Apr, 2011 13:23:05

Message: 14 of 17

"Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iogd7l$q1c$1@fred.mathworks.com>...
> Or the point to lie on the boundary of the convex hull +/- eps. I appreciate any pointers.
>
> To fix the question, a parallel example is to constrain the point p with coordinates (x, y) to lie on a circle s.t. x^2 + y^2 - r^2 = 0. Can we do this for a triangular region (a reduced case of convex hull), s.t. the point p lies on one of the edges of the triangle?
====================

Hmmm. That's an unusual one. I guess you could try as follows,

(1) Use the output of vert2lcon to obtain the usual linear constraint inputs A,b, Aeq, beq to FMINCON.

(2) Add the non-linear equality constraint, prod(b-A*x)=0. This can only be satisfied when x is at the relative boundary of the polyhedron.

Subject: How to define if the point lies on a face of the convex hull?

From: Jay Berger

Date: 18 Apr, 2011 14:43:22

Message: 15 of 17

Thanks Matt. Do you mean, set ceq to prod(b-A*x) and set A, Aeq, b, beq, c to [] in fmincon?

I tried this and fmincon (backsolveSys.p at 18) is complaining that Matrix is close to singular or badly scaled.

And points are going out of boundary.

"Matt J" wrote in message <iohdvp$7b3$1@fred.mathworks.com>...
> Hmmm. That's an unusual one. I guess you could try as follows,
>
> (1) Use the output of vert2lcon to obtain the usual linear constraint inputs A,b, Aeq, beq to FMINCON.
>
> (2) Add the non-linear equality constraint, prod(b-A*x)=0. This can only be satisfied when x is at the relative boundary of the polyhedron.

Subject: How to define if the point lies on a face of the convex hull?

From: Matt J

Date: 18 Apr, 2011 14:55:20

Message: 16 of 17

"Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iohima$se9$1@ginger.mathworks.com>...
> Thanks Matt. Do you mean, set ceq to prod(b-A*x) and set A, Aeq, b, beq, c to [] in fmincon?

No, set A, Aeq, b, beq to what vert2lcon gives you.

Subject: How to define if the point lies on a face of the convex hull?

From: Jay Berger

Date: 18 Apr, 2011 15:21:07

Message: 17 of 17

It works; sometimes it throws badly conditioned matrix warning. Thanks a bunch Matt.

Jay.
"Matt J" wrote in message <iohjco$1i1$1@ginger.mathworks.com>...
> "Jay Berger" <jayvegbb-remove-this-@gmail.com> wrote in message <iohima$se9$1@ginger.mathworks.com>...
> > Thanks Matt. Do you mean, set ceq to prod(b-A*x) and set A, Aeq, b, beq, c to [] in fmincon?
>
> No, set A, Aeq, b, beq to what vert2lcon gives you.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us