how can I find the minimum distance from convex boundary

Hi, How to find minimum distance between a point (outside convexhull) and convexhull boundary? Thanks

Answer 1

[Matt J]

If your problem dimension, N, isn't too large, you might be able to use VERT2LCON to convert the region to inequalities

A*x<=b
Aeq*x=beq

Then you can use LSQLIN

closestpoint = lsqlin(speye(N),givenpoint,A,b,Aeq,beq)

Answer 2

[Teja Muppirala]

I like Matt J's SVM-based idea. It is actually very straightforward to solve this as a maximum separation problem.

Reference: http://math.arizona.edu/~hzhang/math574m/2013Lect13_hyperplane.pdf

%% 1. Generate and plot random data

npts = 50;
dims = 2;

P1 = randn(npts,dims);
P2 = randn(1,2); P2 = 5*P2/norm(P2);

dt = delaunay(P1);
figure,hold all;
triplot(dt,P1(:,1),P1(:,2));
plot(P1(:,1),P1(:,2),'b.');
plot(P2(:,1),P2(:,2),'r.','markersize',16);

%% 2. Solve the quadratic programming problem

H = blkdiag(eye(dims),0);
A = [P1 ones(npts,1); -P2 -1];
b = -ones(npts+1,1);
x = quadprog(H,[],A,b,[],[],[],[]);

%% Plot the solution

D =  2/norm(x(1:2)); %distance
S = -2/norm(x(1:2))^2; % scaling for vector
quiver(P2(1),P2(2),S*x(1),S*x(2),1,'r');
title(['Distance is '  num2str(abs(D))]);
axis equal;
grid on;

Answer 3

[John D'Errico]

There can be many faces of a convex hull. However, it is often easily possible to reduce the number of faces one need test.

Several tricks come to mind. First, one can efficiently compute a circumcircle for each facet of the hull. This is done by solving a linear system of equations for each facet. However, if you are careful, then you can put all of those linear systems into a sparse block diagonal system. Then one does the solve in ONE call to backslash, computing all of the circumcircles in one step. If you created the system as a sparse one, this will be FAST.

Next I might rank the facets, in terms of the distance to the circumcenters for those facets. Pick the closest facet using this greedy measure, and compute the true distance to that facet using a standard scheme. (I might use LDP, or something like it. Find LDP in Lawson & Hanson as I recall.) Call that distance Dmin.

You can now exclude many of the other facets from further testing based on the circumradius of the corresponding circumcircle. (Its just a little geometry.) I recall that in my tests you could exclude roughly 90% of the facets directly using this test.

[Sean de Wolski]

Could you only look at facets that contain the vertex of the closest point?

[John D'Errico]

No. That is not sufficient. One can construct a case where the closest point is NOT a vertex of the closest facet.

Admittedly, if you started looking at the facets with the nearest vertices first, this would likely find the truly closest facet soon enough. Again however, you need a scheme to decide when you can stop looking at facets. The circumcircles scheme I described above is a good one, that typically allows you to stop after examining perhaps 10% of the total facets. At that point you can know that no other facet can possibly be closer to the one you have found as best so far.

Answer 4

[Image Analyst]

The bwdist() function in the Image Processing Toolbox will tell you that.

[Image Analyst]

If you're interested in seeing a demo of this in 2 dimensions, see the demo file I attached below (in blue text).

Answer 5

[Sean de Wolski]

http://www.mathworks.com/matlabcentral/fileexchange/24484-geom3d

No reason to reinvent the wheel, compare the distance between each face of the convex hull and the point of interest using distancePointPlane() from the above toolbox and keep the minimum.

[Bhaskar]

Thanks for that, however the data I am working on is mainly more than 3D. Also to find dist with each face will be more time consuming for higher dimen.

Answer 6

[Matt J]

Another possibility might be to use SVMTRAIN, if you have the Statistics Toolbox where the first training group is your single given point and the second training group consists of all the other points defining your polyhedral region.

The output will let you find a supporting hyperplane intersecting your polyhedron. The projection of your given point onto this hyperplane (an easy computation) should give you your closest point.