how can I find the minimum distance from convex boundary

30 Ansichten (letzte 30 Tage)
Bhaskar
Bhaskar am 26 Nov. 2013
Beantwortet: Teja Muppirala am 27 Nov. 2013
Hi, How to find minimum distance between a point (outside convexhull) and convexhull boundary? Thanks

Akzeptierte Antwort

Matt J
Matt J am 26 Nov. 2013
Bearbeitet: Matt J am 26 Nov. 2013
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)

Weitere Antworten (5)

Teja Muppirala
Teja Muppirala am 27 Nov. 2013
I like Matt J's SVM-based idea. It is actually very straightforward to solve this as a maximum separation problem.
%% 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 am 26 Nov. 2013
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 Kommentare
Sean de Wolski
Sean de Wolski am 26 Nov. 2013
Bearbeitet: Sean de Wolski am 26 Nov. 2013
Could you only look at facets that contain the vertex of the closest point?
John D'Errico
John D'Errico am 26 Nov. 2013
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.

Melden Sie sich an, um zu kommentieren.


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

Melden Sie sich an, um zu kommentieren.


Sean de Wolski
Sean de Wolski am 26 Nov. 2013
Bearbeitet: Sean de Wolski am 26 Nov. 2013
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 Kommentar
Bhaskar
Bhaskar am 26 Nov. 2013
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.

Melden Sie sich an, um zu kommentieren.


Matt J
Matt J am 26 Nov. 2013
Bearbeitet: Matt J am 26 Nov. 2013
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.

Tags

Community Treasure Hunt

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

Start Hunting!

Translated by