how can I find the minimum distance from convex boundary

40 次查看（过去 30 天）
Bhaskar
Bhaskar 2013-11-26
回答： Teja Muppirala 2013-11-27
Hi, How to find minimum distance between a point (outside convexhull) and convexhull boundary? Thanks

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2013-11-26
编辑：Matt J 2013-11-26
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)

更多回答（5 个）

Teja Muppirala
Teja Muppirala 2013-11-27
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;
John D'Errico
John D'Errico 2013-11-26
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.
  2 个评论
Sean de Wolski
Sean de Wolski 2013-11-26
编辑：Sean de Wolski 2013-11-26
Could you only look at facets that contain the vertex of the closest point?
John D'Errico
John D'Errico 2013-11-26
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.

请先登录，再进行评论。

Image Analyst
Image Analyst 2013-11-26
The bwdist() function in the Image Processing Toolbox will tell you that.
  1 个评论
Image Analyst
Image Analyst 2013-11-26
If you're interested in seeing a demo of this in 2 dimensions, see the demo file I attached below (in blue text).

请先登录，再进行评论。

Sean de Wolski
Sean de Wolski 2013-11-26
编辑：Sean de Wolski 2013-11-26
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.
  1 个评论
Bhaskar
Bhaskar 2013-11-26
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.

请先登录，再进行评论。

Matt J
Matt J 2013-11-26
编辑：Matt J 2013-11-26
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.

类别

在 Help Center 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by